A156042 -id:A156042 - cp's OEIS frontend

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

Jack W Grahl, Feb 02 2009, Feb 11 2009

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

			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)

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

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.

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

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

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

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

More terms from Alois P. Heinz, Jun 14 2009

A156041 Array A(n,k) (n>=1, k>=1) read by antidiagonals, where A(n,k) is the number of compositions (ordered partitions) of n into exactly k parts, some of which may be zero, with the first part greater than or equal to all the rest.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 3, 4, 4, 1, 1, 3, 6, 7, 5, 1, 1, 4, 8, 11, 11, 6, 1, 1, 4, 11, 17, 19, 16, 7, 1, 1, 5, 13, 26, 32, 31, 22, 8, 1, 1, 5, 17, 35, 54, 56, 48, 29, 9, 1, 1, 6, 20, 48, 82, 102, 93, 71, 37, 10, 1, 1, 6, 24, 63, 120, 172, 180, 148, 101, 46, 11, 1, 1, 7, 28, 81, 170

Offset: 1

Jack W Grahl, Feb 02 2009, Feb 11 2009

A(n,k) is of course smaller than the number of ordered partitions of n into k parts and at least the number of partitions into k parts in descending order.
The sums of the antidiagonals give A079500 - 1. - N. J. A. Sloane, Feb 26 2011
For an alternative definition of essentially the same sequence, as a triangle, and which avoids the use of parts of size zero, see A184957. - N. J. A. Sloane, Feb 27 2011

			The array A(n,k) begins:
  1  1  1  1  1  1  1  1  1 ...
  1  2  3  4  5  6  7  8  9 ...
  1  2  4  7 11 16 22 29 ...
  1  3  6 11 19 31 48 ...
  1  3  8 17 32 56 ...
  1  4 11 26 54 ...
  1  4 13 35 ...
  ...
The antidiagonals are:
  1,
  1, 1,
  1, 2, 1,
  1, 2, 3, 1,
  1, 3, 4, 4, 1,
  1, 3, 6, 7, 5, 1,
  1, 4, 8, 11, 11, 6, 1,
  1, 4, 11, 17, 19, 16, 7, 1,
  1, 5, 13, 26, 32, 31, 22, 8, 1,
  ...
A(3,5) = 11 and the 11 partition of 3 into 5 parts of this type are: (3,0,0,0,0), (2,1,0,0,0), (2,0,1,0,0), (2,0,0,1,0), (2,0,0,0,1), (1,1,1,0,0), (1,1,0,1,0), (1,1,0,0,1), (1,0,1,1,0), (1,0,1,0,1), (1,0,0,1,1).

R. H. Hardin, Table of n, a(n) for n = 1..2278
Michele Graffeo, Sergej Monavari, Riccardo Moschetti, and Andrea T. Ricolfi, Enumeration of partitions via socle reduction, arXiv:2501.10267 [math.CO], 2025. See p. 32.

A156039 gives A(n,4) and A156040 gives A(n,3). A156042 is the part on or below the main diagonal. A(n,2) is A008619. A(2,n) is A000027. A(3,n) is A000124.

Cf. A079500.

b:= proc(n, i, m) option remember;
      if n<0 then 0
    elif n=0 then 1
    elif i=1 then `if`(n<=m, 1, 0)
    else add(b(n-k, i-1, m), k=0..m)
      fi
    end:
A:= (n, k)-> add(b(n-m, k-1, m), m=ceil(n/k)..n):
seq(seq(A(d-k, k), k=1..d-1), d=1..14); # Alois P. Heinz, Jun 14 2009

(* Returns rectangular array *) nn=10;Table[Table[Coefficient[Series[Sum[x^i((1-x^(i+1))/(1-x))^(k-1),{i,0,n}],{x,0,nn}],x^n],{k,1,nn}],{n,1,nn}]//Grid (* Geoffrey Critzer, Jul 15 2013 *)

A(n,k) = [x^n] Sum_{i=0..n} x^i*((1 - x^(i+1))/(1-x))^(k-1). - Geoffrey Critzer, Jul 15 2013

More terms from Alois P. Heinz, Jun 14 2009

Edited by N. J. A. Sloane, Feb 26 2011

A156039 Number of compositions (ordered partitions) of n into 4 parts, where the first is at least as great as each of the others.

Original entry on oeis.org

1, 1, 4, 7, 11, 17, 26, 35, 48, 63, 81, 102, 127, 154, 187, 223, 263, 308, 359, 413, 474, 540, 612, 690, 775, 865, 964, 1069, 1181, 1301, 1430, 1565, 1710, 1863, 2025, 2196, 2377, 2566, 2767, 2977, 3197, 3428, 3671, 3923, 4188, 4464, 4752, 5052, 5365, 5689

Offset: 0

Jack W Grahl, Feb 02 2009, Feb 11 2009

nonn

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

Diagonal sums of the irregular triangle A109439, for example a(0)=1, a(1)=1, a(2)=1+3, a(3)=1+3+3, a(4)=1+3+6+1. - Bob Selcoe, Feb 09 2014

			For n = 3 the a(3) = 7 compositions are: (3 0 0 0) (2 1 0 0) (2 0 1 0) (2 0 0 1) (1 1 1 0) (1 1 0 1) (1 0 1 1).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2, -1, 1, -1, -1, 1, -1, 2, -1).

For partitions into 3 summands see A156040; also see A156041 and A156042.

a:= proc(n) local m, r; m:= iquo(n, 12, 'r'); r:= r+1; (9 +(27 +72*m +18*r)*m +((9 +3*r) *r-12) /2)*m +[1, 1, 4, 7, 11, 17, 26, 35, 48, 63, 81, 102][r] end: seq(a(n), n=0..60); # Alois P. Heinz, Jun 14 2009

LinearRecurrence[{2, -1, 1, -1, -1, 1, -1, 2, -1}, {1, 1, 4, 7, 11, 17, 26, 35, 48}, 60] (* Jean-François Alcover, May 17 2018 *)

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

More terms from Alois P. Heinz, Jun 14 2009

A156043 A(n,n), where A(n,k) is the number of compositions (ordered partitions) of n into k parts (parts of size 0 being allowed), with the first part being greater than or equal to all the rest.

Original entry on oeis.org

1, 2, 4, 11, 32, 102, 331, 1101, 3724, 12782, 44444, 156334, 555531, 1991784, 7197369, 26186491, 95847772, 352670170, 1303661995, 4838822931, 18025920971, 67371021603, 252538273442, 949164364575, 3576145084531, 13503991775252

Offset: 1

Jack W Grahl, Feb 02 2009

nonn

The value is smaller than the number of compositions of n into k parts and at least the number of (unordered) partitions.
It is also at least the number of compositions of n into n parts  divided by n. From these bounds: C(2*n-1,n-1)/n <= a(n) <= C(2*n-1,n-1). - Robert Gerbicz, Apr 06 2011
a(n) is also the number of Dyck paths of semilength 2n such that each level has exactly n peaks or no peaks. a(3) = 4: //\\//\\//\\, ///\\//\/\\\, ///\/\\//\\\, ////\/\/\\\\. - Alois P. Heinz, Jun 04 2017

			a(4) = 11: the 11 compositions of this type of 4 into 4 parts being
(4,0,0,0); (3,1,0,0); (3,0,1,0); (3,0,0,1);
(2,2,0,0); (2,0,2,0); (2,0,0,2); (2,1,1,0);
(2,1,0,1); (2,0,1,1); (1,1,1,1)

Robert Gerbicz, Table of n, a(n) for n = 1..500

A156041 gives the full array A(n, k). See also A156039, A156040 and A156042.

One of two bisections of A188624 (see also A188625).

b:= proc(n,i,m) option remember; if n<0 then 0 elif n=0 then 1 elif i=1 then `if`(n<=m, 1, 0) else add(b(n-k, i-1, m), k=0..m) fi end: A:= (n,k)-> add(b(n-m, k-1, m), m=ceil(n/k)..n): seq(A(n,n), n=1..30); # Alois P. Heinz, Jun 14 2009

b[n_, i_, m_] := b[n, i, m] = Which[n<0, 0, n==0, 1, i==1, If[n <= m, 1, 0], True, Sum[b[n-k, i-1, m], {k, 0, m}]]; A[n_, k_] := Sum[b[n-m, k-1, m], {m, Ceiling[n/k], n}]; Table[A[n, n], {n, 1, 30}] (* Jean-François Alcover, Jul 15 2015, after Alois P. Heinz *)

N=120;v=vector(N,i,0);for(d=1,N,A=matrix(N,N,i,j,0);A[1,1]=1; for(i=1,N-1,for(j=0,N-1,s=0;for(k=0,min(j,d), s+=A[i,j-k+1]);A[i+1,j+1]=s)); for(i=d,N,v[i]+=A[i,i-d+1]));for(i=1,N,print1(v[i]", ")) \\ Robert Gerbicz, Apr 06 2011

More terms from Alois P. Heinz, Jun 14 2009

Edited by N. J. A. Sloane, Apr 06 2011

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A156041 Array A(n,k) (n>=1, k>=1) read by antidiagonals, where A(n,k) is the number of compositions (ordered partitions) of n into exactly k parts, some of which may be zero, with the first part greater than or equal to all the rest.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A156039 Number of compositions (ordered partitions) of n into 4 parts, where the first is at least as great as each of the others.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A156043 A(n,n), where A(n,k) is the number of compositions (ordered partitions) of n into k parts (parts of size 0 being allowed), with the first part being greater than or equal to all the rest.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions