A001400 Number of partitions of n into at most 4 parts. (Formerly M0627 N0229)

1, 1, 2, 3, 5, 6, 9, 11, 15, 18, 23, 27, 34, 39, 47, 54, 64, 72, 84, 94, 108, 120, 136, 150, 169, 185, 206, 225, 249, 270, 297, 321, 351, 378, 411, 441, 478, 511, 551, 588, 632, 672, 720, 764, 816, 864, 920, 972, 1033, 1089, 1154, 1215, 1285, 1350, 1425, 1495

Offset

0,3

Comments

Molien series for 4-dimensional representation of S_4 [Nebe, Rains, Sloane, Chap. 7].

Also number of pure 2-complexes on 4 nodes with n multiple 2-simplexes. - Vladeta Jovovic, Dec 27 1999

Also number of different integer triangles with perimeter <= n+3. Also number of different scalene integer triangles with perimeter <= n+9. - Reinhard Zumkeller, May 12 2002

a(n) is the coefficient of q^n in the expansion of (m choose 4)_q as m goes to infinity. - Y. Kelly Itakura (yitkr(AT)mta.ca), Aug 21 2002

Also number of partitions of n into parts <= 4. a(n) = A026820(n,4), for n > 3. - Reinhard Zumkeller, Jan 21 2010

Number of different distributions of n+10 identical balls in 4 boxes as x,y,z,p where 0 < x < y < z < p. - Ece Uslu and Esin Becenen, Jan 11 2016

Number of partitions of 5n+8 or 5n+12 into 4 parts (+-) 3 mod 5. a(4) = 5 partitions of 28: [7,7,7,7], [12,7,7,2], [12,12,2,2], [17,7,2,2], [22,2,2,2]. a(3) = 3 partitions of 27: [8,8,8,3], [13,8,3,3], [18,3,3,3]. - Richard Turk, Feb 24 2016

a(n) is the total number of non-isomorphic geodetic graphs of diameter n homeomorphic to a complete graph K4. - Carlos Enrique Frasser, May 24 2018

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 115, row m=4 of Q(m,n) table; p. 120, P(n,4).

H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 2.

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 275.

D. E. Knuth, The Art of Computer Programming, vol. 4, Fascicle 3, Generating All Combinations and Partitions, Addison-Wesley, 2005, Section 7.2.1.4., p. 56, exercise 31.

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

T. D. Noe, Table of n, a(n) for n = 0..1000

Nesrine Benyahia-Tani, Zahra Yahi, and Sadek Bouroubi, Ordered and non-ordered non-congruent convex quadrilaterals inscribed in a regular n-gon. Rostocker Math. Kolloq. 68, 71-79 (2013), g(Z).

Jonathan Bloom and Nathan McNew, Counting pattern-avoiding integer partitions, arXiv:1908.03953 [math.CO], 2019.

V. M. Buchstaber and A. V. Ustinov, Coefficient rings of formal group laws, Sbornik: Mathematics, Volume 206, Number 11.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

Éva Czabarka, Peter Dankelmann, Trevor Olsen, and László A. Székely, Wiener Index and Remoteness in Triangulations and Quadrangulations, arXiv:1905.06753 [math.CO], 2019.

F. Ellermann, Illustration for A001400, A061924

C. E. Frasser and G. N. Vostrov, Geodetic Graphs Homeomorphic to a Given Geodetic Graph, arXiv:1611.01873 [cs.DM], 2016. [p. 16, corollary 5]

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 353

Gerzson Keri and Patric R. J. Östergård, The Number of Inequivalent (2R+3,7)R Optimal Covering Codes, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.7.

G. Nebe, E. M. Rains and N. J. A. Sloane, Self-Dual Codes and Invariant Theory, Springer, Berlin, 2006.

Jon Perry, More Partition Functions

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992

Index entries for linear recurrences with constant coefficients, signature (1,1,0,0,-2,0,0,1,1,-1).

Formula

G.f.: 1/((1-x)*(1-x^2)*(1-x^3)*(1-x^4)).

a(n) = 1 + (a(n-2) + a(n-3) + a(n-4)) - (a(n-5) + a(n-6) + a(n-7)) + a(n-9). - Norman J. Meluch (norm(AT)iss.gm.com), Mar 09 2000

P(n, 4) = (1/288)*(2*n^3 + 6*n^2 - 9*n - 13 + (9*n+9)*pcr{1, -1}(2, n) - 32*pcr{1, -1, 0}(3, n) - 36*pcr{1, 0, -1, 0}(4, n)) (see Comtet).

Let c(n) = Sum_{i=0..floor(n/3)} (1 + ceiling((n-3*i-1)/2)), then a(n) = Sum_{i=0..floor(n/4)} (1 + ceiling((n-4*i-1)/2) + c(n-4*i-3)). - Jon Perry, Jun 27 2003

Euler transform of finite sequence [1, 1, 1, 1].

(n choose 4)_q = (q^n-1)*(q^(n-1)-1)*(q^(n-2)-1)*(q^(n-3)-1)/((q^4-1)*(q^3-1)*(q^2-1)*(q-1)).

a(n) = round(((n+4)^3 + 3*(n+4)^2 - 9*(n+4)*((n+4) mod 2))/144). - Washington Bomfim, Jul 03 2012

a(n) = a(n-1) + a(n-2) - 2*a(n-5) + a(n-8) + a(n-9) - a(n-10). - David Neil McGrath, Sep 12 2014

a(n) = -a(-10-n) for all n in Z. - Michael Somos, Dec 29 2014

a(n) - a(n+1) - a(n+3) + a(n+4) = 0 if n is odd, else floor(n/4) + 2 for all n in Z. - Michael Somos, Dec 29 2014

a(n) = n^3/144 + n^2/24 - 7*n/144 + 1 + floor(n/4)/4 + floor(n/3)/3 + (n+5)*floor(n/2)/8 + floor((n+1)/4)/4. - Vaclav Kotesovec, Aug 18 2015

a(n) = a(n-4) + A001399(n). - Ece Uslu, Esin Becenen, Jan 11 2016, corrected Sep 25 2020

a(6*n) - a(6*n+1) - a(6*n+4) + a(6*n+5) = n+1. - Richard Turk, Apr 19 2016

a(n) = a(n-1) + A005044(n+3) for n>0, i.e., first differences is A005044. - Yuchun Ji, Oct 12 2020

From Vladimír Modrák and Zuzana Soltysova, Dec 09 2020: (Start)

a(n) = round((n + 3)^2/12) + Sum_{i=0..floor(n/4)} round((n - 4*i - 1)^2/12).

a(n) = floor(((n + 3)^2 + 4)/12) + Sum_{i=0..floor(n/4)} floor(((n - 4*i - 1)^2 + 4)/12). (End)

a(n) - a(n-3) = A008642(n). - R. J. Mathar, Jun 23 2021

a(n) - a(n-2) = A025767(n). - R. J. Mathar, Jun 23 2021

a(n) = round((2*n^3 + 30*n^2 + 135*n + 175)/288 + (-1)^n*(n+5)/32). - Dave Neary, Oct 28 2021

From Vladimír Modrák, Jul 13 2022: (Start)

a(n) = Sum_{j=0..floor(n/4)} Sum_{i=0..floor(n/3)} ceiling((max(0,n + 1 - 3*i - 4*j))/2).

a(n) = Sum_{i=0..floor(n/4)} floor(((n + 3 - 4*i)^2 + 4)/12). (End)

Example

(4 choose 4)_q = 1, (5 choose 4)_q = q^4 + q^3 + q^2 + q + 1, (6 choose 4)_q = q^8 + q^7 + 2*q^6 + 2*q^5 + 3*q^4 + 2*q^3 + 2*q^2 + q + 1, (7 choose 4) = q^12 + q^11 + 2*q^10 + 3*q^9 + 4*q^8 + 4*q^7 + 5*q^6 + 4*q^5 + 4*q^4 + 3*q^3 + 2*q^2 + q + 1 so the coefficient of q^0 converges to 1, q^1 to 1, q^2 to 2 and so on.
G.f. = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 6*x^5 + 9*x^6 + 11*x^7 + ...
a(4) = 5, i.e., {1,2,3,8}, {1,2,4,7}, {1,2,5,6}, {2,3,4,5}, {1,3,4,6}. Number of different distributions of 14 identical balls in 4 boxes as x,y,z,p where 0 < x < y < z < p. - Ece Uslu, Esin Becenen, Jan 11 2016

Maple

A001400 := n->if n mod 2 = 0 then round(n^2*(n+3)/144); else round((n-1)^2*(n+5)/144); fi;
with(combstruct):ZL5:=[S, {S=Set(Cycle(Z, card<5))}, unlabeled]:seq(count(ZL5, size=n), n=0..55); # Zerinvary Lajos, Sep 24 2007
A001400:=-(-z**8+z**9+2*z**4-z**7-1-z)/(z**2+1)/(z**2+z+1)/(z+1)**2/(z-1)**4; # [conjectured by Simon Plouffe in his 1992 dissertation; gives sequence except for an initial 1]
B:=[S, {S = Set(Sequence(Z, 1 <= card), card <=4)}, unlabelled]: seq(combstruct[count](B, size=n), n=0..55); # Zerinvary Lajos, Mar 21 2009

Mathematica

CoefficientList[ Series[ 1/((1 - x)*(1 - x^2)*(1 - x^3)*(1 - x^4)), {x, 0, 65} ], x ]
LinearRecurrence[{1, 1, 0, 0, -2, 0, 0, 1, 1, -1}, {1, 1, 2, 3, 5, 6, 9, 11, 15, 18}, 80] (* Vladimir Joseph Stephan Orlovsky, Feb 17 2012 *)
a[n_] := Sum[Floor[(n - j - 3*k + 2)/2], {j, 0, Floor[n/4]}, {k, j, Floor[(n - j)/3]}]; Table[a[n], {n, 0, 55}] (* L. Edson Jeffery, Jul 31 2014 *)
a[ n_] := With[{m = n + 5}, Round[ (2 m^3 - 3 m (5 + 3 (-1)^m)) / 288]]; (* Michael Somos, Dec 29 2014 *)
a[ n_] := With[{m = Abs[n + 5] - 5}, Sign[n + 5] Length[ IntegerPartitions[ m, 4]]]; (* Michael Somos, Dec 29 2014 *)
a[ n_] := With[{m = Abs[n + 5] - 5}, Sign[n + 5] SeriesCoefficient[ 1 / ((1 - x) (1 - x^2) (1 - x^3) (1 - x^4)), {x, 0, m}]]; (* Michael Somos, Dec 29 2014 *)
Table[Length@IntegerPartitions[n, 4], {n, 0, 55}] (* Robert Price, Aug 18 2020 *)

Prog

(Magma) K:=Rationals(); M:=MatrixAlgebra(K, 4); q1:=DiagonalMatrix(M, [1, -1, 1, -1]); p1:=DiagonalMatrix(M, [1, 1, -1, -1]); q2:=DiagonalMatrix(M, [1, 1, 1, -1]); h:=M![1, 1, 1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, -1, 1]/2; G:=MatrixGroup<4, K|q1, q2, h>; MolienSeries(G);
(PARI) a(n) = round(((n+4)^3 + 3*(n+4)^2 -9*(n+4)*((n+4)% 2))/144) \\ Washington Bomfim, Jul 03 2012
(PARI) {a(n) = n+=5; round( (2*n^3 - 3*n*(5 + 3*(-1)^n)) / 288)}; \\ Michael Somos, Dec 29 2014
(Haskell)
a001400 n = a001400_list !! n
a001400_list = scanl1 (+) a005044_list -- Reinhard Zumkeller, Feb 28 2013

Crossrefs

Essentially same as A026810. Partial sums of A005044.

a(n) = A008284(n+4, 4), n >= 0.

Cf. A008619, A001399, A001401, A026820, A070083, A117486.

First differences of A002621.

Sequence in context: A028309 A242717 A026810 * A350897 A008773 A008772

Adjacent sequences: A001397 A001398 A001399 * A001401 A001402 A001403

Keyword

nonn,easy

Author

N. J. A. Sloane

Status

approved