Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #59 Mar 23 2020 21:23:19
%S 1,1,2,6,24,119,694,4582,33324,261808,2190688,19318688,178108704,
%T 1705985883,16891621166,172188608886,1801013405436,19274897768196,
%U 210573149141896,2343553478425816,26525044132374656,304856947930144656
%N Number of permutations in S_n with longest increasing subsequence of length <= 4.
%C Or, number of permutations in S_n that avoid the pattern 12345, - _N. J. A. Sloane_, Mar 19 2015
%C 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 Gheorghe Coserea, <a href="/A047889/b047889.txt">Table of n, a(n) for n = 0..300</a>
%H 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 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 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 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 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 <a href="/index/Y#Young">Index entries for sequences related to Young tableaux.</a>
%F 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 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 a(n) ~ 3 * 2^(4*n + 9) / (n^(15/2) * Pi^(3/2)). - _Vaclav Kotesovec_, Sep 10 2014
%e G.f. = 1 + x + 2*x^2 + 6*x^3 + 24*x^4 + 119*x^5 + 694*x^6 + 4582*x^7 + ...
%p 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 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 (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 A column of A047888.
%Y Cf. A005802, A047890, A052399.
%Y Column k=4 of A214015.
%Y 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 nonn,easy
%O 0,3
%A Eric Rains (rains(AT)caltech.edu), _N. J. A. Sloane_
%E More terms from _Naohiro Nomoto_, Mar 01 2002
%E Edited by _N. J. A. Sloane_, Aug 23 2008 at the suggestion of _R. J. Mathar_