A183559 Number of partitions of n containing a clique of size 2.

1, 0, 2, 2, 3, 5, 9, 10, 16, 23, 31, 43, 60, 75, 106, 140, 179, 237, 310, 389, 508, 647, 815, 1032, 1305, 1617, 2033, 2527, 3117, 3857, 4764, 5812, 7142, 8711, 10585, 12866, 15605, 18803, 22716, 27325, 32774, 39286, 47016, 56019, 66819, 79456, 94273, 111766

Offset: 2

Author

Alois P. Heinz, Jan 05 2011

Keywords

• nonn

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

			a(7) = 5, because 5 partitions of 7 contain (at least) one clique of size 2: [1,1,1,2,2], [1,1,2,3], [2,2,3], [1,3,3], [1,1,5].
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 2..1000

Crossrefs

Column k=2 of A183568.

Cf. A000041, A183558, A183560, A183561, A183562, A183563, A183564, A183565, A183566, A183567.

Programs

Maple

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

Mathematica

max = 50; f = (1 - Product[1 - x^(2j) + x^(3j), {j, 1, max}])/Product[1 - x^j, {j, 1, max}]; s = Series[f, {x, 0, max}]; Drop[CoefficientList[s, x], 2] (* Jean-François Alcover, Oct 01 2014 *)

Formula

G.f.: (1-Product_{j>0} (1-x^(2*j)+x^(3*j))) / (Product_{j>0} (1-x^j)).

a(n) = A000041(n) - A116645(n). - Vaclav Kotesovec, Jun 12 2025