A173102 Number of partitions x + y = z with {x,y,z} in {1,2,3,..,3*n} and z > y >= x.
2, 9, 20, 36, 56, 81, 110, 144, 182, 225, 272, 324, 380, 441, 506, 576, 650, 729, 812, 900, 992, 1089, 1190, 1296, 1406, 1521, 1640, 1764, 1892, 2025, 2162, 2304, 2450, 2601, 2756, 2916, 3080, 3249, 3422, 3600, 3782, 3969, 4160, 4356, 4556, 4761, 4970
Offset: 1
Links
- Chai Wah Wu, Table of n, a(n) for n = 1..10000
- Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
- Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).
Programs
-
Maple
seq( (-1 +(-1)^n +18*n^2)/8, n=1..50); # G. C. Greubel, Mar 03 2020
-
Mathematica
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 -
PARI
vector(50, n, (18*n^2 +(-1)^n -1)/8 ) \\ G. C. Greubel, Mar 03 2020
-
Python
def A173102(n): return (9*n**2 - (n % 2))//4 # Chai Wah Wu, Mar 03 2020
Formula
Conjectures from Colin Barker, Sep 04 2013: (Start)
a(n) = (-1 + (-1)^n + 18*n^2)/8.
a(n) = 2*a(n-1) - 2*a(n-3) + a(n-4).
G.f.: x*(2+x)*(1+2*x)/((1-x)^3*(1+x)). (End)
Conjecture: a(n) = Sum_{j=1..n} Sum_{i=1..n} ceiling((i+j-n+3)/2). - Wesley Ivan Hurt, Mar 12 2015
From Chai Wah Wu, Mar 03 2020: (Start)
a(n) = (9*n^2-1)/4 if n is odd and a(n) = 9*n^2/4 if n is even.
Proof: z ranges from 2 to 3*n. For each z, since z = y+x >= 2*x, 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..3*n} floor(z/2).
For z odd, floor(z/2) = floor((z-1)/2).
As a consequence, if n is odd, 3*n is odd and floor(z/2) occur in pairs, i.e. Sum_{z = 2..3*n} floor(z/2) = 2*(Sum_{w = 1..floor(3*n/2)} w) = 2*(Sum_{w = 1..(3*n-1)/2} w) = 2*((3*n-1)*(3*n+1)/8) = (3*n-1)*(3*n+1)/4 = (9*n^2-1)/4.
If n is even, 3*n is even and floor(z/2) occurs in pairs, except for when z = 3*n where floor(z/2) occurs once. Thus Sum_{z = 2..3*n} floor(z/2) = 2*(Sum_{w = 1..floor(3*n/2)} w) - floor(3*n/2).
This is equal to 2*(Sum_{w = 1..3*n/2} w) - 3*n/2 = (3*n/2)*(3*n/2+1) - 3*n/2 = 9*n^2/4.
This also implies that the above conjectures on the recurrence and g.f. are true.
(End)
E.g.f.: (9*x*(1 + x)*cosh(x) + (-1 + 9*x + 9*x^2)*sinh(x))/4. - Stefano Spezia, Mar 04 2020