A117142 Number of partitions of n in which any two parts differ by at most 2.

1, 2, 3, 5, 6, 9, 10, 14, 15, 20, 21, 27, 28, 35, 36, 44, 45, 54, 55, 65, 66, 77, 78, 90, 91, 104, 105, 119, 120, 135, 136, 152, 153, 170, 171, 189, 190, 209, 210, 230, 231, 252, 253, 275, 276, 299, 300, 324, 325, 350, 351, 377, 378, 405, 406, 434, 435, 464, 465

Offset: 1

Author

Emeric Deutsch, Feb 27 2006

Keywords

• nonn
• easy

Comments

Equals row sums of triangle A177991. - Gary W. Adamson, May 16 2010

Positive numbers that are either triangular (A000217) or triangular minus 1 (A000096). - Jon E. Schoenfield, Jun 12 2010

Examples

			a(6) = 9 because we have
  1: [6],
  2: [4, 2],
  3: [3, 3],
  4: [3, 2, 1],
  5: [3, 1, 1, 1],
  6: [2, 2, 2],
  7: [2, 2, 1, 1],
  8: [2, 1, 1, 1, 1],
  9: [1, 1, 1, 1, 1, 1]
([5,1] and [4,1,1] do not qualify).
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1000
• Jonathan Bloom and Nathan McNew, Counting pattern-avoiding integer partitions, arXiv:1908.03953 [math.CO], 2019.
• Index entries for linear recurrences with constant coefficients, signature (1,2,-2,-1,1).

Crossrefs

Cf. A000096, A000217, A117143, A152271, A177991, A152919.

Column k=2 of A194621. - Alois P. Heinz, Oct 17 2012

Programs

GAP

List([1..60],n->(2*n^2+10*n+3+(-1)^n*(2*n-3))/16); # Muniru A Asiru, Dec 21 2018

Magma

[(2*n*(n+5) +3 +(-1)^n*(2*n-3))/16: n in [1..60]]; // G. C. Greubel, Jul 18 2023

Maple

g:=sum(x^k/(1-x^k)/(1-x^(k+1))/(1-x^(k+2)),k=1..75): gser:=series(g,x=0,70): seq(coeff(gser,x^n),n=1..65); with(combinat): for n from 1 to 7 do P:=partition(n): A:={}: for j from 1 to nops(P) do if P[j][nops(P[j])]-P[j][1]<3 then A:=A union {P[j]} else A:=A fi od: print(A); od: # this program yields the partitions

Mathematica

Table[Count[IntegerPartitions[n], ?(Max[#] - Min[#] <= 2 &)], {n, 30}] (* _Birkas Gyorgy, Feb 20 2011 *)
Table[(2*n^2 +10*n +3 +(-1)^n*(2*n-3))/16, {n,30}] (* Birkas Gyorgy, Feb 20 2011 *)
Table[Sum[If[EvenQ[k], 1, (k+1)/2], {k,0,n}], {n,0,60}] (* Jon Maiga, Dec 21 2018 *)

PARI

Vec(x*(x^2-x-1)/((x-1)^3*(x+1)^2) + O(x^100)) \\ Colin Barker, Mar 05 2015

SageMath

[(2*n*(n+5) +3 +(-1)^n*(2*n-3))/16 for n in range(1,61)] # G. C. Greubel, Jul 18 2023

Formula

G.f.: Sum_{k>=1} x^k/((1 - x^k)*(1 - x^(k + 1))*(1 - x^(k + 2))). More generally, the g.f. of the number of partitions in which any two parts differ by at most b is Sum_{k>=1} (x^k/(Product_{j=k..k+b} 1 - x^j)).

a(n) = (2*n^2 + 10*n + 3 + (-1)^n * (2*n - 3))/16. - Birkas Gyorgy, Feb 20 2011

G.f.: (1 + x)/(1 - x)/(Q(0) - x^2 - x^3), where Q(k) = 1 + x^2 + x^3 + k*x*(1 + x^2) - x^2*(1 + x*(k + 2))*(1 + k*x)/Q(k+1) ; (continued fraction). - Sergei N. Gladkovskii, Jan 05 2014

G.f.: x*(1 + x - x^2)/((1 - x)^3*(1 + x)^2). - Colin Barker, Mar 05 2015

a(n) = Sum_{k=0..n-1} A152271(k). - Jon Maiga, Dec 21 2018

E.g.f.: (1/16)*( (3 + 2*x)*exp(-x) + (3 + 12*x + 2*x^2)*exp(x) ). - G. C. Greubel, Jul 18 2023

a(n) = A152919(n+1)/2. - Ridouane Oudra, Oct 29 2024