A183558 Number of partitions of n containing a clique of size 1.

0, 1, 1, 2, 3, 6, 7, 13, 16, 25, 33, 49, 61, 90, 113, 156, 198, 269, 334, 448, 556, 726, 902, 1163, 1428, 1827, 2237, 2817, 3443, 4302, 5219, 6478, 7833, 9632, 11616, 14197, 17031, 20712, 24769, 29925, 35688, 42920, 50980, 61059, 72318, 86206, 101837, 120941

Offset: 0

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(5) = 6, because 6 partitions of 5 contain (at least) one clique of size 1: [1,1,1,2], [1,2,2], [1,1,3], [2,3], [1,4], [5].
From _Gus Wiseman_, Apr 19 2019: (Start)
The a(1) = 1 through a(8) = 16 partitions are the following. The Heinz numbers of these partitions are given by A052485 (weak numbers).
  (1)  (2)  (3)   (4)    (5)     (6)      (7)       (8)
            (21)  (31)   (32)    (42)     (43)      (53)
                  (211)  (41)    (51)     (52)      (62)
                         (221)   (321)    (61)      (71)
                         (311)   (411)    (322)     (332)
                         (2111)  (3111)   (331)     (422)
                                 (21111)  (421)     (431)
                                          (511)     (521)
                                          (2221)    (611)
                                          (3211)    (3221)
                                          (4111)    (4211)
                                          (31111)   (5111)
                                          (211111)  (32111)
                                                    (41111)
                                                    (311111)
                                                    (2111111)
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..5000

Crossrefs

Column k=1 of A183568.

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

Cf. A052485, A090858, A117571, A127002, A325241, A325242, A325244.

Programs

Maple

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

Mathematica

max = 50; f = (1 - Product[1 - x^j + x^(2*j), {j, 1, max}])/Product[1 - x^j, {j, 1, max}]; s = Series[f, {x, 0, max}]; CoefficientList[s, x] (* Jean-François Alcover, Oct 01 2014. Edited by Gus Wiseman, Apr 19 2019 *)

Formula

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

From Vaclav Kotesovec, Nov 15 2016: (Start)

a(n) = A000041(n) - A007690(n).

a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*n). (End)

Extensions

a(0)=0 prepended by Gus Wiseman, Apr 19 2019