login
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.
13

%I #22 Oct 24 2018 16:06:38

%S 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,

%T 100,75,50,11,0,1,7,21,185,195,231,205,13,0,1,8,28,308,420,736,1414,

%U 292,19,0,1,9,36,476,798,1876,6032,2376,587,27,0

%N 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.

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

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

%C [1] [2] [0]

%C [1] [0] [2]

%C 2ab, 2aa, 2bb.

%H Alois P. Heinz, <a href="/A261835/b261835.txt">Antidiagonals n = 0..140, flattened</a>

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

%e A(3,2) = 16: 3aaa, 3aab, 3abb, 3bbb, 2aa1a, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 2bb1b, 1a2aa, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1b2bb.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 2, 3, 4, 5, 6, 7, ...

%e 0, 1, 3, 6, 10, 15, 21, 28, ...

%e 0, 3, 16, 46, 100, 185, 308, 476, ...

%e 0, 3, 21, 75, 195, 420, 798, 1386, ...

%e 0, 5, 50, 231, 736, 1876, 4116, 8106, ...

%e 0, 11, 205, 1414, 6032, 19320, 51114, 117936, ...

%e 0, 13, 292, 2376, 11712, 42610, 126288, 322764, ...

%p b:= proc(n, i, p, k) option remember;

%p `if`(i*(i+1)/2<n, 0, `if`(n=0, p!, b(n, i-1, p, k)+

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

%p end:

%p A:= (n, k)-> b(n$2, 0, k):

%p seq(seq(A(n, d-n), n=0..d), d=0..12);

%t 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 *)

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

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

%Y Main diagonal gives A261837.

%Y Cf. A261780, A261836.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Sep 02 2015