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

%I #36 Sep 08 2022 08:45:24

%S 1,2,3,5,7,10,13,17,22,27,33,41,48,57,68,78,90,105,118,134,153,170,

%T 190,214,235,260,289,315,345,380,411,447,488,525,567,615,658,707,762,

%U 812,868,931,988,1052,1123,1188,1260,1340,1413,1494,1583,1665,1755,1854

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

%H Alois P. Heinz, <a href="/A117143/b117143.txt">Table of n, a(n) for n = 1..1000</a>

%H Jonathan Bloom, Nathan McNew, <a href="https://arxiv.org/abs/1908.03953">Counting pattern-avoiding integer partitions</a>, arXiv:1908.03953 [math.CO], 2019.

%H <a href="/index/Rec#order_09">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,1,-2,-2,1,1,1,-1).

%F 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).

%F 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

%F 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

%e 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).

%p 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

%t Table[Count[IntegerPartitions[n], _?(Max[#] - Min[#] <= 3 &)], {n, 30}] (* _Birkas Gyorgy_, Feb 20 2011 *)

%o (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

%o (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

%Y Cf. A117142.

%Y Column k=3 of A194621.

%Y Cf. A002717, A045947, A248851.

%K nonn,easy

%O 1,2

%A _Emeric Deutsch_, Feb 27 2006