|
%I #10 Jul 12 2021 04:16:03
%S 1,1,1,5,7,27,195,421,1619,8675,105757,274029,1402193,6625987,
%T 55349787,975068069,3137395939,17960895375,101880880461,696011551909,
%U 7596647200175,197122787505191,723879298052695,4905597865756059,29537689035766501,227793692735075911
%N Total number of sequences with c_j copies of j and longest increasing subsequence of length k summed over all compositions [c_1, c_2, ..., c_k] of n into distinct parts.
%H Alois P. Heinz, <a href="/A268701/b268701.txt">Table of n, a(n) for n = 0..90</a>
%H J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. <a href="http://www.ams.org/mathscinet-getitem?mr=681905">MR 681905</a>
%e The compositions of 4 into distinct parts are [3,1], [1,3], [4] giving the a(4) = 7 sequences: 1112, 1121, 1211, 1222, 2122, 2212, 1111.
%p c:= l-> f(l)*nops(l)!/(v-> mul(coeff(v, x, j)!,
%p j=0..degree(v)))(add(x^i, i=l)):
%p g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
%p binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]
%p -1, l))), j=1..nops(l)-1))(add(i, i=l))
%p end:
%p f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(
%p n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):
%p h:= (n, i, l)-> `if`(n>i*(i+1)/2, 0, `if`(n=0, c(l), h(n, i-1, l)
%p +`if`(i>n, 0, h(n-i, i-1, [i, l[]])))):
%p a:= n-> h(n$2, []):
%p seq(a(n), n=0..30);
%t c[l_] := f[l]*Length[l]!/Function[v, Product[Coefficient[v, x, j]!,{j, 0, Exponent[v, x]}]][Sum[x^i, {i, l}]];
%t 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]];
%t 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]];
%t h[n_, i_, l_] := If[n > i (i + 1)/2, 0, If[n == 0, c[l], h[n, i - 1, l] + If[i > n, 0, h[n - i, i - 1, Join[{i}, l]]]]];
%t a[n_] := h[n, n, {}];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jul 12 2021, after _Alois P. Heinz_ *)
%Y Cf. A047909, A268698, A268699, A268700.
%K nonn
%O 0,4
%A _Alois P. Heinz_, Feb 11 2016
|
