A261835 Number A(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; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 3, 0, 1, 4, 6, 16, 3, 0, 1, 5, 10, 46, 21, 5, 0, 1, 6, 15, 100, 75, 50, 11, 0, 1, 7, 21, 185, 195, 231, 205, 13, 0, 1, 8, 28, 308, 420, 736, 1414, 292, 19, 0, 1, 9, 36, 476, 798, 1876, 6032, 2376, 587, 27, 0

Offset: 0

Author

Alois P. Heinz, Sep 02 2015

Keywords

• nonn
• tabl

Comments

Also matrices with k rows of nonnegative integers with distinct positive column sums and total element sum n.

A(2,2) = 3: (matrices and corresponding marked compositions are given)

[1] [2] [0]

[1] [0] [2]

2ab, 2aa, 2bb.

Examples

			A(3,2) = 16: 3aaa, 3aab, 3abb, 3bbb, 2aa1a, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 2bb1b, 1a2aa, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1b2bb.
Square array A(n,k) begins:
  1,  1,   1,    1,     1,     1,      1,      1, ...
  0,  1,   2,    3,     4,     5,      6,      7, ...
  0,  1,   3,    6,    10,    15,     21,     28, ...
  0,  3,  16,   46,   100,   185,    308,    476, ...
  0,  3,  21,   75,   195,   420,    798,   1386, ...
  0,  5,  50,  231,   736,  1876,   4116,   8106, ...
  0, 11, 205, 1414,  6032, 19320,  51114, 117936, ...
  0, 13, 292, 2376, 11712, 42610, 126288, 322764, ...
		

Links

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

Crossrefs

Columns k=0-10 give: A000007, A032020, A261840, A261841, A261842, A261843, A261844, A261845, A261846, A261847, A261848.

Rows n=0-4 give: A000012, A001477, A000217, A255211, A228317(n+2).

Main diagonal gives A261837.

Cf. A261780, A261836.

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:
A:= (n, k)-> b(n$2, 0, k):
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2 < n, 0, If[n == 0, p!, b[n, i-1, p, k] + If[i>n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; A[n_, k_] := b[n, n, 0, k]; Table[A[n, d-n], {d, 0, 12}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jan 16 2017, translated from Maple *)

Formula

A(n,k) = Sum_{i=0..k} C(k,i) * A261836(n,k-i).