A241701 Number T(n,k) of Carlitz compositions of n with exactly k descents; triangle T(n,k), n>=0, 0<=k<=floor(n/3), read by rows.

1, 1, 1, 2, 1, 2, 2, 3, 4, 4, 8, 2, 5, 13, 5, 6, 21, 12, 8, 33, 27, 3, 10, 50, 53, 11, 12, 73, 98, 31, 15, 106, 174, 78, 5, 18, 150, 296, 175, 22, 22, 209, 486, 363, 72, 27, 289, 781, 715, 204, 8, 32, 393, 1222, 1342, 510, 43, 38, 529, 1874, 2421, 1168, 159

Offset

0,4

Comments

No two adjacent parts of a Carlitz composition are equal.

Links

Alois P. Heinz, Rows n = 0..250, flattened

Formula

Sum_{k=0..floor(n/3)} (k+1) * T(n,k) = A285994(n) (for n>0).

Example

T(6,0) = 4: [6], [1,5], [2,4], [1,2,3].
T(6,1) = 8: [4,2], [5,1], [3,1,2], [1,3,2], [1,4,1], [2,3,1], [2,1,3], [1,2,1,2].
T(6,2) = 2: [3,2,1], [2,1,2,1].
T(7,0) = 5: [7], [3,4], [1,6], [2,5], [1,2,4].
T(7,1) = 13: [4,3], [6,1], [5,2], [2,1,4], [4,1,2], [1,4,2], [2,3,2], [3,1,3], [1,5,1], [2,4,1], [1,2,3,1], [1,3,1,2], [1,2,1,3].
T(7,2) = 5: [4,2,1], [2,1,3,1], [3,1,2,1], [1,3,2,1], [1,2,1,2,1].
Triangle T(n,k) begins:
00:   1;
01:   1;
02:   1;
03:   2,   1;
04:   2,   2;
05:   3,   4;
06:   4,   8,   2;
07:   5,  13,   5;
08:   6,  21,  12;
09:   8,  33,  27,   3;
10:  10,  50,  53,  11;
11:  12,  73,  98,  31;
12:  15, 106, 174,  78,   5;
13:  18, 150, 296, 175,  22;
14:  22, 209, 486, 363,  72;
15:  27, 289, 781, 715, 204, 8;

Maple

b:= proc(n, i) option remember; `if`(n=0, 1, expand(
      add(`if`(j=i, 0, b(n-j, j)*`if`(j<i, x, 1)), j=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0)):
seq(T(n), n=0..20);

Mathematica

b[n_, i_] := b[n, i] = If[n == 0, 1, Expand[Sum[If[j == i, 0, b[n-j, j]*If[j<i, x, 1]], {j, 1, n}]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0]]; Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Feb 13 2015, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000009, A241691, A241692, A241693, A241694, A241695, A241696, A241697, A241698, A241699, A241700.

Row sums give A003242.

T(3n,n) = A000045(n+1).

T(3n+1,n) = A129715(n) for n>0.

Cf. A238344, A285994.

Sequence in context: A244788 A078660 A239239 * A347662 A060177 A347788

Adjacent sequences: A241698 A241699 A241700 * A241702 A241703 A241704

Keyword

nonn,tabf

Author

Alois P. Heinz, Apr 27 2014

Status

approved