login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A047889 Number of permutations in S_n with longest increasing subsequence of length <= 4. 30
1, 1, 2, 6, 24, 119, 694, 4582, 33324, 261808, 2190688, 19318688, 178108704, 1705985883, 16891621166, 172188608886, 1801013405436, 19274897768196, 210573149141896, 2343553478425816, 26525044132374656, 304856947930144656 (list; graph; refs; listen; history; text; internal format)
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.

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

A047889(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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 19 13:01 EDT 2019. Contains 328222 sequences. (Running on oeis4.)