A183568 Triangle T(n,k), n>=0, 0<=k<=n, read by rows: T(n,k) is the number of partitions of n containing a clique of size k.

1, 1, 1, 2, 1, 1, 3, 2, 0, 1, 5, 3, 2, 0, 1, 7, 6, 2, 1, 0, 1, 11, 7, 3, 2, 1, 0, 1, 15, 13, 5, 3, 1, 1, 0, 1, 22, 16, 9, 3, 3, 1, 1, 0, 1, 30, 25, 10, 6, 3, 2, 1, 1, 0, 1, 42, 33, 16, 8, 5, 3, 2, 1, 1, 0, 1, 56, 49, 23, 13, 6, 5, 2, 2, 1, 1, 0, 1, 77, 61, 31, 15, 10, 5, 5, 2, 2, 1, 1, 0, 1

Offset: 0

Author

Alois P. Heinz, Jan 05 2011

Keywords

• nonn
• tabl

Comments

All parts of a number partition with the same value form a clique. The size of a clique is the number of elements in the clique. Each partition has a clique of size 0.

Examples

			T(5,2) = 2, because 2 (of 7) partitions of 5 contain (at least) one clique of size 2: [1,2,2], [1,1,3].
Triangle T(n,k) begins:
   1;
   1,  1;
   2,  1, 1;
   3,  2, 0, 1;
   5,  3, 2, 0, 1;
   7,  6, 2, 1, 0, 1;
  11,  7, 3, 2, 1, 0, 1;
  15, 13, 5, 3, 1, 1, 0, 1;
		

Links

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

Crossrefs

Columns k=0-10 give: A000041, A183558, A183559, A183560, A183561, A183562, A183563, A183564, A183565, A183566, A183567.

Differences between columns 0 and k (0A007690, A116645, A118807, A184639, A184640, A184641, A184642, A184643, A184644, A184645.

T(2*k+1,k+1) gives A002865.

Programs

Maple

b:= proc(n, i, k) option remember; `if`(n=0, [1, 0], `if`(i<1, [0, 0],
      add((l->`if`(j=k, [l[1]$2], l))(b(n-i*j, i-1, k)), j=0..n/i)))
    end:
T:= (n, k)-> (l-> l[`if`(k=0, 1, 2)])(b(n, n, k)):
seq(seq(T(n, k), k=0..n), n=0..12);

Mathematica

b[n_, i_, k_] := b[n, i, k] = If[n == 0, {1, 0}, If[i < 1, {0, 0}, Sum[Function[l, If[j == k, {l[[1]], l[[1]]}, l]][b[n - i*j, i-1, k]], {j, 0, n/i}]] ]; t[n_, k_] := Function[l, l[[If[k == 0, 1, 2]]]][b[n, n, k]]; Table[Table[t[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)

Formula

G.f. of column k: (1-Product_{j>0} (1-x^(k*j)+x^((k+1)*j))) / (Product_{j>0} (1-x^j)).