A268701 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.

1, 1, 1, 5, 7, 27, 195, 421, 1619, 8675, 105757, 274029, 1402193, 6625987, 55349787, 975068069, 3137395939, 17960895375, 101880880461, 696011551909, 7596647200175, 197122787505191, 723879298052695, 4905597865756059, 29537689035766501, 227793692735075911

Offset

0,4

Links

Alois P. Heinz, Table of n, a(n) for n = 0..90

J. D. Horton and A. Kurn, Counting sequences with complete increasing subsequences, Congressus Numerantium, 33 (1981), 75-80. MR 681905

Example

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.

Maple

c:= l-> f(l)*nops(l)!/(v-> mul(coeff(v, x, j)!,
        j=0..degree(v)))(add(x^i, i=l)):
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, c(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

c[l_] := f[l]*Length[l]!/Function[v, Product[Coefficient[v, x, j]!, {j, 0, Exponent[v, x]}]][Sum[x^i, {i, l}]];
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, c[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, Jul 12 2021, after Alois P. Heinz *)

Crossrefs

Cf. A047909, A268698, A268699, A268700.

Sequence in context: A278646 A029668 A144392 * A317166 A126888 A358582

Adjacent sequences: A268698 A268699 A268700 * A268702 A268703 A268704

Keyword

nonn

Author

Alois P. Heinz, Feb 11 2016

Status

approved