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

%I M0627 N0229 #244 Jun 02 2024 14:40:06

%S 1,1,2,3,5,6,9,11,15,18,23,27,34,39,47,54,64,72,84,94,108,120,136,150,

%T 169,185,206,225,249,270,297,321,351,378,411,441,478,511,551,588,632,

%U 672,720,764,816,864,920,972,1033,1089,1154,1215,1285,1350,1425,1495

%N Number of partitions of n into at most 4 parts.

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

%C Also number of pure 2-complexes on 4 nodes with n multiple 2-simplexes. - _Vladeta Jovovic_, Dec 27 1999

%C 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

%C 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

%C Also number of partitions of n into parts <= 4. a(n) = A026820(n,4), for n > 3. - _Reinhard Zumkeller_, Jan 21 2010

%C 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

%C 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

%C 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

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

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

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

%D 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.

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

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

%H T. D. Noe, <a href="/A001400/b001400.txt">Table of n, a(n) for n = 0..1000</a>

%H Nesrine Benyahia-Tani, Zahra Yahi, and Sadek Bouroubi, <a href="http://ftp.math.uni-rostock.de/pub/romako/heft68/bouroubi68.html">Ordered and non-ordered non-congruent convex quadrilaterals inscribed in a regular n-gon.</a> Rostocker Math. Kolloq. 68, 71-79 (2013), g(Z).

%H Jonathan Bloom and Nathan McNew, <a href="https://arxiv.org/abs/1908.03953">Counting pattern-avoiding integer partitions</a>, arXiv:1908.03953 [math.CO], 2019.

%H V. M. Buchstaber and A. V. Ustinov, <a href="https://doi.org/10.1070/SM2015v206n11ABEH004504">Coefficient rings of formal group laws</a>, Sbornik: Mathematics, Volume 206, Number 11.

%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

%H Éva Czabarka, Peter Dankelmann, Trevor Olsen, and László A. Székely, <a href="https://arxiv.org/abs/1905.06753">Wiener Index and Remoteness in Triangulations and Quadrangulations</a>, arXiv:1905.06753 [math.CO], 2019.

%H F. Ellermann, <a href="/A061924/a061924.txt">Illustration for A001400, A061924</a>

%H C. E. Frasser and G. N. Vostrov, <a href="https://arxiv.org/abs/1611.01873">Geodetic Graphs Homeomorphic to a Given Geodetic Graph</a>, arXiv:1611.01873 [cs.DM], 2016. [p. 16, corollary 5]

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=353">Encyclopedia of Combinatorial Structures 353</a>

%H Gerzson Keri and Patric R. J. Östergård, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL9/Keri/keri6.html">The Number of Inequivalent (2R+3,7)R Optimal Covering Codes</a>, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.7.

%H G. Nebe, E. M. Rains and N. J. A. Sloane, <a href="http://neilsloane.com/doc/cliff2.html">Self-Dual Codes and Invariant Theory</a>, Springer, Berlin, 2006.

%H Jon Perry, <a href="https://web.archive.org/web/20060923015527/http://www.users.globalnet.co.uk/~perry/maths/morepartitionfunction/morepartitionfunction.htm">More Partition Functions</a>

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992

%H <a href="/index/Rec#order_10">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,0,0,-2,0,0,1,1,-1).

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

%F 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

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

%F 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

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

%F (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)).

%F a(n) = round(((n+4)^3 + 3*(n+4)^2 - 9*(n+4)*((n+4) mod 2))/144). - _Washington Bomfim_, Jul 03 2012

%F 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

%F a(n) = -a(-10-n) for all n in Z. - _Michael Somos_, Dec 29 2014

%F 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

%F 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

%F a(n) = a(n-4) + A001399(n). - _Ece Uslu_, Esin Becenen, Jan 11 2016, corrected Sep 25 2020

%F a(6*n) - a(6*n+1) - a(6*n+4) + a(6*n+5) = n+1. - _Richard Turk_, Apr 19 2016

%F a(n) = a(n-1) + A005044(n+3) for n>0, i.e., first differences is A005044. - _Yuchun Ji_, Oct 12 2020

%F From _Vladimír Modrák_ and _Zuzana Soltysova_, Dec 09 2020: (Start)

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

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

%F a(n) - a(n-3) = A008642(n). - _R. J. Mathar_, Jun 23 2021

%F a(n) - a(n-2) = A025767(n). - _R. J. Mathar_, Jun 23 2021

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

%F From _Vladimír Modrák_, Jul 13 2022: (Start)

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

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

%e (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.

%e G.f. = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 6*x^5 + 9*x^6 + 11*x^7 + ...

%e 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

%p A001400 := n->if n mod 2 = 0 then round(n^2*(n+3)/144); else round((n-1)^2*(n+5)/144); fi;

%p with(combstruct):ZL5:=[S,{S=Set(Cycle(Z,card<5))}, unlabeled]:seq(count(ZL5,size=n),n=0..55); # _Zerinvary Lajos_, Sep 24 2007

%p 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]

%p 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

%t CoefficientList[ Series[ 1/((1 - x)*(1 - x^2)*(1 - x^3)*(1 - x^4)), {x, 0, 65} ], x ]

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

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

%t a[ n_] := With[{m = n + 5}, Round[ (2 m^3 - 3 m (5 + 3 (-1)^m)) / 288]]; (* _Michael Somos_, Dec 29 2014 *)

%t a[ n_] := With[{m = Abs[n + 5] - 5}, Sign[n + 5] Length[ IntegerPartitions[ m, 4]]]; (* _Michael Somos_, Dec 29 2014 *)

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

%t Table[Length@IntegerPartitions[n, 4], {n, 0, 55}] (* _Robert Price_, Aug 18 2020 *)

%o (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);

%o (PARI) a(n) = round(((n+4)^3 + 3*(n+4)^2 -9*(n+4)*((n+4)% 2))/144) \\ _Washington Bomfim_, Jul 03 2012

%o (PARI) {a(n) = n+=5; round( (2*n^3 - 3*n*(5 + 3*(-1)^n)) / 288)}; \\ _Michael Somos_, Dec 29 2014

%o (PARI) a(n) = #partitions(n,,4); \\ _Ruud H.G. van Tol_, Jun 02 2024

%o (Haskell)

%o a001400 n = a001400_list !! n

%o a001400_list = scanl1 (+) a005044_list -- _Reinhard Zumkeller_, Feb 28 2013

%Y Essentially same as A026810. Partial sums of A005044.

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

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

%Y First differences of A002621.

%K nonn,easy

%O 0,3

%A _N. J. A. Sloane_