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

1, 1, 2, 6, 24, 119, 694, 4582, 33324, 261808, 2190688, 19318688, 178108704, 1705985883, 16891621166, 172188608886, 1801013405436, 19274897768196, 210573149141896, 2343553478425816, 26525044132374656, 304856947930144656

Offset

0,3

Comments

Or, number of permutations in S_n that avoid the pattern 12345, - N. J. A. Sloane, Mar 19 2015

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

Links

Gheorghe Coserea, Table of n, a(n) for n = 0..300

F. Bergeron and F. Gascon, Counting Young tableaux of bounded height, J. Integer Sequences, Vol. 3 (2000), #00.1.7.

Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.

Shalosh B. Ekhad, Nathaniel Shar, and Doron Zeilberger, The number of 1...d-avoiding permutations of length d+r for SYMBOLIC d but numeric r, arXiv:1504.02513 [math.CO], 2015.

Ira M. Gessel, Symmetric functions and P-recursiveness, J. Combin. Theory A 53 (1990), 257-285.

Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.

Index entries for sequences related to Young tableaux.

Formula

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

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

a(n) ~ 3 * 2^(4*n + 9) / (n^(15/2) * Pi^(3/2)). - Vaclav Kotesovec, Sep 10 2014

Example

G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 119*x^5 + 694*x^6 + 4582*x^7 + ...

Maple

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

Mathematica

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 *)

Prog

(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 */

Crossrefs

A column of A047888.

Cf. A005802, A047890, A052399.

Column k=4 of A214015.

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

Sequence in context: A116485 A256206 A052397 * A256207 A256208 A264432

Adjacent sequences: A047886 A047887 A047888 * A047890 A047891 A047892

Keyword

nonn,easy

Author

Eric Rains (rains(AT)caltech.edu), N. J. A. Sloane

Extensions

More terms from Naohiro Nomoto, Mar 01 2002

Edited by N. J. A. Sloane, Aug 23 2008 at the suggestion of R. J. Mathar

Status

approved