login
A268667
Number of sequences with j copies of j for each j in {1,2,...,n} and longest increasing subsequence of length n.
2
1, 1, 2, 26, 3511, 6742796, 233249911607, 175703195017370516, 3377940832101159287907151, 1899957346851645870857879683505890, 35246706696124014829643459097288501560957174, 23998872279553738609365779286317516184675391844037227392
OFFSET
0,3
COMMENTS
Sequences counted by a(n) have length A000217(n) and element sum A000330(n).
LINKS
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905
EXAMPLE
a(2) = 2: 122, 212.
a(3) = 26: 122333, 123233, 123323, 123332, 132233, 132323, 132332, 133223, 133232, 212333, 213233, 213323, 231233, 231323, 233123, 312233, 312323, 312332, 313223, 313232, 321233, 321323, 323123, 331223, 331232, 332123.
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)):
a:= n-> f([$1..n]):
seq(a(n), n=0..8);
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]];
a[n_] := f[Range[n]];
Table[a[n], {n, 0, 11}] (* Jean-François Alcover, Feb 27 2017, after Alois P. Heinz *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Feb 10 2016
STATUS
approved