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,4

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.

Links

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

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)

Example

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)

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 *)

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.

Sequence in context: A182708 A304709 A330145 * A328164 A294916 A233423

Adjacent sequences: A183555 A183556 A183557 * A183559 A183560 A183561

Keyword

nonn

Author

Alois P. Heinz, Jan 05 2011

Extensions

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

Status

approved