A156040 Number of compositions (ordered partitions) of n into 3 parts (some of which may be zero), where the first is at least as great as each of the others.

1, 1, 3, 4, 6, 8, 11, 13, 17, 20, 24, 28, 33, 37, 43, 48, 54, 60, 67, 73, 81, 88, 96, 104, 113, 121, 131, 140, 150, 160, 171, 181, 193, 204, 216, 228, 241, 253, 267, 280, 294, 308, 323, 337, 353, 368, 384, 400, 417, 433, 451, 468, 486, 504, 523, 541, 561, 580, 600

Offset: 0

Author

Jack W Grahl, Feb 02 2009, Feb 11 2009

Keywords

• nonn
• easy

Comments

For n = 1, 2 these are just the triangular numbers. a(n) is always at least 1/3 of the corresponding triangular number, since each partition of this type gives up to three ordered partitions with the same cyclical order.

An alternative definition, which avoids using parts of size 0: a(n) is the third diagonal of A184957. - N. J. A. Sloane, Feb 27 2011

Diagonal sums of the triangle formed by rows T(2, k) k = 0, 1, ..., 2m of ascending m-nomial triangles (see A004737):

1

1 2 1

1 2 3 2 1

1 2 3 4 3 2 1

1 2 3 4 5 4 3 2 1

1 2 3 4 5 6 5 4 3 2 1

- Bob Selcoe, Feb 07 2014

Arrange A004396 in rows successively shifted to the right two spaces and sum the columns:

1 1 2 3 3 4 5 5 6 ...

1 1 2 3 3 4 5 ...

1 1 2 3 3 ...

1 1 2 ...

1 ...

------------------------------

1 1 3 4 6 8 11 13 17 ... - L. Edson Jeffery, Jul 30 2014

a(n) is the dimension of three-dimensional (2n + 2)-homogeneous polynomial vector fields with full tetrahedral symmetry (for a given orthogonal representation), and which are solenoidal. - Giedrius Alkauskas, Sep 30 2017

Also the number of compositions of n + 3 into three parts, the first at least as great as each of the other two. Also the number of compositions of n + 4 into three parts, the first strictly greater than each of the other two. - Gus Wiseman, Oct 09 2020

Examples

			G.f. = 1 + x + 3*x^2 + 4*x^3 + 6*x^4 + 8*x^5 + 11*x^6 + 13*x^7 + 17*x^8 + 20*x^9 + ...
The a(4) = 6 compositions of 4 are: (4 0 0), (3 1 0), (3 0 1), (2 2 0), (2 1 1), (2 0 2).
From _Gus Wiseman_, Oct 05 2020: (Start)
The a(0) = 1 through a(7) = 13 triples of nonnegative integers summing to n where the first is at least as great as each of the other two are:
  (000)  (100)  (101)  (111)  (202)  (212)  (222)  (313)
                (110)  (201)  (211)  (221)  (303)  (322)
                (200)  (210)  (220)  (302)  (312)  (331)
                       (300)  (301)  (311)  (321)  (403)
                              (310)  (320)  (330)  (412)
                              (400)  (401)  (402)  (421)
                                     (410)  (411)  (430)
                                     (500)  (420)  (502)
                                            (501)  (511)
                                            (510)  (520)
                                            (600)  (601)
                                                   (610)
                                                   (700)
(End)
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Giedrius Alkauskas, Projective and polynomial superflows. I, arxiv.org/1601.06570 [math.AG] (2017), Section 4.3.
• Index entries for linear recurrences with constant coefficients, signature (1,1,0,-1,-1,1).

Crossrefs

For compositions into 4 summands see A156039; also see A156041 and A156042.

Cf. A184957, A071619 (bisection).

A001399(n-2)*2 is the strict case.

A001840(n-2) is the version with opposite relations.

A001840(n-1) is the version with strict opposite relations.

A069905 is the case with strict relations.

A014311 ranks 3-part compositions, with strict case A337453.

A014612 ranks 3-part partitions, with strict case A007304.

Cf. A000217, A001523, A211540, A218004, A220377, A337483, A337484.

Programs

Maple

a:= proc(n) local m, r; m := iquo(n, 6, 'r'); (4 +6*m +2*r) *m + [1, 1, 3, 4, 6, 8][r+1] end: seq(a(n), n=0..60); # Alois P. Heinz, Jun 14 2009

Mathematica

nn = 58; CoefficientList[Series[x^3/(1 - x^2)^2/(1 - x^3) + 1/(1 - x^2)^2/(1 - x), {x, 0, nn}], x] (* Geoffrey Critzer, Jul 14 2013 *)
CoefficientList[Series[(1 + x^2)/((1 + x) * (1 + x + x^2) * (1 - x)^3), {x, 0, 58}], x] (* L. Edson Jeffery, Jul 29 2014 *)
LinearRecurrence[{1, 1, 0, -1, -1, 1}, {1, 1, 3, 4, 6, 8}, 60] (* Harvey P. Dale, May 28 2015 *)
Table[Length[Select[Join@@Permutations/@IntegerPartitions[n+3,{3}],#[[1]]>=#[[2]]&&#[[1]]>=#[[3]]&]],{n,0,15}] (* Gus Wiseman, Oct 05 2020*)

PARI

{a(n) = n*(n+4)\6 + 1}; /* Michael Somos, Mar 26 2017 */

Formula

G.f.: (x^2+1) / (1-x-x^2+x^4+x^5-x^6). - Alois P. Heinz, Jun 14 2009

Slightly nicer g.f.: (1+x^2)/((1-x)*(1-x^2)*(1-x^3)). - N. J. A. Sloane, Apr 29 2011

a(n) = A007590(n+2) - A000212(n+2). - Richard R. Forberg, Dec 08 2013

a(2*n) = A071619(n+1). - L. Edson Jeffery, Jul 29 2014

a(n) = a(n-1) + a(n-2) - a(n-4) - a(n-5) + a(n-6), with a(0) = 1, a(1) = 1, a(2) = 3, a(3) = 4, a(4) = 6, a(5) = 8. - Harvey P. Dale, May 28 2015

a(n) = (n^2 + 4*n + 3)/6 + IF(MOD(n, 2) = 0, 1/2) + IF(MOD(n, 3) = 1, -1/3). - Heinrich Ludwig, Mar 21 2017

a(n) = 1 + floor((n^2 + 4*n)/6). - Giovanni Resta, Mar 21 2017

Euler transform of length 4 sequence [1, 2, 1, -1]. - Michael Somos, Mar 26 2017

a(n) = a(-4 - n) for all n in Z. - Michael Somos, Mar 26 2017

0 = a(n)*(-1 + a(n) - 2*a(n+1) - 2*a(n+2) + 2*a(n+3)) + a(n+1)*(+1 + a(n+1) + 2*a(n+2) - 2*a(n+3)) + a(n+2)*(+1 + a(n+2) - 2*a(n+3)) + a(n+3)*(-1 + a(n+3)) for all n in Z. - Michael Somos, Mar 26 2017

a(n) = round((n+1)*(n+3)/6). - Bill McEachen, Feb 16 2021

Sum_{n>=0} 1/a(n) = 3/2 + Pi^2/36 + (tan(c1)-1)*c1 + 3*c2*sinh(c2)/(1+2*cosh(c2)), where c1 = Pi/(2*sqrt(3)) and c2 = Pi*sqrt(2)/3. - Amiram Eldar, Dec 10 2022

E.g.f.: ((16 + 15*x + 3*x^2)*cosh(x) + 2*exp(-x/2)*(cos(sqrt(3)*x/2) - sqrt(3)*sin(sqrt(3)*x/2)) + (7 + 15*x + 3*x^2)*sinh(x))/18. - Stefano Spezia, Apr 05 2023

Extensions

More terms from Alois P. Heinz, Jun 14 2009