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
Keywords
Examples
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
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.
Crossrefs
Column k=2 of A218698. - Alois P. Heinz, Nov 04 2012
Column k=0 of A268193. - Alois P. Heinz, Feb 13 2016
Programs
-
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 *) -
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 */
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
Comments