A261780 Number A(n,k) of compositions of n 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, 2, 0, 1, 3, 7, 4, 0, 1, 4, 15, 24, 8, 0, 1, 5, 26, 73, 82, 16, 0, 1, 6, 40, 164, 354, 280, 32, 0, 1, 7, 57, 310, 1031, 1716, 956, 64, 0, 1, 8, 77, 524, 2395, 6480, 8318, 3264, 128, 0, 1, 9, 100, 819, 4803, 18501, 40728, 40320, 11144, 256, 0

Offset: 0

Author

Alois P. Heinz, Aug 31 2015

Keywords

• nonn
• tabl

Comments

Also the number of k-compositions of n: matrices with k rows of nonnegative integers with positive column sums and total element sum n.

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

[1 1] [0 0] [1 0] [0 1] [1] [2] [0]

[0 0] [1 1] [0 1] [1 0] [1] [0] [2]

1a1a, 1b1b, 1a1b, 1b1a, 2ab, 2aa, 2bb.

Examples

			A(3,2) = 24: 3aaa, 3aab, 3abb, 3bbb, 2aa1a, 2aa1b, 2ab1a, 2ab1b, 2bb1a, 2bb1b, 1a2aa, 1a2ab, 1a2bb, 1b2aa, 1b2ab, 1b2bb, 1a1a1a, 1a1a1b, 1a1b1a, 1a1b1b, 1b1a1a, 1b1a1b, 1b1b1a, 1b1b1b.
Square array A(n,k) begins:
  1,  1,   1,    1,     1,      1,      1, ...
  0,  1,   2,    3,     4,      5,      6, ...
  0,  2,   7,   15,    26,     40,     57, ...
  0,  4,  24,   73,   164,    310,    524, ...
  0,  8,  82,  354,  1031,   2395,   4803, ...
  0, 16, 280, 1716,  6480,  18501,  44022, ...
  0, 32, 956, 8318, 40728, 142920, 403495, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• E. Grazzini, E. Munarini, M. Poneti, S. Rinaldi, m-compositions and m-partitions: exhaustive generation and Gray code, Pure Math. Appl. 17 (2006), 111-121.
• G. Louchard, Matrix Compositions: a Probabilistic analysis, Proc. GASCOM'08, Pure Mathematics and Applications, 19, 2-3, 127-146, 2008.
• E. Munarini, M. Poneti, S. Rinaldi, Matrix compositions, Journal of Integer Sequences, Vol. 12 (2009), Article 09.4.8

Crossrefs

Columns k=0-10 give: A000007, A011782, A003480, A145839, A145840, A145841, A161434, A261799, A261800, A261801, A261802.

Rows n=0-2 give: A000012, A001477, A005449.

Main diagonal gives A261783.

Cf. A261718 (same for partitions), A261781.

Programs

Maple

A:= proc(n, k) option remember; `if`(n=0, 1,
      add(A(n-j, k)*binomial(j+k-1, k-1), j=1..n))
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

a[n_, k_] := SeriesCoefficient[(1-x)^k/(2*(1-x)^k-1), {x, 0, n}]; Table[ a[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Feb 07 2017 *)

Formula

G.f. of column k: (1-x)^k/(2*(1-x)^k-1).

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

A(n,k) = Sum_{j>=0} (1/2)^(j+1) * binomial(n-1+k*j,n). - Seiichi Manyama, Aug 06 2024