A111133 Number of partitions of n into at least two distinct parts.

0, 0, 0, 1, 1, 2, 3, 4, 5, 7, 9, 11, 14, 17, 21, 26, 31, 37, 45, 53, 63, 75, 88, 103, 121, 141, 164, 191, 221, 255, 295, 339, 389, 447, 511, 584, 667, 759, 863, 981, 1112, 1259, 1425, 1609, 1815, 2047, 2303, 2589, 2909, 3263, 3657, 4096, 4581, 5119, 5717, 6377

Offset

0,6

Comments

Old name: Number of sets of natural numbers less than n which sum to n.

From Clark Kimberling, Mar 13 2012: (Start)

(1) Number of partitions of n into at least two distinct parts.

(2) Also, number of partitions of 2n into distinct parts having maximal part n; see Example section. (End)

Links

Reinhard Zumkeller, Table of n, a(n) for n = 0..5000

Riccardo Aragona, Roberto Civino, and Norberto Gavioli, A modular idealizer chain and unrefinability of partitions with repeated parts, arXiv:2301.06347 [math.RA], 2023.

Thomas Enkosky and Branden Stone, Sequences defined by h-vectors, arXiv preprint arXiv:1308.4945 [math.CO], 2013.

Formula

a(n) = A000009(n) - 1. - Vladeta Jovovic, Oct 19 2005

G.f.: Sum_{k>=0} (x^((k^2+k)/2) / Product_{j=1..k} (1-x^j)) - 1/(1-x). - Joerg Arndt, Sep 17 2012

a(n) = A026906(floor(n-1)/2)) + A258259(n). - Bob Selcoe, Oct 05 2015

G.f.: -1/(1 - x) + Product_{k>=1} (1 + x^k). - Ilya Gutkovskiy, Aug 10 2018

Example

a(6) = 3 because 1+5, 2+4 and 1+2+3 each sum to 6. That is, the three sets are {1,5},{2,4},{1,2,3}.
For n=6, the partitions of 2n into distinct parts having maximum 6 are 6+5+1, 6+4+2, 6+3+2+1, so that a(6)=3, as an example for Comment (2). - Clark Kimberling, Mar 13 2012

Maple

seq(coeff(series(mul((1+x^k), k=1..n)-1/(1-x), x, n+1), x, n), n=0..60); # Muniru A Asiru, Aug 10 2018

Mathematica

Needs["DiscreteMath`Combinatorica`"]
f[n_] := Block[{lmt = Floor[(Sqrt[8n + 1] - 1)/2] + 1, t}, Sum[ Length[ Select[Plus @@@ KSubsets[ Range[n - k(k - 1)/2 + 1], k], # == n &]], {k, 2, lmt}]]; Array[f, 55] (* Robert G. Wilson v, Oct 17 2005 *)
(* Next program shows the partitions (sets) *)
d[n_] := Select[IntegerPartitions[n], Max[Length /@ Split@ #] == 1 &]; Table[d[n], {n, 1, 12}]
TableForm[%]
(* Clark Kimberling, Mar 13 2012 *)
Table[PartitionsQ[n]-1, {n, 0, 55}] (* Jean-François Alcover, Jan 17 2014, after Vladeta Jovovic *)

Prog

(PARI) N=66;  x='x+O('x^N);
gf=sum(k=0, N, x^((k^2+k)/2) / prod(j=1, k, 1-x^j)) - 1/(1-x);
concat( [0, 0, 0], Vec(gf) ) /* Joerg Arndt, Sep 17 2012 */
(Haskell)
a111133 = subtract 1 . a000009  -- Reinhard Zumkeller, Sep 09 2015

Crossrefs

Cf. A058377.

Cf. A000009.

Cf. A026906, A258259.

Sequence in context: A161306 A266744 A242216 * A279076 A076970 A064548

Adjacent sequences: A111130 A111131 A111132 * A111134 A111135 A111136

Keyword

nonn,nice

Author

David Sharp (davidsharp(AT)rcn.com), Oct 17 2005

Extensions

More terms from Vladeta Jovovic and Robert G. Wilson v, Oct 17 2005

a(0)=0 prepended by Joerg Arndt, Sep 17 2012

Status

approved