A034296 Number of flat partitions of n: partitions {a_i} with each |a_i - a_{i-1}| <= 1.

1, 1, 2, 3, 4, 5, 7, 8, 10, 13, 15, 18, 23, 26, 31, 39, 44, 52, 63, 72, 85, 101, 115, 134, 158, 181, 208, 243, 277, 318, 369, 418, 478, 549, 622, 710, 809, 914, 1036, 1177, 1328, 1498, 1695, 1904, 2143, 2416, 2706, 3036, 3408, 3811, 4264, 4769, 5319, 5934, 6621

Offset: 0

Author

Erich Friedman

Keywords

• nonn

Comments

Also number of partitions of n such that all parts, with the possible exception of the largest, appear only once. Example: a(6)=7 because we have [6], [5,1], [4,2], [3,3], [3,2,1], [2,2,2] and [1,1,1,1,1,1] ([4,1,1], [3,1,1,1], [2,2,1,1], [2,1,1,1,1,1] do not qualify). - Emeric Deutsch and Vladeta Jovovic, Feb 23 2006

Also the number of partitions p of n such that d(p) > max(p) - min(p), where d is the number of distinct parts of p; indeed that inequality occurs only when d(p) = 1+ max(p) - min(p), so p satisfies a(i) - a(i-1) = 1 for all parts, ordered as a(i) >= a(i-1) > ... > a(k). - Clark Kimberling, Apr 18 2014

Flat partitions are also called gap-free partitions. See, for example, the Grabner et al. reference. - Emeric Deutsch, Sep 22 2016

Conjecture: Also the sum of the smallest parts in the distinct partitions of n with an odd number of parts. - George Beck, May 06 2017

Above conjecture was proved by Shane Chern, see link. - George Beck, Aug 12 2017

Note that Andrews [2016] uses a(0) = 1. - Michael Somos, Aug 07 2017

Also called number of compact partitions of n where a compact partition is one where every integer between the largest and smallest parts of it also appears as a part. [Andrews 2016] - Michael Somos, Aug 13 2017

Examples

			From _Joerg Arndt_, Dec 27 2012: (Start)
The a(11)=18 flat partitions of 11 are (in lexicographic order)
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 1 1 1 1 1 1 1 1 1 ]
[ 3]  [ 2 2 1 1 1 1 1 1 1 ]
[ 4]  [ 2 2 2 1 1 1 1 1 ]
[ 5]  [ 2 2 2 2 1 1 1 ]
[ 6]  [ 2 2 2 2 2 1 ]
[ 7]  [ 3 2 1 1 1 1 1 1 ]
[ 8]  [ 3 2 2 1 1 1 1 ]
[ 9]  [ 3 2 2 2 1 1 ]
[10]  [ 3 2 2 2 2 ]
[11]  [ 3 3 2 1 1 1 ]
[12]  [ 3 3 2 2 1 ]
[13]  [ 3 3 3 2 ]
[14]  [ 4 3 2 1 1 ]
[15]  [ 4 3 2 2 ]
[16]  [ 4 4 3 ]
[17]  [ 6 5 ]
[18]  [ 11 ]
The a(11)=18 partitions of 11 where no part (except possibly the largest) is repeated are
[ 1]  [ 1 1 1 1 1 1 1 1 1 1 1 ]
[ 2]  [ 2 2 2 2 2 1 ]
[ 3]  [ 3 3 3 2 ]
[ 4]  [ 4 4 2 1 ]
[ 5]  [ 4 4 3 ]
[ 6]  [ 5 3 2 1 ]
[ 7]  [ 5 4 2 ]
[ 8]  [ 5 5 1 ]
[ 9]  [ 6 3 2 ]
[10]  [ 6 4 1 ]
[11]  [ 6 5 ]
[12]  [ 7 3 1 ]
[13]  [ 7 4 ]
[14]  [ 8 2 1 ]
[15]  [ 8 3 ]
[16]  [ 9 2 ]
[17]  [ 10 1 ]
[18]  [ 11 ]
(End)
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..10000
• George E. Andrews, The Bhargava-Adiga Summation and Partitions, 2016; See page 4 equation (2.1).
• Shane Chern, On a conjecture of George Beck, arXiv:1705.10700 [math.NT], 2017.
• P. J. Grabner, A. Knopfmacher, Analysis of some new partition statistics, Ramanujan J., 12, 2006, 439-454.
• Jia Huang, Compositions with restricted parts, arXiv:1812.11010 [math.CO], 2018. Also Discrete Masth., 343 (2020), # 111875.
• Jane Y. X. Yang, Combinatorial proofs and generalizations on conjectures related with Euler's partition theorem, arXiv:1801.06815 [math.CO], 2018.

Crossrefs

Cf. A034297, A239954, A092265.

Sequences "number of partitions with max diff d": A000005 (d=0, for n>=1), this sequence (d=1), A224956 (d=2), A238863 (d=3), A238864 (d=4), A238865 (d=5), A238866 (d=6), A238867 (d=7), A238868 (d=8), A238869 (d=9), A000041 (d --> infinity).

Programs

Maple

g:= 1+sum(x^j*product(1+x^i, i=1..j-1)/(1-x^j), j=1..60): gser:=series(g, x=0, 55): seq(coeff(gser, x, n), n=0..50); # Emeric Deutsch, Feb 23 2006
# second Maple program:
b:= proc(n, i) option remember;
      `if`(n=0, 1, `if`(i<1, 0, add(b(n-i*j, i-1), j=1..n/i)))
    end:
a:= n-> add(b(n, k), k=0..n):
seq(a(n), n=0..70);  # Alois P. Heinz, Jul 06 2012

Mathematica

nn=54;Drop[CoefficientList[Series[Sum[x^i/(1-x^i)Product[1+x^j,{j,1,i-1}],{i,1,nn}],{x,0,nn}],x],1] (* Geoffrey Critzer, Sep 28 2013 *)
b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[b[n-i*j, i-1], {j, 1, n/i}]]]; a[n_] := Sum[b[n, k], {k, 1, n}]; Table[a[n], {n, 1, 70}] (* Jean-François Alcover, Mar 24 2015, after Alois P. Heinz *)
a[ n_] := SeriesCoefficient[ Sum[ x^k / (1 - x^k) QPochhammer[ -x, x, k - 1] // FunctionExpand, {k, n}], {x, 0, n}]; (* Michael Somos, Aug 07 2017 *)

PARI

N = 66;  x = 'x + O('x^N);
gf = sum(n=1,N, x^n/(1-x^n) * prod(k=1,n-1,1+x^k) );
v = Vec(gf)
/* Joerg Arndt, Apr 21 2013 */

PARI

{a(n) = my(t); if( n<1, 0, polcoeff(sum(k=1, n, (t *= 1 + x^k) * x^k / (1 - x^(2*k)), t = 1 + x * O(x^n)), n))}; /* Michael Somos, Aug 07 2017 */

PARI

{a(n) = my(c); forpart(p=n, c++; for(i=1, #p-1, if( p[i+1] > p[i] + 1, c--; break))); c}; /* Michael Somos, Aug 13 2017 */

Python

from sympy.core.cache import cacheit
@cacheit
def b(n, i): return 1 if n==0 else 0 if i<1 else sum(b(n - i*j, i - 1) for j in range(1, n//i + 1))
def a(n): return sum(b(n, k) for k in range(n + 1))
print([a(n) for n in range(71)]) # Indranil Ghosh, Aug 14 2017, after Maple code by Alois P. Heinz

Formula

G.f.: x/(1-x) + x^2/(1-x^2)*(1+x) + x^3/(1-x^3)*(1+x)*(1+x^2) + x^4/(1-x^4)*(1+x)*(1+x^2)*(1+x^3) + x^5/(1-x^5)*(1+x)*(1+x^2)*(1+x^3)*(1+x^4) + ... . - Emeric Deutsch and Vladeta Jovovic, Feb 22 2006

a(n) = Sum_{k=0..1} A238353(n,k). - Alois P. Heinz, Mar 09 2014

a(n) ~ exp(Pi*sqrt(n/3)) / (4*3^(1/4)*n^(3/4)). - Vaclav Kotesovec, May 24 2018

Extensions

More terms from Emeric Deutsch, Feb 23 2006

a(0)=1 prepended by Alois P. Heinz, Aug 14 2017