A047890 - OEIS

%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