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

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.

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

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

Example

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

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

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.

Sequence in context: A362125 A261718 A144074 * A124540 A124550 A306024

Adjacent sequences: A261777 A261778 A261779 * A261781 A261782 A261783

Keyword

nonn,tabl

Author

Alois P. Heinz, Aug 31 2015

Status

approved