A116931 Number of partitions of n in which each part, with the possible exception of the largest, occurs at least twice.

1, 2, 2, 4, 4, 8, 8, 13, 15, 22, 24, 37, 40, 57, 64, 89, 98, 135, 149, 199, 224, 292, 325, 424, 472, 601, 676, 850, 950, 1191, 1329, 1643, 1845, 2258, 2524, 3082, 3442, 4158, 4659, 5591, 6246, 7472, 8338, 9903, 11072, 13077, 14586, 17184, 19150, 22431, 25019

Offset

1,2

Comments

Also, partitions of n in which any two distinct parts differ by at least 2. Example: a(5) = 4 because we have [5], [4,1], [3,1,1] and [1,1,1,1,1].

References

P. A. MacMahon, Combinatory Analysis, Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 2, p 52, Article 298.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..20000 (terms 1..7500 from Alois P. Heinz)

Mingjia Yang, Doron Zeilberger, Systematic Counting of Restricted Partitions, arXiv:1910.08989 [math.CO], 2019.

Formula

G.f.: sum(x^k*product(1+x^(2j)/(1-x^j), j=1..k-1)/(1-x^k), k=1..infinity). More generally, the g.f. of partitions of n in which each part, with the possible exception of the largest, occurs at least b times, is sum(x^k*product(1+x^(bj)/(1-x^j), j=1..k-1)/(1-x^k), k=1..infinity). It is also the g.f. of partitions of n in which any two distinct parts differ by at least b.

log(a(n)) ~ 2*Pi*sqrt(n)/3. - Vaclav Kotesovec, Jan 28 2022

Example

a(5) = 4 because we have [5], [3,1,1], [2,1,1,1] and [1,1,1,1,1].
q + 2*q^2 + 2*q^3 + 4*q^4 + 4*q^5 + 8*q^6 + 8*q^7 + 13*q^8 + 15*q^9 + ...
There are a(9) = 15 partitions of 9 where distinct parts differ by at least 2:
01:  [ 1 1 1 1 1 1 1 1 1 ]
02:  [ 3 1 1 1 1 1 1 ]
03:  [ 3 3 1 1 1 ]
04:  [ 3 3 3 ]
05:  [ 4 1 1 1 1 1 ]
06:  [ 4 4 1 ]
07:  [ 5 1 1 1 1 ]
08:  [ 5 2 2 ]
09:  [ 5 3 1 ]
10:  [ 6 1 1 1 ]
11:  [ 6 3 ]
12:  [ 7 1 1 ]
13:  [ 7 2 ]
14:  [ 8 1 ]
15:  [ 9 ]
- Joerg Arndt, Jun 09 2013

Maple

g:=sum(x^k*product(1+x^(2*j)/(1-x^j), j=1..k-1)/(1-x^k), k=1..70): gser:=series(g, x=0, 60): seq(coeff(gser, x^n), n=1..54);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
       b(n, i-1) +add(b(n-i*j, i-2), j=1..n/i)))
    end:
a:= n-> b(n, n):
seq(a(n), n=1..70);  # Alois P. Heinz, Nov 04 2012

Mathematica

b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + Sum[b[n-i*j, i-2], {j, 1, n/i}]]]; a[n_] := b[n, n]; Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)

Prog

(PARI) {a(n) = if( n<1, 0, polcoeff( sum( k=1, n, x^k / (1 - x^k) * prod( j=1, k-1, 1 + x^(2*j) / (1 - x^j), 1 + x * O(x^(n-k)))), n))} /* Michael Somos, Jan 26 2008 */

Crossrefs

Cf. A116932, A007690.

Column k=2 of A218698. - Alois P. Heinz, Nov 04 2012

Column k=0 of A268193. - Alois P. Heinz, Feb 13 2016

Sequence in context: A046971 A051754 A108747 * A206558 A145810 A172148

Adjacent sequences: A116928 A116929 A116930 * A116932 A116933 A116934

Keyword

nonn

Author

Emeric Deutsch, Feb 27 2006

Status

approved