cp's OEIS Frontend

A047889 Number of permutations in S_n with longest increasing subsequence of length <= 4.

%I A047889 #65 Sep 02 2025 11:57:58
%S A047889 1,1,2,6,24,119,694,4582,33324,261808,2190688,19318688,178108704,
%T A047889 1705985883,16891621166,172188608886,1801013405436,19274897768196,
%U A047889 210573149141896,2343553478425816,26525044132374656,304856947930144656
%N A047889 Number of permutations in S_n with longest increasing subsequence of length <= 4.
%C A047889 Or, number of permutations in S_n that avoid the pattern 12345, - _N. J. A. Sloane_, Mar 19 2015
%C A047889 Also, the dimension of the space of SL(4)-invariants in V^m ⊗ (V^*)^m, where V is the standard 4-dimensional representation of SL(4) and V^* its dual. - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
%H A047889 Gheorghe Coserea, <a href="/A047889/b047889.txt">Table of n, a(n) for n = 0..300</a>
%H A047889 F. Bergeron and F. Gascon, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL3/CYT/cyt.html">Counting Young tableaux of bounded height</a>, J. Integer Sequences, Vol. 3 (2000), #00.1.7.
%H A047889 Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, <a href="https://arxiv.org/abs/2001.00393">Stieltjes moment sequences for pattern-avoiding permutations</a>, arXiv:2001.00393 [math.CO], 2020.
%H A047889 Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, <a href="http://arxiv.org/abs/1504.02513">The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r</a>, arXiv:1504.02513 [math.CO], 2015.
%H A047889 Peter J. Forrester and Fei Wei, <a href="https://arxiv.org/abs/2508.20797">Higher order linear differential equations for unitary matrix integrals: applications and generalisations</a>, arXiv:2508.20797 [math-ph], 2025.
%H A047889 Ira M. Gessel, <a href="http://dx.doi.org/10.1016/0097-3165(90)90060-A">Symmetric functions and P-recursiveness</a>, J. Combin. Theory A 53 (1990), 257-285.
%H A047889 Permutation Pattern Avoidance Library (PermPAL), <a href="https://permpal.com/perms/name/01234/">12345</a>
%H A047889 Nathaniel Shar, <a href="https://pdfs.semanticscholar.org/98e3/71b675789ed6ec4f9c9cd82e2dee9ca79399.pdf">Experimental methods in permutation patterns and bijective proof</a>, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
%H A047889 <a href="/index/Y#Young">Index entries for sequences related to Young tableaux.</a>
%F A047889 a(0)=1, a(1)=1, (n^3 + 16*n^2 + 85*n + 150)*a(n+2) = (20*n^3 + 182*n^2 + 510*n + 428)*a(n+1) - (64*n^3 + 256*n^2 + 320*n + 128)*a(n). - Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
%F A047889 a(n) = (64*(n+1)*(2*n^3 + 21*n^2 + 76*n + 89)*A002895(n) -(8*n^4 + 104*n^3 + 526*n^2 + 1098*n + 776) *A002895(n+1)) / (3*(n+2)^3*(n+3)^3*(n+4)). - _Mark van Hoeij_, Jun 02 2010
%F A047889 a(n) ~ 3 * 2^(4*n + 9) / (n^(15/2) * Pi^(3/2)). - _Vaclav Kotesovec_, Sep 10 2014
%e A047889 G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 119*x^5 + 694*x^6 + 4582*x^7 + ...
%p A047889 A:=rsolve({a(0) = 1, a(1) = 1, (n^3 + 16*n^2 + 85*n + 150)*a(n + 2) = (20*n^3 + 182*n^2 + 510*n + 428)*a(n + 1) - (64*n^3 + 256*n^2 + 320*n +128)*a(n)}, a(n), makeproc): # Alec Mihailovs (alec(AT)mihailovs.com), Aug 14 2005
%t A047889 Flatten[{1,RecurrenceTable[{64*(-1+n)^2*n*a[-2+n]-2*(-12 + 11*n + 31*n^2 + 10*n^3)*a[-1+n] + (3+n)^2*(4+n)*a[n]==0,a[1]==1,a[2]==2},a,{n,20}]}] (* _Vaclav Kotesovec_, Sep 10 2014 *)
%o A047889 (PARI) {a(n) = my(v); if( n<2, n>=0, v = vector(n+1, k, 1); for(k=2, n, v[k+1] = ((20*k^3 + 62*k^2 + 22*k - 24) * v[k] - 64*k*(k-1)^2 * v[k-1]) / ((k+3)^2 * (k+4))); v[n+1])}; /* _Michael Somos_, Apr 19 2015 */
%Y A047889 A column of A047888.
%Y A047889 Cf. A005802, A047890, A052399.
%Y A047889 Column k=4 of A214015.
%Y A047889 Representatives for the 16 Wilf-equivalence patterns of length 5 are given in A116485, A047889, and A256195-A256208. - _N. J. A. Sloane_, Mar 19 2015
%K A047889 nonn,easy,changed
%O A047889 0,3
%A A047889 Eric Rains (rains(AT)caltech.edu), _N. J. A. Sloane_
%E A047889 More terms from _Naohiro Nomoto_, Mar 01 2002
%E A047889 Edited by _N. J. A. Sloane_, Aug 23 2008 at the suggestion of _R. J. Mathar_