VOOZH about

URL: https://oeis.org/A047889

⇱ A047889 - OEIS

login
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
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
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.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes Moment Sequences for Pattern-Avoiding Permutations, Electron. J. Combin., Vol. 27, No. 4 (2020), p. 25.
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.
Permutation Pattern Avoidance Library (PermPAL), 12345
Nathaniel Shar, Experimental methods in permutation patterns and bijective proof, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
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.
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
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