|
|
A052399
|
|
Number of permutations in S_n with longest increasing subsequence of length <= 6.
|
|
9
|
|
|
1, 1, 2, 6, 24, 120, 720, 5039, 40270, 361302, 3587916, 38957991, 457647966, 5763075506, 77182248916, 1091842643475, 16219884281650, 251774983140578, 4066273930979460, 68077194367392864, 1177729684507324152, 20995515989327134152, 384762410996641402384
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
COMMENTS
|
Previous name was: Related to Young tableaux of bounded height.
|
|
LINKS
|
|
|
FORMULA
|
a(n) ~ 5 * 2^(2*n + 6) * 3^(2*n + 21) / (n^(35/2) * Pi^(5/2)). - Vaclav Kotesovec, Sep 10 2014
|
|
MAPLE
|
h:= proc(l) local n; n:=nops(l); add(i, i=l)! /mul(mul(1+l[i]-j
+add(`if`(l[k]>=j, 1, 0), k=i+1..n), j=1..l[i]), i=1..n)
end:
g:= proc(n, i, l) option remember;
`if`(n=0, h(l)^2, `if`(i<1, 0, `if`(i=1, h([l[], 1$n])^2,
g(n, i-1, l)+ `if`(i>n, 0, g(n-i, i, [l[], i])))))
end:
a:= n-> g(n, 6, []):
# second Maple program
a:= proc(n) option remember; `if`(n<7, n!,
((56*n^5-9408+11032*n+19028*n^2+7360*n^3+1092*n^4)*a(n-1)
-4*(196*n^3+1608*n^2+3167*n+444)*(n-1)^2*a(n-2)
+1152*(2*n+3)*(n-1)^2*(n-2)^2*a(n-3))/ ((n+9)*(n+8)^2*(n+5)^2))
end:
|
|
MATHEMATICA
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|