login
Number of partitions of n into parts congruent to 1 mod 3.
26

%I #45 Aug 05 2020 22:03:32

%S 1,1,1,1,2,2,2,3,4,4,5,6,7,8,10,11,13,15,17,19,23,26,29,33,38,42,48,

%T 54,61,68,77,85,96,107,119,132,148,163,181,201,223,245,272,299,330,

%U 363,400,438,483,529,580,635,697,760,832,908,992,1081,1180,1283,1399,1521

%N Number of partitions of n into parts congruent to 1 mod 3.

%C a(n) = A116373(3*n). - _Reinhard Zumkeller_, Feb 15 2006

%H Alois P. Heinz and Vaclav Kotesovec, <a href="/A035382/b035382.txt">Table of n, a(n) for n = 0..10000</a> (terms 0..1000 from Alois P. Heinz)

%H Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, p. 350.

%F a(n) = 1/n*Sum_{k=1..n} A078181(k)*a(n-k), a(0) = 1.

%F G.f.: 1/prod(j>=0, 1-x^(1+3*j) ). - _Emeric Deutsch_, Mar 30 2006

%F From _Joerg Arndt_, Oct 02 2012: (Start)

%F G.f.: sum(n>=0, q^n/prod(k=1..n, 1-q^(3*k)) ); this is the special case of R=1, M=3 of the g.f. sum(n>=0, q^(R*n)/prod(k=1..n, 1-q^(M*k) ) ) for partitions into parts R mod M (where R!=0).

%F G.f. sum(n>=0, q^(3*n^2-2*n) / prod(k=0..n-1, (1-q^(3*k+3))*(1-q^(3*k+1))) ); this is the special case of R=1, M=3 of the g.f. sum(n>=0, q^(M*n^2+(R-M)*n) / prod(k=0..n-1, (1-q^(M*k+M))*(1-q^(M*k+R))) ) for partitions into parts R mod M (where R!=0). (See Fxtbook link)

%F (End)

%F a(n) ~ Gamma(1/3) * exp(sqrt(2*n)*Pi/3) / (2*sqrt(3) * (2*Pi*n)^(2/3)) * (1 + (Pi/72 - 2/(3*Pi)) / sqrt(2*n)). - _Vaclav Kotesovec_, Feb 26 2015, extended Jan 24 2017

%F Euler transform of period 3 sequence [ 1, 0, 0, ...]. - _Kevin T. Acres_, Apr 28 2018

%e a(3) = 1 because we have [1,1,1];

%e a(4) = 2 because we have [1,1,1,1] and [4];

%e a(9) = 4 because we have [7,1,1], [4,4,1], [4,1,1,1,1,1] and [1,1,1,1,1,1,1,1,1].

%e 1 + x + x^2 + x^3 + 2*x^4 + 2*x^5 + 2*x^6 + 3*x^7 + 4*x^8 + 4*x^9 + ...

%p g:= 1/product(1-x^(1+3*j), j=0..50): gser:= series(g, x=0, 64): seq(coeff(gser, x, n), n=0..61); # _Emeric Deutsch_, Mar 30 2006

%p # second Maple program

%p b:= proc(n, i) option remember; `if`(n=0, 1,

%p `if`(i<1, 0, b(n, i-3) +`if`(i>n, 0, b(n-i, i))))

%p end:

%p a:= n-> b(n, 3*iquo(n, 3)+1):

%p seq(a(n), n=0..100); # _Alois P. Heinz_, Oct 03 2012

%t b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-3] + If[i>n, 0, b[n-i, i]]]]; a[n_] := b[n, 3*Quotient[n, 3]+1]; Table[a[n], {n, 0, 100}] (* _Jean-François Alcover_, Mar 23 2015, after _Alois P. Heinz_ *)

%t nmax = 100; poly = ConstantArray[0, nmax + 1]; poly[[1]] = 1; poly[[2]] = -1; Do[If[Mod[k, 3] == 1, Do[poly[[j + 1]] -= poly[[j - k + 1]], {j, nmax, k, -1}];], {k, 2, nmax}]; poly2 = Take[poly, {2, nmax + 1}]; poly3 = 1 + Sum[poly2[[n]]*x^n, {n, 1, Length[poly2]}]; CoefficientList[Series[1/poly3, {x, 0, Length[poly2]}], x] (* _Vaclav Kotesovec_, Jan 13 2017 *)

%t nmax = 50; s = Range[0, nmax/3]*3 + 1;

%t Table[Count[IntegerPartitions@n, x_ /; SubsetQ[s, x]], {n, 0, nmax}] (* _Robert Price_, Aug 05 2020 *)

%Y Cf. A035386, A035451, A261612.

%K nonn

%O 0,5

%A _Olivier Gérard_