A261836 Number T(n,k) of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order and all k letters occur at least once in the composition; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 1, 1, 0, 3, 10, 7, 0, 3, 15, 21, 9, 0, 5, 40, 96, 92, 31, 0, 11, 183, 832, 1562, 1305, 403, 0, 13, 266, 1539, 3908, 4955, 3090, 757, 0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873, 0, 27, 1056, 10902, 50208, 124450, 178456, 148638, 66904, 12607

Offset: 0

Author

Alois P. Heinz, Sep 02 2015

Keywords

• nonn
• tabl

Comments

Also number of matrices with k rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.

Examples

			T(3,2) = 10: (matrices and corresponding marked compositions are given)
  [2]   [1]   [2 0]  [0 2]  [1 0]  [0 1]  [1 1]  [1 1]  [1 0]  [0 1]
  [1]   [2]   [0 1]  [1 0]  [0 2]  [2 0]  [1 0]  [0 1]  [1 1]  [1 1]
  3aab, 3abb, 2aa1b, 1b2aa, 1a2bb, 2bb1a, 2ab1a, 1a2ab, 2ab1b, 1b2ab.
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  3,  10,    7;
  0,  3,  15,   21,     9;
  0,  5,  40,   96,    92,    31;
  0, 11, 183,  832,  1562,  1305,   403;
  0, 13, 266, 1539,  3908,  4955,  3090,   757;
  0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873;
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A000007, A032020 (for n>0), A261853, A261854, A261855, A261856, A261857, A261858, A261859, A261860, A261861.

Main diagonal gives A032011.

Row sums give A261838.

T(2n,n) gives A261828.

Cf. A261781, A261835.

Programs

Maple

b:= proc(n, i, p, k) option remember;
      `if`(i*(i+1)/2n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
    end:
T:= (n, k)-> add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; T[n_, k_] := Sum[b[n, n, 0, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]; Table[ Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz *)

Formula

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A261835(n,k-i).