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,8

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.

Links

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

Formula

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

Example

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

Maple

b:= proc(n, i, p, k) option remember;
      `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))))
    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 *)

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.

Sequence in context: A384865 A384580 A392378 * A384866 A384581 A384582

Adjacent sequences: A261832 A261833 A261834 * A261836 A261837 A261838

Keyword

nonn,tabl

Author

Alois P. Heinz, Sep 02 2015

Status

approved