login
Number of permutations in S_n with longest increasing subsequence of length <= 6.
9

%I #51 Mar 23 2020 21:23:32

%S 1,1,2,6,24,120,720,5039,40270,361302,3587916,38957991,457647966,

%T 5763075506,77182248916,1091842643475,16219884281650,251774983140578,

%U 4066273930979460,68077194367392864,1177729684507324152,20995515989327134152,384762410996641402384

%N Number of permutations in S_n with longest increasing subsequence of length <= 6.

%C Previous name was: Related to Young tableaux of bounded height.

%H Alois P. Heinz, <a href="/A052399/b052399.txt">Table of n, a(n) for n = 0..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 [math.CO], 2015.

%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) ~ 5 * 2^(2*n + 6) * 3^(2*n + 21) / (n^(35/2) * Pi^(5/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) option remember;

%p `if`(n=0, h(l)^2, `if`(i<1, 0, `if`(i=1, h([l[], 1$n])^2,

%p g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i, [l[], i])))))

%p end:

%p a:= n-> g(n, 6, []):

%p seq(a(n), n=0..25); # _Alois P. Heinz_, Apr 10 2012

%p # second Maple program

%p a:= proc(n) option remember; `if`(n<7, n!,

%p ((56*n^5-9408+11032*n+19028*n^2+7360*n^3+1092*n^4)*a(n-1)

%p -4*(196*n^3+1608*n^2+3167*n+444)*(n-1)^2*a(n-2)

%p +1152*(2*n+3)*(n-1)^2*(n-2)^2*a(n-3))/ ((n+9)*(n+8)^2*(n+5)^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, 6], {n, 0, 30}] (* _Jean-François Alcover_, Mar 11 2014, after _Alois P. Heinz_ *)

%Y Cf. A005802, A047889, A047890.

%Y Column k=6 of A214015.

%K nonn

%O 0,3

%A _N. J. A. Sloane_, Mar 13 2000

%E More terms from _Alois P. Heinz_, Apr 10 2012

%E New name from _Vaclav Kotesovec_, Sep 10 2014