login
Number of partitions x + y = z with {x,y,z} in {1,2,3,..,3n} and z > y >= x.
1

%I #36 Mar 04 2020 07:41:42

%S 2,9,20,36,56,81,110,144,182,225,272,324,380,441,506,576,650,729,812,

%T 900,992,1089,1190,1296,1406,1521,1640,1764,1892,2025,2162,2304,2450,

%U 2601,2756,2916,3080,3249,3422,3600,3782,3969,4160,4356,4556,4761,4970

%N Number of partitions x + y = z with {x,y,z} in {1,2,3,..,3n} and z > y >= x.

%H Chai Wah Wu, <a href="/A173102/b173102.txt">Table of n, a(n) for n = 1..10000</a>

%H Paul Barry, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Barry/barry321.html">Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices</a>, Journal of Integer Sequences, 19, 2016, #16.3.5.

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

%F Conjectures from _Colin Barker_, Sep 04 2013: (Start)

%F a(n) = (-1 + (-1)^n + 18*n^2)/8.

%F a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4).

%F G.f.: x*(2+x)*(1+2*x)/((1-x)^3*(1+x)). (End)

%F Conjecture: a(n) = Sum_{j=1..n} Sum_{i=1..n} ceiling((i+j-n+3)/2). - _Wesley Ivan Hurt_, Mar 12 2015

%F From _Chai Wah Wu_, Mar 03 2020: (Start)

%F a(n) = (9*n^2-1)/4 if n is odd and a(n) = 9n^2/4 if n is even.

%F Proof: z ranges from 2 to 3n. For each z, since z = y+x >= 2x, x ranges from 1 to floor(z/2), i.e. there are floor(z/2) partitions. Thus the total number of partitions is a(n) = Sum_{z = 2..3n} floor(z/2).

%F For z odd, floor(z/2) = floor((z-1)/2).

%F As a consequence, if n is odd, 3n is odd and floor(z/2) occur in pairs, i.e. Sum_{z = 2..3n} floor(z/2) = 2*(Sum_{w = 1..floor(3n/2}} w) = 2*(Sum_{w = 1..(3n-1)/2}} w) = 2*((3n-1)*(3n+1)/8) = (3n-1)*(3n+1)/4 = (9*n^2-1)/4.

%F If n is even, 3n is even and floor(z/2) occurs in pairs, except for when z = 3n where floor(z/2) occurs once. Thus Sum_{z = 2..3n} floor(z/2) = 2*(Sum_{w = 1..floor(3n/2}} w) - floor(3n/2).

%F This is equal to 2*(Sum_{w = 1..3n/2} w) - 3n/2 = (3n/2)(3n/2+1) - 3n/2 = 9n^2/4.

%F This also implies that the above conjectures on the recurrence and G.f. are true.

%F (End)

%F E.g.f.: (9*x*(1 + x)*cosh(x) + (-1 + 9*x + 9*x^2)*sinh(x))/4. - _Stefano Spezia_, Mar 04 2020

%p seq( (-1 +(-1)^n +18*n^2)/8, n=1..50); # _G. C. Greubel_, Mar 03 2020

%t aa = {}; Do[i = 0; Do[Do[Do[If[x + y == z, i = i + 1], {x, y, 3 n}], {y, 1, 3 n}], {z, 1, 3 n}]; AppendTo[aa, i], {n, 1, 50}]; aa

%o (Python)

%o def A173102(n):

%o return (9*n**2 - (n % 2))//4 # _Chai Wah Wu_, Mar 03 2020

%o (PARI) vector(50, n, (18*n^2 +(-1)^n -1)/8 ) \\ _G. C. Greubel_, Mar 03 2020

%Y Cf. A016766, A136016.

%K nonn,easy

%O 1,1

%A _Artur Jasinski_, Feb 09 2010