A173102 Number of partitions x + y = z with {x,y,z} in {1,2,3,..,3n} 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,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).

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) = 9n^2/4 if n is even.

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

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

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.

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

This is equal to 2*(Sum_{w = 1..3n/2} w) - 3n/2 = (3n/2)(3n/2+1) - 3n/2 = 9n^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

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

Prog

(Python)
def A173102(n):
    return (9*n**2 - (n % 2))//4 # Chai Wah Wu, Mar 03 2020
(PARI) vector(50, n, (18*n^2 +(-1)^n -1)/8 ) \\ G. C. Greubel, Mar 03 2020

Crossrefs

Cf. A016766, A136016.

Sequence in context: A154495 A248121 A014107 * A090398 A091941 A294540

Adjacent sequences: A173099 A173100 A173101 * A173103 A173104 A173105

Keyword

nonn,easy

Author

Artur Jasinski, Feb 09 2010

Status

approved