login
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
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)):
seq(a(n), n=0..10); # Alois P. Heinz, Mar 03 2016
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]];
Table[a[n], {n, 0, 10}] (* Jean-François Alcover, Jun 18 2018, translated from 2nd Maple program *)
CROSSREFS
Main diagonal of A047909.
Sequence in context: A234811 A069642 A182345 * A066162 A096725 A332536
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Feb 05 2016
STATUS
approved