A197126 Triangle T(n,k), n>=1, 1<=k<=n, read by rows: T(n,k) is the number of cliques of size k in all partitions of n.

1, 1, 1, 3, 0, 1, 4, 2, 0, 1, 8, 2, 1, 0, 1, 11, 4, 2, 1, 0, 1, 19, 5, 3, 1, 1, 0, 1, 26, 10, 3, 3, 1, 1, 0, 1, 41, 11, 7, 3, 2, 1, 1, 0, 1, 56, 20, 8, 5, 3, 2, 1, 1, 0, 1, 83, 25, 13, 6, 5, 2, 2, 1, 1, 0, 1, 112, 38, 17, 11, 5, 5, 2, 2, 1, 1, 0, 1, 160, 49, 25, 13, 9, 5, 4, 2, 2, 1, 1, 0, 1

Offset: 1

Author

Alois P. Heinz, Oct 10 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.

Examples

			T(4,1) = 4: [1,1,(2)], [(1),(3)], [(4)].
T(8,3) = 3: [1,1,(2,2,2)], [(1,1,1),2,3], [(1,1,1),5].
T(12,4) = 11: [(1,1,1,1),(2,2,2,2)], [1,(2,2,2,2),3], [(1,1,1,1),2,3,3], [(3,3,3,3)], [(1,1,1,1),2,2,4], [(2,2,2,2),4], [(1,1,1,1),4,4], [(1,1,1,1),3,5], [(1,1,1,1),2,6], [(1,1,1,1),8].  Here the first partition contains 2 cliques.
Triangle begins:
   1;
   1,  1;
   3,  0, 1;
   4,  2, 0, 1;
   8,  2, 1, 0, 1;
  11,  4, 2, 1, 0, 1;
  19,  5, 3, 1, 1, 0, 1;
  26, 10, 3, 3, 1, 1, 0, 1;
  ...
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened
• Abdulaziz M. Alanazi and Augustine O. Munagi, On partition configurations of Andrews-Deutsch, Integers 17 (2017), #A7.

Crossrefs

Columns k=1-10 give: A024786(n+1), A116646, A117524, A222704, A222705, A222706, A222707, A222708, A222709, A222710.

Row sums give: A000070(n-1). Diagonal gives: A000012. Limit of reversed rows: T(2*n+1,n+1) = A002865(n).

Cf. A213180.

Programs

Maple

b:= proc(n, p, k) option remember; `if`(n=0, [1, 0], `if`(p<1, [0, 0],
      add((l->`if`(m=k, l+[0, l[1]], l))(b(n-p*m, p-1, k)), m=0..n/p)))
    end:
T:= (n, k)-> b(n, n, k)[2]:
seq(seq(T(n, k), k=1..n), n=1..20);

Mathematica

Table[CoefficientList[ 1/q* Tr[Flatten[q^Map[Length, Split /@ IntegerPartitions[n], {2}]]], q], {n, 24}] (* Wouter Meeussen, Apr 21 2012 *)
b[n_, p_, k_] := b[n, p, k] = If[n == 0, {1, 0}, If[p < 1, {0, 0}, Sum[ Function[l, If[m == k, l + {0, l[[1]]}, l]][b[n - p*m, p - 1, k]], {m, 0, n/p}]]]; T[n_, k_] := b[n, n, k][[2]]; Table[Table[T[n, k], {k, 1, n}], {n, 1, 20}] // Flatten (* Jean-François Alcover, Aug 29 2016, after Alois P. Heinz *)

Formula

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

Column k is asymptotic to exp(Pi*sqrt(2*n/3)) / (k*(k+1)*Pi*2^(3/2)*sqrt(n)). - Vaclav Kotesovec, May 24 2018