|
|
A268485
|
|
Number of sequences with n copies each of 1,2,...,n and longest increasing subsequence of length n.
|
|
4
|
|
|
1, 1, 5, 1306, 46922017, 449363984934526, 1878320344216429026862153, 5078529731893937404909347067888886466, 12324197596430667064913735085330208112438377122058241, 35544813569338447788721757701614208334438136486811525386710064098254294
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905
|
|
EXAMPLE
|
a(2) = 5: 1122, 1212, 1221, 2112, 2121.
a(3) = 1306: 111222333, 111223233, 111223323, ..., 332212113, 332212131, 332212311.
|
|
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([n$n]):
seq(a(n), n=0..8);
# second Maple program:
b:= proc(k, p, j, l, t) option remember;
`if`(k=0, (-1)^t/l!, `if`(p<0, 0, add(b(k-i, p-1,
j+1, l+i*j, irem(t+i*j, 2))/(i!*p!^i), i=0..k)))
end:
a:= n-> n!*(n^2)!*b(n, n-1, 1, 0, irem(n, 2)):
|
|
MATHEMATICA
|
b[k_, p_, j_, l_, t_] := b[k, p, j, l, t] = If[k==0, (-1)^t/l!, If[p<0, 0, Sum[b[k-i, p-1, j+1, l+i*j, Mod[t + i*j, 2]]/(i!*p!^i), {i, 0, k}]]];
a[n_] := n!*(n^2)!*b[n, n - 1, 1, 0, Mod[n, 2]];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|