login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 14
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 (list; table; graph; refs; listen; history; text; internal format)
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).

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: A265609 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 18 04:48 EST 2020. Contains 332011 sequences. (Running on oeis4.)