%I #57 Mar 23 2020 21:23:26
%S 1,2,6,24,120,719,5003,39429,344837,3291590,33835114,370531683,
%T 4285711539,51990339068,657723056000,8636422912277,117241501095189,
%U 1639974912709122,23570308719710838,347217077020664880,5231433025400049936,80466744544235325387
%N Number of permutations in S_n with longest increasing subsequence of length <= 5.
%H Alois P. Heinz, <a href="/A047890/b047890.txt">Table of n, a(n) for n = 1..250</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, 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 Ser. A 53 (1990), no. 2, 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(n) ~ 9 * 5^(2*n + 25/2) / (512 * n^12 * Pi^2). - _Vaclav Kotesovec_, Sep 10 2014
%p h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
%p +add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
%p end:
%p g:= proc(n, i, l)
%p `if`(n=0 or i=1, h([l[], 1$n])^2, `if`(i<1, 0,
%p add(g(n-i*j, i-1, [l[], i$j]), j=0..n/i)))
%p end:
%p a:= n-> g(n, 5, []):
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Apr 10 2012
%p # second Maple program
%p a:= proc(n) option remember; `if`(n<6, n!, ((-375+400*n+843*n^2
%p +322*n^3+35*n^4)*a(n-1) +225*(n-1)^2*(n-2)^2*a(n-3)
%p -(259*n^2+622*n+45)*(n-1)^2*a(n-2))/ ((n+6)^2*(n+4)^2))
%p end:
%p seq(a(n), n=1..30); # _Alois P. Heinz_, Sep 26 2012
%t h[l_] := With[{n = Length[l]}, Sum[i, {i, l}]!/Product[Product[1+l[[i]]-j+Sum[If[l[[k]] >= j, 1, 0], {k, i+1, n}], {j, 1, l[[i]]}], {i, 1, n}]]; g[n_, i_, l_] := If[n == 0 || i == 1, h[Join[l, Array[1&, n]]]^2, If[i<1, 0, Sum[g[n-i*j, i-1, Join[l, Array[i&, j]]], {j, 0, n/i}]]]; a[n_, k_] := If[k >= n, n!, g[n, k, {}]]; Table[a[n, 5], {n, 1, 30}] (* _Jean-François Alcover_, Mar 10 2014, after _Alois P. Heinz_ *)
%Y A column of A047888. Cf. A005802, A052399.
%Y Column k=5 of A214015.
%K nonn,easy
%O 1,2
%A Eric Rains (rains(AT)caltech.edu), _N. J. A. Sloane_
%E More terms from _Naohiro Nomoto_, Mar 01 2002
%E More terms from _Alois P. Heinz_, Apr 10 2012
|