|
| |
|
|
A268700
|
|
Total number of sequences with p_j copies of j and longest increasing subsequence of length k summed over all partitions [p_1, p_2, ..., p_k] of n into distinct parts.
|
|
4
|
|
|
|
1, 1, 1, 3, 4, 14, 46, 111, 330, 1614, 7348, 21340, 98145, 379405, 2633085, 14871033, 57284558, 278927415, 1609313975, 8289565670, 74945364815, 522977754235, 2403799401259, 14180489136597, 83964652635668, 623008803758260, 3918144764978718, 46950727351392315
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
LINKS
|
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905
|
|
|
EXAMPLE
|
The partitions of 4 into distinct parts are [3,1], [4] giving the a(4) = 4 sequences: 1112, 1121, 1211, 1111.
|
|
|
MAPLE
|
g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]
-1, l))), j=1..nops(l)-1))(add(i, i=l))
end:
f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(
n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):
h:= (n, i, l)-> `if`(n>i*(i+1)/2, 0, `if`(n=0, f(l), h(n, i-1, l)
+`if`(i>n, 0, h(n-i, i-1, [i, l[]])))):
a:= n-> h(n$2, []):
seq(a(n), n=0..30);
|
|
|
MATHEMATICA
|
g[l_] := g[l] = Function[n, f[Most[l]]*Binomial[n-1, l[[-1]]-1] + Sum[f[ Sort[ReplacePart[l, j -> l[[j]]-1]]], {j, 1, Length[l]-1}]][Total[l]]; f[l_] := Function[n, If[n<2 || l[[-1]]==1, 1, If[l[[1]]==0, 0, If[n==2, Binomial[l[[1]]+l[[2]], l[[1]]]-1, g[l]]]]][Length[l]]; h[n_, i_, l_] := If[n>i*(i+1)/2, 0, If[n==0, f[l], h[n, i-1, l] + If[i>n, 0, h[n-i, i-1, Join[{i}, l]]]]]; a[n_] := h[n, n, {}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Feb 11 2017, translated from Maple *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
