A117143 Number of partitions of n in which any two parts differ by at most 3.

1, 2, 3, 5, 7, 10, 13, 17, 22, 27, 33, 41, 48, 57, 68, 78, 90, 105, 118, 134, 153, 170, 190, 214, 235, 260, 289, 315, 345, 380, 411, 447, 488, 525, 567, 615, 658, 707, 762, 812, 868, 931, 988, 1052, 1123, 1188, 1260, 1340, 1413, 1494, 1583, 1665, 1755, 1854

Offset

1,2

Links

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Jonathan Bloom, Nathan McNew, Counting pattern-avoiding integer partitions, arXiv:1908.03953 [math.CO], 2019.

Index entries for linear recurrences with constant coefficients, signature (1,1,1,-2,-2,1,1,1,-1).

Formula

G.f.: sum(x^k/[(1-x^k)(1-x^(k+1))(1-x^(k+2))(1-x^(k+3))], k=1..infinity). More generally, the g.f. of the number of partitions in which any two parts differ by at most b is sum(x^k/product(1-x^j, j=k..k+b), k=1..infinity).

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

a(n)=(2*floor((n+2)/3)*(14*floor((n+2)/3)^2-(10*n+21)*floor((n+2)/3)+2*(n^2+5*n+7))-(1-(-1)^floor((n+2)/3))*(-1)^(n+2-floor((n+2)/3)))/16. - Luce ETIENNE, May 12 2015

Example

a(6) = 10 because we have [6], [4,2], [4,1,1], [3,3], [3,2,1], [3,1,1,1], [2,2,2], [2,2,1,1], [2,1,1,1,1] and [1,1,1,1,1,1] ([5,1] does not qualify).

Maple

g:=sum(x^k/(1-x^k)/(1-x^(k+1))/(1-x^(k+2))/(1-x^(k+3)), k=1..85): gser:=series(g, x=0, 65): seq(coeff(gser, x^n), n=1..59); 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]<4 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[#] <= 3 &)], {n, 30}] (* Birkas Gyorgy, Feb 20 2011 *)

Prog

(PARI) Vec(x*(x^5-x^4-x^3+x+1)/((x-1)^4*(x+1)*(x^2+x+1)^2) + O(x^100)) \\ Colin Barker, Mar 05 2015
(Magma) [(2*Floor((n+2)/3)*(14*Floor((n+2)/3)^2-(10*n+21)*Floor((n+2)/3)+2*(n^2+5*n+7))-(1-(-1)^Floor((n+2)/3))*(-1)^(n+2-Floor((n+2)/3)))/16: n in [1..60]]; // Vincenzo Librandi, May 12 2015

Crossrefs

Cf. A117142.

Column k=3 of A194621.

Cf. A002717, A045947, A248851.

Sequence in context: A194205 A136413 A177337 * A253170 A337567 A177332

Adjacent sequences: A117140 A117141 A117142 * A117144 A117145 A117146

Keyword

nonn,easy

Author

Emeric Deutsch, Feb 27 2006

Status

approved