cp's OEIS Frontend

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

%I A268699 #9 Sep 06 2022 06:02:14
%S A268699 1,1,2,6,22,95,471,2618,16052,107313,775045,6002106,49536510,
%T A268699 433485429,4004680967,38912323570,396393445096,4221367056961,
%U A268699 46878865762185,541660919690866,6498811587848690,80818650742133717,1040037672241415947,13829246515918840106
%N A268699 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.
%H A268699 Alois P. Heinz, <a href="/A268699/b268699.txt">Table of n, a(n) for n = 0..60</a>
%H A268699 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 A268699 The compositions of 4 are [1,1,1,1], [2,1,1], [1,2,1], [1,1,2], [2,2], [3,1], [1,3], [4] giving the a(4) = 22 sequences: 1234, 1123, 1213, 1231, 1223, 2123, 1232, 1233, 1323, 3123, 1122, 1212, 1221, 2112, 2121, 1112, 1121, 1211, 1222, 2122, 2212, 1111.
%p A268699 c:= l-> f(l)*nops(l)!/(v-> mul(coeff(v, x, j)!,
%p A268699         j=0..degree(v)))(add(x^i, i=l)):
%p A268699 g:= proc(l) option remember; (n-> f(l[1..nops(l)-1])*
%p A268699       binomial(n-1, l[-1]-1)+ add(f(sort(subsop(j=l[j]
%p A268699       -1, l))), j=1..nops(l)-1))(add(i, i=l))
%p A268699     end:
%p A268699 f:= l-> (n-> `if`(n<2 or l[-1]=1, 1, `if`(l[1]=0, 0, `if`(
%p A268699          n=2, binomial(l[1]+l[2], l[1])-1, g(l)))))(nops(l)):
%p A268699 h:= (n, i, l)-> `if`(n=0 or i=1, c([1$n, l[]]), h(n, i-1, l)+
%p A268699                 `if`(i>n, 0, h(n-i, i, [i, l[]]))):
%p A268699 a:= n-> h(n$2, []):
%p A268699 seq(a(n), n=0..25);
%t A268699 c[l_] := f[l]*Length[l]!/Function[v, Product[Coefficient[v, x, j]!, {j, 0, Exponent[v, x]}]][Sum[x^i, {i, l}]];
%t A268699 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 A268699 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 A268699 h[n_, i_, l_] := If[n == 0 || i == 1, c[Join[Array[1&, n], l]], h[n, i-1, l] + If[i > n, 0, h[n-i, i, Join[{i}, l]]]];
%t A268699 a[n_] := h[n, n, {}];
%t A268699 Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Sep 06 2022, after _Alois P. Heinz_ *)
%Y A268699 Cf. A047909, A268698, A268700, A268701.
%K A268699 nonn
%O A268699 0,3
%A A268699 _Alois P. Heinz_, Feb 11 2016