A001401 Number of partitions of n into at most 5 parts. (Formerly M0642 N0237)

1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 84, 101, 119, 141, 164, 192, 221, 255, 291, 333, 377, 427, 480, 540, 603, 674, 748, 831, 918, 1014, 1115, 1226, 1342, 1469, 1602, 1747, 1898, 2062, 2233, 2418, 2611, 2818, 3034, 3266, 3507, 3765, 4033, 4319

Offset

0,3

Comments

a(n) = T_{r}(n) for r large, where T_{r}(n) = number of outcomes in which r indistinguishable dice yield a sum r+n-1.

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

For n > 4: also number of partitions of n into parts <= 5: a(n) = A026820(n,5). - Reinhard Zumkeller, Jan 21 2010

Number of different distributions of n+15 identical balls in 5 boxes as x,y,z,p,q where 0 < x < y < z < p < q. - Ece Uslu and Esin Becenen, Jan 11 2016 [i.e., a(n) is the number of partitions of n+15 into 5 distinct parts. - R. J. Mathar, Feb 28 2021]

Tengely and Ulas prove that a(n) is a square only for n=1 and 2027. - Michel Marcus, Feb 11 2021

References

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 115, row m=5 of Q(m,n) table.

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

D. E. Knuth, The Art of Computer Programming, vol. 4, fascicle 3, Generating All Combinations and Partitions, 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

Philippe Deléham, Letter to N. J. A. Sloane, Apr 20 1998

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 354

Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.7.

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.

Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions, J. Integer Seqs., Vol. 7, 2004.

B. Kisacanin, Mathematical Problems and Proofs, Plenum, New York, 1998, pp. 71-72.

Jon Perry, More Partition Function

Szabolcs Tengely and Maciej Ulas, Equal values of certain partition functions via Diophantine equations, arXiv:2102.05352 [math.NT], 2021.

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

Formula

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

a(n) = 1 + (a(n-2) + a(n-3) + a(n-4)) - (a(n-6) + (2*a(n-7)) + a(n-8)) + (a(n-10) + a(n-11) + a(n-12)) - a(n-14). - Norman J. Meluch (norm(AT)iss.gm.com), Mar 09 2000

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

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

a(n) = round(((n+5)^4 + 10*((n+5)^3 + (n+5)^2) - 75*(n+5) - 45*(n+5)*(-1)^(n+5))/2880). - Washington Bomfim, Jul 03 2012

a(n) = a(n-1) + a(n-2) - a(n-5) - a(n-6) - a(n-7) + a(n-8) + a(n-9) + a(n-10) - a(n-13) - a(n-14) + a(n+15). - David Neil McGrath, Sep 13 2014

a(n+5) = a(n) + A001400(n) = A001400(n)+A026811(n). - Ece Uslu, Esin Becenen, Jan 11 2016

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

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

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

Example

(5 choose 5)_q = 1;
(6 choose 5)_q = q^5 + q^4 + q^3 + q^2 + q + 1;
(7 choose 5)_q = q^10 + q^9 + 2*q^8 + 2*q^7 + 3*q^6 + 3*q^5 + 3*q^4 + 2*q^3 + 2*q^2 + q + 1;
(8 choose 5)_q = q^15 + q^14 + 2*q^13 + 3*q^12 + 4*q^11 + 5*q^10 + 6*q^9 + 6*q^8 + 6*q^7 + 6*q^6 + 5*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.
a(3) = 3, i.e., {1,2,3,4,8}, {1,2,3,5,7}, {1,2,4,5,6}. Number of different distributions of 18 identical balls in 5 boxes as x,y,z,p,q where 0 < x < y < z < p < q. - Ece Uslu, Esin Becenen, Jan 11 2016

Maple

with(combstruct):ZL6:=[S, {S=Set(Cycle(Z, card<6))}, unlabeled]:seq(count(ZL6, size=n), n=0..52); # Zerinvary Lajos, Sep 24 2007
a:= n-> (Matrix(15, (i, j)-> if (i=j-1) then 1 elif j=1 then [1, 1, 0, 0, -1, -1, -1, 1, 1, 1, 0, 0, -1, -1, 1][i] else 0 fi)^n)[1, 1]: seq(a(n), n=0..60); # Alois P. Heinz, Jul 31 2008
B:=[S, {S = Set(Sequence(Z, 1 <= card), card <=5)}, unlabelled]: seq(combstruct[count](B, size=n), n=0..52); # Zerinvary Lajos, Mar 21 2009

Mathematica

CoefficientList[ Series[ 1/((1 - x)*(1 - x^2)*(1 - x^3)*(1 - x^4)*(1 - x^5)), {x, 0, 60} ], x ]
a[n_] := IntegerPartitions[n, 5] // Length; Table[a[n], {n, 0, 52}] (* Jean-François Alcover, Jul 13 2012 *)
LinearRecurrence[{1, 1, 0, 0, -1, -1, -1, 1, 1, 1, 0, 0, -1, -1, 1}, {1, 1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70}, 60] (* Harvey P. Dale, Jan 05 2019 *)

Prog

(PARI) a(n)=#partitions(n, , 5) \\ Charles R Greathouse IV, Sep 15 2014

Crossrefs

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

Cf. A008619, A001400, A001399, A008667 (first differences).

First differences of A002622.

Sequence in context: A341912 A033485 A026811 * A347549 A008628 A363067

Adjacent sequences: A001398 A001399 A001400 * A001402 A001403 A001404

Keyword

nonn,easy,nice

Author

N. J. A. Sloane

Extensions

Additional comments from Michael Somos and Branislav Kisacanin (branislav.kisacanin(AT)delphiauto.com)

Status

approved