login
Number T(n,k) of compositions of n into distinct parts with exactly k descents; triangle T(n,k), n>=0, 0<=k<=max(floor((sqrt(1+8*n)-3)/2),0), read by rows.
12

%I #22 Oct 30 2014 22:39:36

%S 1,1,1,2,1,2,1,3,2,4,6,1,5,7,1,6,11,2,8,16,3,10,31,15,1,12,36,16,1,15,

%T 55,29,2,18,71,41,3,22,101,65,5,27,147,144,32,1,32,188,179,35,1,38,

%U 245,269,63,2,46,327,382,93,3,54,421,549,148,5,64,540,739,205,7

%N Number T(n,k) of compositions of n into distinct parts with exactly k descents; triangle T(n,k), n>=0, 0<=k<=max(floor((sqrt(1+8*n)-3)/2),0), read by rows.

%H Alois P. Heinz, <a href="/A241719/b241719.txt">Rows n = 0..500, flattened</a>

%e T(6,0) = 4: [6], [2,4], [1,5], [1,2,3].

%e T(6,1) = 6: [5,1], [4,2], [3,1,2], [1,3,2], [2,1,3], [2,3,1].

%e T(6,2) = 1: [3,2,1].

%e T(7,0) = 5: [7], [3,4], [2,5], [1,6], [1,2,4].

%e T(7,1) = 7: [6,1], [4,3], [5,2], [2,1,4], [1,4,2], [2,4,1], [4,1,2].

%e T(7,2) = 1: [4,2,1].

%e Triangle T(n,k) begins:

%e 00: 1;

%e 01: 1;

%e 02: 1;

%e 03: 2, 1;

%e 04: 2, 1;

%e 05: 3, 2;

%e 06: 4, 6, 1;

%e 07: 5, 7, 1;

%e 08: 6, 11, 2;

%e 09: 8, 16, 3;

%e 10: 10, 31, 15, 1;

%e 11: 12, 36, 16, 1;

%e 12: 15, 55, 29, 2;

%e 13: 18, 71, 41, 3;

%e 14: 22, 101, 65, 5;

%e 15: 27, 147, 144, 32, 1;

%p g:= proc(u, o) option remember; `if`(u+o=0, 1, expand(

%p add(g(u+j-1, o-j) , j=1..o)+

%p add(g(u-j, o+j-1)*x, j=1..u)))

%p end:

%p b:= proc(n, i) option remember; local m; m:= i*(i+1)/2;

%p `if`(n>m, 0, `if`(n=m, x^i,

%p expand(b(n, i-1) +`if`(i>n, 0, x*b(n-i, i-1)))))

%p end:

%p T:= n-> (p-> (q-> seq(coeff(q, x, i), i=0..degree(q)))(add(

%p coeff(p, x, k)*g(0, k), k=0..degree(p))))(b(n$2)):

%p seq(T(n), n=0..20);

%t g[u_, o_] := g[u, o] = If[u+o == 0, 1, Expand[Sum[g[u+j-1, o-j], {j, 1, o}] + Sum[g[u-j, o+j-1]*x, {j, 1, u}]]]; b[n_, i_] := b[n, i] = Module[{m}, m = i*(i+1)/2; If[n>m, 0, If[n == m, x^i, Expand[b[n, i-1] + If[i>n, 0, x*b[n-i, i-1]]]]]]; T[n_] := Function [p, Function[q, Table[Coefficient[q, x, i], {i, 0, Exponent[q, x]}]][Sum[Coefficient[p, x, k]*g[0, k], {k, 0, Exponent[p, x]}]]][b[n, n]]; Table[T[n], {n, 0, 20}] // Flatten (* _Jean-François Alcover_, Apr 28 2014, after _Alois P. Heinz_ *)

%Y Columns k=0-10 give: A000009, A241720, A241721, A241722, A241723, A241724, A241725, A241726, A241727, A241728, A241729.

%Y Row sums give A032020.

%Y T(A000217(k+1)-1,k-1) = A000041(k) for k>0.

%Y Cf. A052146.

%K nonn,tabf,look

%O 0,4

%A _Alois P. Heinz_, Apr 27 2014