A243081 Number A(n,k) of compositions of n into parts with multiplicity not larger than k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 2, 3, 0, 1, 1, 2, 3, 3, 0, 1, 1, 2, 4, 7, 5, 0, 1, 1, 2, 4, 7, 11, 11, 0, 1, 1, 2, 4, 8, 15, 21, 13, 0, 1, 1, 2, 4, 8, 15, 26, 34, 19, 0, 1, 1, 2, 4, 8, 16, 31, 52, 59, 27, 0, 1, 1, 2, 4, 8, 16, 31, 57, 93, 114, 57, 0, 1, 1, 2, 4, 8, 16, 32, 63, 114, 173, 178, 65, 0

Offset: 0

Author

Alois P. Heinz, May 29 2014

Keywords

• nonn
• tabl

Comments

A(n,k) is the number of compositions of n avoiding the pattern {1}^(k+1).

Examples

			Square array A(n,k) begins:
  1,  1,  1,  1,   1,   1,   1,   1,   1, ...
  0,  1,  1,  1,   1,   1,   1,   1,   1, ...
  0,  1,  2,  2,   2,   2,   2,   2,   2, ...
  0,  3,  3,  4,   4,   4,   4,   4,   4, ...
  0,  3,  7,  7,   8,   8,   8,   8,   8, ...
  0,  5, 11, 15,  15,  16,  16,  16,  16, ...
  0, 11, 21, 26,  31,  31,  32,  32,  32, ...
  0, 13, 34, 52,  57,  63,  63,  64,  64, ...
  0, 19, 59, 93, 114, 120, 127, 127, 128, ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-10 give: A000007, A032020, A232432, A232464, A243082, A243083, A243084, A243085, A243086, A243087, A243088.

Main diagonal gives A011782.

A(2n,n) gives A232605.

Programs

Maple

b:= proc(n, i, p, k) option remember; `if`(n=0, p!, `if`(i<1, 0,
      add(b(n-i*j, i-1, p+j, k)/j!, j=0..min(n/i, k))))
    end:
A:= (n, k)-> `if`(k>=n, `if`(n=0, 1, 2^(n-1)), b(n$2, 0, k)):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

b[n_, i_, p_, k_] := b[n, i, p, k] = If[n == 0, p!, If[i<1, 0,
     Sum[b[n-i*j, i-1, p+j, k]/j!, {j, 0, Min[n/i, k]}]]];
A[n_, k_] := If[k >= n, If[n == 0, 1, 2^(n-1)], b[n, n, 0, k]];
Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Feb 02 2015, after Alois P. Heinz *)

Formula

A(n,k) = Sum_{i=0..k} A242447(n,i).