A179647 Rectangular array read by antidiagonals: T(n,k) is the number of compositions (ordered partitions) of n in which no part (summand) is equal to k.

0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 2, 3, 4, 3, 1, 2, 4, 6, 7, 5, 1, 2, 4, 7, 11, 12, 8, 1, 2, 4, 8, 14, 21, 21, 13, 1, 2, 4, 8, 15, 27, 39, 37, 21, 1, 2, 4, 8, 16, 30, 52, 73, 65, 34, 1, 2, 4, 8, 16, 31, 59, 101, 136, 114, 55, 1, 2, 4, 8, 16, 32, 62, 116, 195, 254, 200, 89

Offset

1,8

Links

Alois P. Heinz, Antidiagonals n = 1..141, flattened

Formula

O.g.f. for column k: B(A(x)) where A(x) = x/(1-x)-x^k and B(x) = 1/(1-x).

Example

T(4,2) = 4 because there are four compositions of 4 with no part equal to two: 4, 3+1, 1+3, 1+1+1+1.
Array starts as:
  0,    1,   1,   1,   1,   1,   1,   1,   1,   1, ...
  1,    1,   2,   2,   2,   2,   2,   2,   2,   2, ...
  1,    2,   3,   4,   4,   4,   4,   4,   4,   4, ...
  2,    4,   6,   7,   8,   8,   8,   8,   8,   8, ...
  3,    7,  11,  14,  15,  16,  16,  16,  16,  16, ...
  5,   12,  21,  27,  30,  31,  32,  32,  32,  32, ...
  8,   21,  39,  52,  59,  62,  63,  64,  64,  64, ...
  13,  37,  73, 101, 116, 123, 126, 127, 128, 128, ...
  21,  65, 136, 195, 228, 244, 251, 254, 255, 256, ...
  34, 114, 254, 377, 449, 484, 500, 507, 510, 511, ...

Maple

T:= proc(n, k) option remember;
      `if`(n=0, 1, add(`if`(j=k, 0, T(n-j, k)), j=1..n))
    end:
seq(seq(T(n, d+1-n), n=1..d), d=1..12);  # Alois P. Heinz, Oct 23 2011

Mathematica

Transpose[Table[Table[Length[Select[Level[Map[Permutations, IntegerPartitions[n]], {2}], FreeQ[#, i] &]], {n, 1, 10}], {i, 1, 10}]] // Grid
(* second program: *)
a = x/(1 - x) - x^n; Transpose[Table[Rest[CoefficientList[Series[1/(1 - a), {x, 0, 10}], x]], {n, 1, 10}]] // Grid
(* Program translated from Maple: *)
T[n_, k_] := T[n, k] = If[n==0, 1, Sum[If[j==k, 0, T[n-j, k]], {j, 1, n}]];
Table[Table[T[n, d+1-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Jun 06 2021, after Alois P. Heinz *)

Crossrefs

Sequence in context: A261904 A297030 A266348 * A029330 A132225 A263923

Adjacent sequences: A179644 A179645 A179646 * A179648 A179649 A179650

Keyword

nonn,tabl

Author

Geoffrey Critzer, Jan 09 2011

Extensions

Corrected and extended by Alois P. Heinz, Oct 23 2011

Status

approved