1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385,

490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349,
10143, 12310, 14883, 17977, 21637, 26015, 31185, 37338, 44583, 53174, 63261, 75175,
89134, 105558, 124754, 147273, 173525 (list; graph; refs; listen; history; text;
internal format)
OFFSET
0,3
COMMENTS
Also number of nonnegative solutions to b + 2c + 3d + 4e + ... = n and the number
of nonnegative solutions to 2c + 3d + 4e + ... <= n. - Henry Bottomley, Apr 17 2001
a(n) is also the number of conjugacy classes in the symmetric group S_n (and the
number of irreducible representations of S_n).
Also the number of rooted trees with n+1 nodes and height at most 2.
Coincides with the sequence of numbers of nilpotent conjugacy classes in the Lie
algebras gl(n). A006950, A015128 and this sequence together cover the nilpotent
conjugacy classes in the classical A,B,C,D series of Lie algebras. - Alexander
Elashvili, Sep 08 2003
Number of distinct Abelian groups of order p^n, where p is prime (the number is
independent of p). - Lekraj Beedassy, Oct 16 2004
Number of graphs on n vertices that do not contain P3 as an induced subgraph. -
Washington Bomfim, May 10 2005
Numbers of terms to be added when expanding the n-th derivative of 1/f(x). - Thomas
Baruchel, Nov 07 2005
Sequence agrees with expansion of Molien series for symmetric group S_n up to the
term in x^n. - Maurice D. Craig (towenaar(AT)[Link]), Oct 30 2006
Also the number of nonnegative integer solutions to x_1 + x_2 + x_3 + ... + x_n = n
such that n >= x_1 >= x_2 >= x_3 >= ... >= x_n >= 0, because by letting y_k = x_k -
x_(k+1) >= 0 (where 0 < k < n) we get y_1 + 2y_2 + 3y_3 + ... + (n-1)y_(n-1) + nx_n
= n. - Werner Grundlingh (wgrundlingh(AT)[Link]), Mar 14 2007
Let P(z) := Sum_{j>=0} b_j z^j, b_0 != 0. Then 1/P(z) = Sum_{j>=0} c_j z^j, where
the c_j must be computed from the infinite triangular system b_0 c_0 = 1, b_0 c_1 +
b_1 c_0 = 0 and so on (Cauchy products of the coefficients set to zero). The n-th
partition number arises as the number of terms in the numerator of the expression
for c_n: The coefficient c_n of the inverted power series is a fraction with
b_0^(n+1) in the denominator and in its numerator having a(n) products of n
coefficients b_i each. The partitions may be read off from the indices of the b_i.
- Peter C. Heinig (algorithms(AT)[Link]), Apr 09 2007
Equals row sums of triangle A137683. - Gary W. Adamson, Feb 05 2008
a(n) is the number of different ways to run up a staircase with n steps, taking
steps of sizes 1, 2, 3, ... and r (r <= n), where the order is not important and
there is no restriction on the number or the size of each step taken. - Mohammad K.
Azarian, May 21 2008
Equals the eigenvector of triangle A145006 and row sums of the eigentriangle of the
partition numbers, A145007. - Gary W. Adamson, Sep 28 2008
Starting with offset 1 = INVERT transform of (1, 1, 0, 0, -1, 0, -1, ...), where
A080995, the characteristic function of A001318 (1, 2, 5, 7, 12, ...) is signed (++
-- ++, ...) as to 1's. This is equivalent to lim_{n>=1} A145006^n as a vector. The
INVERT transform of (1, 1, 0, 0, -1, ...) begins (1, 2,..) then for each successive
operation we take a dot product of (1, 1, 0, 0, -1, ...) in reverse and the ongoing
results of our series (1, 2, 3, 5, 7, ...) then add the result to the next term in
(1, 1, 0, 0, -1, ...). For example, a (7) = 15 = (0, -1, 0, 0, 1, 1) dot (1, 2, 3,
5, 7, 11) = (0*1, (-1)*2, 0*3, 0*5, 1*7, 1*11) = (-2 + 7 + 11) = 16, then add to (-
1) = 15. - Gary W. Adamson, Oct 05 2008
Convolved with A147843 = A000203 prefaced with a zero: (0, 1, 3, 4, 7, ...). - Gary
W. Adamson, Nov 15 2008
From Gary W. Adamson, Jun 12 2009: (Start)
Equals an infinite convolution product_(1, 1, 1, ...)*(1, 0, 1, 0, 1, ...)*(1, 0,
0, 1, 0, 0, 1, ...)*(1, 0, 0, 0, 1, 0, 0, 0, 1, ...)*...; = a*b*c*...; where a =
(1/(1-x)), b = (1/(1-x^2)), c = (1/(1-x^3)), etc. An array by rows: row 1 = a, row
2 = a*b, row 3 = a*b*c, ...; gives:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ... = (a)
1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ... = (a*b)
1, 1, 2, 3, 4, 5, 7, 8, 10, 11, ... = (a*b*c)
1, 1, 2, 3, 4, 5, 6, 9, 11, 17, ... = (a*b*c*d)
1, 1, 2, 3, 5, 5, 7, 10, 13, 18, ... = (a*b*c*d*e)
1, 1, 2, 3, 5, 7, 11, 14, 20, 25, ... = (a*b*c*d*e*f)
1, 1, 2, 3, 5, 7, 11, 15, 21, 27, ... = (a*b*c*d*e*f*g)
1, 1, 2, 3, 5, 7, 11, 15, 22, 28, ... = (a*b*c*d*e*f*g*h)
1, 1, 2, 3, 5, 7, 11, 15, 22, 29, ... = (a*b*c*d*e*f*g*h*i)
... with rows tending to A000041. Partition triangles A058398 = ascending
antidiagonals. Partition triangle A008284 reversal of A058398. (End)
Starting with offset 1 = row sums of triangle A168532. - Gary W. Adamson, Nov 28
2009
P(x) = A(x)/A(x^2) with P(x) = (1 + x + 2x^2 + 3x^3 + 5x^4 + 7x^5 + ...),
and A(x) = (1 + x + 3x^2 + 4x^3 + 10x^4 + 13x^5 + ...),
and A(x^2) = (1 + x^2 + 3x^4 + 4x^6 + 10x^8 + ...), where A092119 = (1, 1, 3, 4,
10, ...) = Euler transform of the ruler sequence, A001511. - Gary W. Adamson, Feb
11 2010
Equals row sums of triangle A173304. - Gary W. Adamson, Feb 15 2010
p(x) = A(x)*A(x^2), A(x) = A174065; p(x) = B(x)*B(x^3), B(x) = A174068. Equals row
sums of triangles A174066 and A174067. - Gary W. Adamson, Mar 06 2010
Triangle A113685 is equivalent to p(x) = p(x^2) * A000009(x). Triangle A176202 is
equivalent to p(x) = p(x^3) * A000726(x). - Gary W. Adamson, Apr 11 2010
A sequence of positive integers p = p_1 ... p_k is a descending partition of the
positive integer n if p_1 + ... + p_k = n and p_1 >= ... >= p_k. If formally needed
p_j = 0 is appended to p for j > k. Let P_n denote the set of these partition for
some n >= 1. Then a(n) = 1 + Sum_{p in P_n} floor((p_1-1)/(p_2+1)). (Cf. A000065,
where the formula reduces to the sum.) Proof in Kelleher and O'Sullivan (2009). For
example a(6) = 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 2 + 5 = 11. - Peter Luschny,
Oct 24 2010
Let n = Sum( k_(p_m) p_m ) = k_1 + 2k_2 + 5k_5 + 7k_7 + ..., where p_m is the m-th
generalized pentagonal number (A001318). Then a(n) is the sum over all such
pentagonal partitions of n of (-1)^(k_5+k_7 + k_22 + ...) ( k_1 + k_2 + k_5 + ...)!
/( k_1! k_2! k_5! ...), where the exponent of (-1) is the sum of all the k's
corresponding to even-indexed GPN's. - Jerome Malenfant, Feb 14 2011
From Jerome Malenfant, Feb 14 2011: (Start)
The matrix of a(n) values
a(0)
a(1) a(0)
a(2) a(1) a(0)
a(3) a(2) a(1) a(0)
....
a(n) a(n-1) a(n-2) ... a(0)
is the inverse of the matrix
1
-1 1
-1 -1 1
0 -1 -1 1
....
-d_n -d_(n-1) -d_(n-2) ... -d_1 1
where d_q = (-1)^(m+1) if q = m(3m-1)/2 = the m-th generalized pentagonal number
(A001318), = 0 otherwise. (End)
Equals row sums of triangle A187566. - Gary W. Adamson, Mar 21 2011
Let k > 0 be an integer, and let i_1, i_2, ..., i_k be distinct integers such that
1 <= i_1 < i_2 < ... < i_k. Then, equivalently, a(n) equals the number of
partitions of N = n + i_1 + i_2 + ... + i_k in which each i_j (1 <= j <= k) appears
as a part at least once. To see this, note that the partitions of N of this class
must be in 1-to-1 correspondence with the partitions of n, since N - i_1 - i_2
- ... - i_k = n. - L. Edson Jeffery, Apr 16 2011
a(n) is the number of distinct degree sequences over all free trees having n + 2
nodes. Take a partition of the integer n, add 1 to each part and append as many
1's as needed so that the total is 2n + 2. Now we have a degree sequence of a tree
with n + 2 nodes. Example: The partition 3 + 2 + 1 = 6 corresponds to the degree
sequence {4, 3, 2, 1, 1, 1, 1, 1} of a tree with 8 vertices. - Geoffrey Critzer,
Apr 16 2011
a(n) is number of distinct characteristic polynomials among n! of permutations
matrices size n X n. - Artur Jasinski, Oct 24 2011
Conjecture: starting with offset 1 represents the numbers of ordered compositions
of n using the signed (++--++...) terms of A001318 starting (1, 2, -5, -7, 12,
15, ...). - Gary W. Adamson, Apr 04 2013 (this is true by the pentagonal number
theorem, Joerg Arndt, Apr 08 2013)
a(n) is also number of terms in expansion of the n-th derivative of log(f(x)). In
Mathematica notation: Table[Length[Together[f[x]^n * D[Log[f[x]], {x, n}]]], {n, 1,
20}]. - Vaclav Kotesovec, Jun 21 2013
Conjecture: No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02
2013
Partitions of n that contain a part p are the partitions of n - p. Thus, number of
partitions of m*n - r that include k*n as a part is A000041(h*n-r), where h = m - k
>= 0, n >= 2, 0 <= r < n; see A111295 as an example. - Clark Kimberling, Mar 03
2014
a(n) is the number of compositions of n into positive parts avoiding the pattern
[1, 2]. - Bob Selcoe, Jul 08 2014
Conjecture: For any j there exists k such that all primes p <= A000040(j) are
factors of one or more a(n) <= a(k). Growth of this coverage is slow and irregular.
k = 1067 covers the first 102 primes, thus slower than A000027. - Richard R.
Forberg, Dec 08 2014
a(n) is the number of nilpotent conjugacy classes in the order-preserving, order-
decreasing and (order-preserving and order-decreasing) injective transformation
semigroups. - Ugbene Ifeanyichukwu, Jun 03 2015
Define a segmented partition a(n,k, <s(1)..s(j)>) to be a partition of n with
exactly k parts, with s(j) parts t(j) identical to each other and distinct from all
the other parts. Note that n >= k, j <= k, 0 <= s(j) <= k, s(1)t(1) + ... +
s(j)t(j) = n and s(1) + ... + s(j) = k. Then there are up to a(k) segmented
partitions of n with exactly k parts. - Gregory L. Simay, Nov 08 2015
(End)
From Gregory L. Simay, Nov 09 2015: (Start)
The polynomials for a(n, k, <s(1), ..., s(j)>) have degree j-1.
a(n, k, <k>) = 1 if n = 0 mod k, = 0 otherwise
a(rn, rk, <r*s(1), ..., r*s(j)>) = a(n, k, <s(1), ..., s(j)>)
a(n odd, k, <all s(j) even>) = 0
Established results can be recast in terms of segmented partitions:
For j(j+1)/2 <= n < (j+1)(j+2)/2, A000009(n) = a(n, 1, <1>) + ... + a(n, j, <j
1's>), j < n
a(n, k, <j 1's> = a(n - j(j-1)/2, k)
(End)
a(10^20) was computed using the NIST Arb package. It has 11140086260 digits and its
head and tail sections are 18381765...88091448. See the Johansson 2015 link. -
Stanislav Sykora, Feb 01 2016
Satisfies Benford's law [Anderson-Rolen-Stoehr, 2011]. - N. J. A. Sloane, Feb 08
2017
The partition function p(n) is log-concave for all n>25 [DeSalvo-Pak, 2014]. -
Michel Marcus, Apr 30 2019
a(n) is also the dimension of the n-th cohomology of the infinite real Grassmannian
with coefficients in Z/2. - Luuk Stehouwer, Jun 06 2021
Number of equivalence relations on n unlabeled nodes. - Lorenzo Sauras Altuzarra,
Jun 13 2022
Equivalently, number of idempotent mappings f from a set X of n elements into
itself (i.e., satisfying f o f = f) up to permutation (i.e., f~f' :<=> There is a
permutation sigma in Sym(X) such that f' o sigma = sigma o f). - Philip Turecek,
Apr 17 2023
Conjecture: Each integer n > 2 different from 6 can be written as a sum of finitely
many numbers of the form a(k) + 2 (k > 0) with no summand dividing another. This
has been verified for n <= 7140. - Zhi-Wei Sun, May 16 2023
REFERENCES
George E. Andrews, The Theory of Partitions, Addison-Wesley, Reading, Mass., 1976.
George E. Andrews and K. Ericksson, Integer Partitions, Cambridge University Press
2004.
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page
307.
R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc.,
1963; Chapter III.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics
and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem II, Missouri
Journal of Mathematical Sciences, Vol. 16, No. 1, Winter 2004, pp. 12-17.
Zentralblatt MATH, Zbl 1071.05501.
Bruce C. Berndt, Ramanujan's Notebooks Part V, Springer-Verlag.
B. C. Berndt, Number Theory in the Spirit of Ramanujan, Chap. I Amer. Math. Soc.
Providence RI 2006.
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page
999.
J. M. Borwein, D. H. Bailey and R. Girgensohn, Experimentation in Mathematics, A K
Peters, Ltd., Natick, MA, 2004. x+357 pp. See p. 183.
L. E. Dickson, History of the Theory of Numbers, [Link] Chapter III pp. 101-164,
Chelsea NY 1992.
N. J. Fine, Basic Hypergeometric Series and Applications, Amer. Math. Soc., 1988;
p. 37, Eq. (22.13).
Fristedt, Bert. "The structure of random partitions of large integers."
Transactions of the American Mathematical Society, 337.2 (1993): 703-735 [A classic
paper - N. J. A. Sloane, Aug 27 2018]
H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4,
Cambridge Univ. Press, 1958, p. 90.
G. H. Hardy and S. Ramanujan, Asymptotic formulas in combinatorial analysis, Proc.
London Math. Soc., 17 (1918), 75-.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers (Fifth
edition), Oxford Univ. Press (Clarendon), 1979, 273-296.
D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms,
Section [Link], p. 396.
D. S. Mitrinovic et al., Handbook of Number Theory, Kluwer, Section XIV.1, p. 491.
S. Ramanujan, Collected Papers, Chap. 25, Cambridge Univ. Press 1927 (Proceedings
of the Camb. Phil. Soc., 19 (1919), pp. 207-213).
S. Ramanujan, Collected Papers, Chap. 28, Cambridge Univ. Press 1927 (Proceedings
of the London Math. Soc., 2, 18(1920)).
S. Ramanujan, Collected Papers, Chap. 30, Cambridge Univ. Press 1927 (Mathematische
Zeitschrift, 9 (1921), pp. 147-163).
S. Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea,
NY, 1962. See Table IV on page 308.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 122.
J. E. Roberts, Lure of the Integers, pp. 168-9 MAA 1992.
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).
R. E. Tapscott and D. Marcovich, "Enumeration of Permutational Isomers: The
Porphyrins", Journal of Chemical Education, 55 (1978), 446-447.
Robert M. Young, "Excursions in Calculus", Mathematical Association of America, p.
367.
LINKS
David W. Wilson, Table of n, a(n) for n = 0..10000
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions,
National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972, p.
836. [scanned copy]
Scott Ahlgren and Ken Ono, Addition and Counting: The Arithmetic of Partitions,
Notices of the AMS, 48 (2001) pp. 978-984.
Scott Ahlgren and Ken Ono, Congruence properties for the partition function
Scott Ahlgren and Ken Ono, Congruence properties for the partition function, PNAS,
vol. 98 no. 23, 12882-12884.
Gert Almkvist, Asymptotic formulas and generalized Dedekind sums, Exper. Math., 7
(No. 4, 1998), pp. 343-359.
Gert Almkvist, On the differences of the partition function, Acta Arith., 61.2
(1992), 173-181.
Gert Almkvist and Herbert S. Wilf, On the coefficients in the Hardy-Ramanujan-
Rademacher formula for p(n). [Broken link?]
Gert Almkvist and Herbert S. Wilf, On the coefficients in the Hardy-Ramanujan-
Rademacher formula for p(n), Journal of Number Theory, Vol. 50, No. 2, 1995, pp.
329-334.
Amazing Mathematical Object Factory, Information on Partitions
Edward Anderson, Rubber Relationalism: Smallest Graph-Theoretically Nontrivial
Leibniz Spaces, arXiv:1805.03346 [gr-qc], 2018.
Theresa C. Anderson, Larry Rolen and Ruth Stoehr, Benford's Law for Coefficients of
Modular Forms and Partition Functions, Proceedings of the American Mathematical
Society, Vol. 139, No. 5, May 2011, pp. 1533-1541.
George E. Andrews, Three Aspects of Partitions, Séminaire Lotharingien de
Combinatoire, B25f (1990), 1 p.
George E. Andrews, On a Partition Function of Richard Stanley, The Electronic
Journal of Combinatorics, Volume 11, Issue 2 (2004-6) (The Stanley Festschrift
volume), Research Paper #R1.
George E. Andrews and Ken Ono, Ramanujan's congruences and Dyson's crank
George E. Andrews and Ranjan Roy, Ramanujan's Method in q-series Congruences, The
Electronic Journal of Combinatorics, Volume 4, Issue 2 (1997) (The Wilf Festschrift
volume) > Research Paper #R2.
George E. Andrews, Sumit Kumar Jha, and J. López-Bonilla, Sums of Squares,
Triangular Numbers, and Divisor Sums, Journal of Integer Sequences, Vol. 26 (2023),
Article 23.2.5.
Anonymous, Bibliography on Partitions
Joerg Arndt, Matters Computational (The Fxtbook), section 16.4, pp.344-353.
A. O. L. Atkins and F. G. Garvan, Relations between the ranks and cranks of
partitions, arXiv:math/0208050 [[Link]], 2002.
Alexander Berkovich and Frank G. Garvan, On the Andrews-Stanley Refinement of
Ramanujan's Partition Congruence Modulo 5, arXiv:math/0401012 [[Link]], 2004.
Alexander Berkovich and Frank G. Garvan, On the Andrews-Stanley Refinement of
Ramanujan's Partition Congruence Modulo 5 and Generalizations, arXiv:math/0402439
[[Link]], 2004.
Bruce C. Berndt, Ramanujan's congruences for the partition function modulo 5,7 and
11
Bruce C. Berndt and K. Ono, Ramanujan's Unpublished Manuscript On The Partition And
Tau Functions With Proofs And Commentary
Bruce C. Berndt and K. Ono, Ramanujan's Unpublished Manuscript on the Partition and
Tau Functions with Proofs and Commentary, Séminaire Lotharingien de Combinatoire,
B42c (1999), 63 pp.
Henry Bottomley, Illustration of initial terms
Henry Bottomley, Illustration of initial terms of A000009, A000041 and A047967
Henry Bottomley, Partition and composition calculator [broken link]
Kevin S. Brown, Additive Partitions of Numbers [Broken link]
Kevin S. Brown, Additive Partitions of Numbers [Cached copy of lost web page]
Kevin S. Brown's Mathpages, Computing the Partitions of n
Jan Hendrik Bruinier, Amanda Folsom, Zachary A. Kent and Ken Ono, Recent work on
the partition function
Jan Hendrik Bruinier and Ken Ono, Algebraic formulas for the coefficients of half-
integral weight harmonic weak Maass forms
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ.
Seqs. Vol. 3 (2000), #00.1.5.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating
Functions, thesis, 2002.
Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating
Functions, thesis, 2002 [Local copy, with permission]
Chao-Ping Chen and Hui-Jie Zhang, Padé approximant related to inequalities
involving the constant e and a generalized Carleman-type inequality, Journal of
Inequalities and Applications, 2017.
Yuriy Choliy and Andrew V. Sills, A formula for the partition function that
'counts'
Lynn Chua and Krishanu Roy Sankar, Equipopularity Classes of 132-Avoiding
Permutations, The Electronic Journal of Combinatorics 21(1)(2014), #P59. [Cited by
Shalosh B. Ekhad and Doron Zeilberger, 2014] - N. J. A. Sloane, Mar 31 2014
CombOS - Combinatorial Object Server, Generate integer partitions
Jimena Davis and Elizabeth Perez, Computations Of The Partition Function, p(n)
Stephen DeSalvo and Igor Pak, Log-Concavity of the Partition Function,
arXiv:1310.7982 [[Link]], 2013-2014.
F. J. Dyson, Some guesses in the theory of partitions, Eureka (Cambridge) 8 (1944),
10-15.
Shalosh B. Ekhad and Doron Zeilberger, Automatic Proofs of Asymptotic Abnormality
(and much more!) of Natural Statistics Defined on Catalan-Counted Combinatorial
Families, arXiv:1403.5664 [[Link]], 2014.
Wenjie Fang, Hsien-Kuei Hwang, and Mihyun Kang, Phase transitions from exp(n^(1/2))
to exp(n^(2/3)) in the asymptotics of banded plane partitions, arXiv:2004.08901
[[Link]], 2020.
FindStat - Combinatorial Statistic Finder, Integer partitions
Nathan J. Fine, Some New Results On Partitions
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 41.
Amanda Folsom, Zachary A. Kent and Ken Ono, l-adic properties of the partition
function, in press.
Amanda Folsom, Zachary A. Kent and Ken Ono, l-adic properties of the partition
function, Adv. Math. 229 (2012) 1586.
B. Forslund, Partitioning Integers
Harald Fripertinger, Partitions of an Integer
GEO magazine, Zahlenspalterei
James Grime and Brady Haran, Partitions, Numberphile video (2016).
Harald Grosse, Alexander Hock, and Raimar Wulkenhaar, A Laplacian to compute
intersection numbers on M_(g,n) and correlation functions in NCQFT,
arXiv:1903.12526 [math-ph], 2019.
A. Hassen and T. J. Olsen, Playing With Partitions On The Computer
Tian-Xiao He, Peter J.-S. Shiue, Zihan Nie, and Minghao Chen, Recursive sequences
and Girard-Waring identities with applications in sequence transformation,
Electronic Research Archive (2020) Vol. 28, No. 2, 1049-1062.
Alexander D. Healy, Partition Identities
Ferdinand Ihringer, Remarks on the Erdős Matching Conjecture for Vector Spaces,
arXiv:2002.06601 [[Link]], 2020.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 61 and
Encyclopedia of Combinatorial Structures 74
Fredrik Johansson, Fast arbitrary-precision evaluation of special functions in the
Arb library, OPSFA13, NIST, June 2015, page 15.
Jonthan M. Kane, Distribution of orders of Abelian groups, Math. Mag., 49 (1976),
132-135.
Jerome Kelleher and Barry O'Sullivan, Generating All Partitions: A Comparison Of
Two Encodings, arXiv:0909.2331 [[Link]], 2009-2014.
Erica Klarreich, Pieces of Numbers: A proof brings closure to a dramatic tale of
partitions and primes, Science News, Week of Jun 18, 2005; Vol. 167, No. 25, p.
392.
Martin Klazar, What is an answer? — remarks, results and problems on PIO formulas
in combinatorial enumeration, part I, arXiv:1808.08449 [[Link]], 2018.
Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the
convolution of generating functions, arXiv:1509.08708 [[Link]], Sep 30 2015.
J. Laurendi, Partitions of Integers
Oleg Lazarev, Matt Mizuhara, and Ben Reid, Some Results in Partitions, Plane
Partitions, and Multipartitions
Li Wenwei, Estimation of the Partition Number: After Hardy and Ramanujan, arXiv
preprint arXiv:1612.05526 [[Link]], 2016-2018.
T. Lockette, Explore Magazine, Path To Partitions
Jerome Malenfant, Finite, Closed-form Expressions for the Partition Function and
for Euler, Bernoulli, and Stirling Numbers, arXiv:1103.1585 [[Link]], 2011.
Dr. Math, Partitioning the Integers and Partitioning an Integer
M. MacMahon, Collected Papers of Ramanujan, Table for p(n);n=1 through 200
S. Markovski and M. Mihova, An explicit formula for computing the partition numbers
p(n), Math. Balkanica 22 (2008) 101-119 MR2467361
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting
numbers for cylinders...", letter to N. J. A. Sloane, N. D.
Johannes W. Meijer, Euler's ship on the Pentagonal Sea, pdf and jpg.
Johannes W. Meijer and Manuel Nepveu, Euler's ship on the Pentagonal Sea, Acta
Nova, Volume 4, No.1, December 2008. pp. 176-187.
Mircea Merca, Fast algorithm for generating ascending compositions,
arXiv:1903.10797 [[Link]], 2019.
Mircea Merca and M. D. Schmidt, The partition function p(n) in terms of the
classical Mobius function, Ramanujan J. 49 (1) (2019) 87-96.
István Mező, Several special values of Jacobi theta functions arXiv:1106.2703v3
[[Link]], 2011-2013.
Gerard P. Michon, Table of partition function p(n) (n=0 through 4096)
Gerard P. Michon, Partition function
G. A. Miller, Number of the abelian groups of a given order
Hisanori Mishima, Factorization of Partition Numbers
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in
Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated,
scanned copy]
D. J. Newman, A simplified proof of the partition formula, Michigan Math. J. 9:3
(1962), pp. 193-287.
Jean-Louis Nicolas, Sur les entiers N pour lesquels il y a beaucoup de groupes
abéliens d’ordre N, Annales de l'Institut Fourier, Tome 28 (1978) no. 4, p. 1-16.
OEIS Wiki, Sorting numbers
Ken Ono, Arithmetic of the partition function
Ken Ono, Parity of the partition function, Electron. Res. Announc. Amer. Math. Soc.
1 (1995), 35-42.
Ken Ono, Distribution of the partition function modulo m, Annals Math. 151 (2000),
293-307.
Ken Ono (with J. Bruinier, A. Folsom and Z. Kent), Emory University, Adding and
counting
T. J. Osler, Playing with Partitions on the Computer
I. Pak, Partition bijections, a survey, Ramanujan J. 12 (2006) 5-75.
Michael Penn, Rogers-Ramanujan Identities, Youtube playlist, 2019, 2020.
I. Peterson, The Power Of Partitions
Götz Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7
(2004), Article 04.3.2.
Michel Planat, Quantum 1/f Noise in Equilibrium: from Planck to Ramanujan,
arXiv:math-ph/0307033, 2003.
M. Presern, Some Results On Partitions
W. A. Pribitkin, Revisiting Rademacher's Formula for the Partition Function p(n),
The Ramanujan Journal 4(4) 2000.
PYTHAGORAS, Ramanujan and The Partition Function(Text in Dutch)
Srinivasa Ramanujan, Some Properties Of p(n), The Number Of Partitions Of n
Srinivasa Ramanujan, Congruence Properties Of Partitions
Srinivasa Ramanujan, Congruence Properties Of Partitions
Srinivasa Ramanujan and G. H. Hardy, Une formule asymptotique pour le nombre de
partitions de n
J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960),
473-478.
J. D. Rosenhouse, Partitions of Integers
J. D. Rosenhouse, Solutions to Problems
Kate Rudolph, Pattern Popularity in 132-Avoiding Permutations, The Electronic
Journal of Combinatorics 20(1)(2013), #P8. [Cited by Shalosh B. Ekhad and Doron
Zeilberger, 2014] - N. J. A. Sloane, Mar 31 2014
F. Ruskey, Generate Numerical Partitions
F. Ruskey, The first 284547 partition numbers (52MB compressed file, archived link)
M. Savic, The Partition Function and Ramanujan's 5k+4 Congruence
Zhumagali Shomanov, Combinatorial formula for the partition function,
arXiv:1508.03173 [[Link]], 2015.
T. Sillke, Number of integer partitions
R. P. Stanley, A combinatorial miscellany
Cormac O'Sullivan, Detailed asymptotic expansions for partitions into powers,
arXiv:2205.13468 [[Link]], 2022-3.
Yi Wang and Bao-Xuan Zhu, Proofs of some conjectures on monotonicity of number-
theoretic and combinatorial sequences, arXiv preprint arXiv:1303.5595 [[Link]],
2013.
R. L. Weaver, New Congruences for the Partition Function, The Ramanujan Journal
5(1) 2001.
Eric Weisstein's World of Mathematics, Partition, Partition Function P, q-
Pochhammer Symbol, and Ramanujan's Identity
West Sussex Grid for Learning, Multicultural Mathematics, Ramanujan's Partition of
Numbers
Thomas Wieder, Comment on A000041
Wikipedia, Partition (number theory)
H. S. Wilf, Lectures on Integer Partitions
Wolfram Research, Generating functions of p(n)
D. J. Wright, Partitions [broken link]
Doron Zeilberger, Noam Zeilberger, Two Questions about the Fractional Counting of
Partitions, arXiv:1810.12701 [[Link]], 2018.
Robert M. Ziff, On Cardy's formula for the critical crossing probability in 2d
percolation, J. Phys. A. 28, 1249-1255 (1995).
Index entries for "core" sequences
Index entries for related partition-counting sequences
Index entries for expansions of Product_{k >= 1} (1-x^k)^m
Index entries for sequences related to rooted trees
Index entries for sequences related to Benford's law
FORMULA
G.f.: Product_{k>0} 1/(1-x^k) = Sum_{k>= 0} x^k Product_{i = 1..k} 1/(1-x^i) = 1 +
Sum_{k>0} x^(k^2)/(Product_{i = 1..k} (1-x^i))^2.
G.f.: 1 + Sum_{n>=1} x^n/(Product_{k>=n} 1-x^k). - Joerg Arndt, Jan 29 2011
a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the
sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the
sign of the k-th term is (-1)^([(k+1)/2]). See A001318 for a good way to remember
this!
a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k), where sigma(k) is the sum of
divisors of k (A000203).
a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3)) as n -> infinity (Hardy and
Ramanujan). See A050811.
a(n) = a(0)*b(n) + a(1)*b(n-2) + a(2)*b(n-4) + ... where b = A000009.
From Jon E. Schoenfield, Aug 17 2014: (Start)
It appears that the above approximation from Hardy and Ramanujan can be refined as
a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3 + c0 + c1/n^(1/2) + c2/n + c3/n^(3/2) +
c4/n^2 + ...)), where the coefficients c0 through c4 are approximately
c0 = -0.230420145062453320665537
c1 = -0.0178416569128570889793
c2 = 0.0051329911273
c3 = -0.0011129404
c4 = 0.0009573,
as n -> infinity. (End)
From Vaclav Kotesovec, May 29 2016 (c4 added Nov 07 2016): (Start)
c0 = -0.230420145062453320665536704197233... = -1/36 - 2/Pi^2
c1 = -0.017841656912857088979502135349949... = 1/(6*sqrt(6)*Pi) - sqrt(3/2)/Pi^3
c2 = 0.005132991127342167594576391633559... = 1/(2*Pi^4)
c3 = -0.001112940489559760908236602843497... = 3*sqrt(3/2)/(4*Pi^5) -
5/(16*sqrt(6)*Pi^3)
c4 = 0.000957343284806972958968694349196... = 1/(576*Pi^2) - 1/(24*Pi^4) +
93/(80*Pi^6)
a(n) ~ exp(Pi*sqrt(2*n/3))/(4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi +
Pi/(24*sqrt(6)))/sqrt(n) + (1/16 + Pi^2/6912)/n).
a(n) ~ exp(Pi*sqrt(2*n/3) - (sqrt(3/2)/Pi + Pi/(24*sqrt(6)))/sqrt(n) + (1/24 -
3/(4*Pi^2))/n) / (4*sqrt(3)*n).
(End)
a(n) < exp( (2/3)^(1/2) Pi sqrt(n) ) (Ayoub, p. 197).
G.f.: Product_{m>=1} (1+x^m)^A001511(m). - Vladeta Jovovic, Mar 26 2004
a(n) = Sum_{i=0..n-1} P(i, n-i), where P(x, y) is the number of partitions of x
into at most y parts and P(0, y)=1. - Jon Perry, Jun 16 2003
G.f.: Product_{i>=1} Product_{j>=0} (1+x^((2i-1)*2^j))^(j+1). - Jon Perry, Jun 06
2004
G.f. e^(Sum_{k>0} (x^k/(1-x^k)/k)). - Franklin T. Adams-Watters, Feb 08 2006
a(n) = A114099(9*n). - Reinhard Zumkeller, Feb 15 2006
Euler transform of all 1's sequence (A000012). Weighout transform of A001511. -
Franklin T. Adams-Watters, Mar 15 2006
a(n) = A027187(n) + A027193(n) = A000701(n) + A046682(n). - Reinhard Zumkeller, Apr
22 2006
A026820(a(n),n) = A134737(n) for n > 0. - Reinhard Zumkeller, Nov 07 2007
Convolved with A152537 gives A000079, powers of 2. - Gary W. Adamson, Dec 06 2008
a(n) = A026820(n, n); a(n) = A108949(n) + A045931(n) + A108950(n) = A130780(n) +
A171966(n) - A045931(n) = A045931(n) + A171967(n). - Reinhard Zumkeller, Jan 21
2010
a(n) = Tr(n)/(24*n-1) = A183011(n)/A183010(n), n>=1. See the Bruinier-Ono paper in
the Links. - Omar E. Pol, Jan 23 2011
From Jerome Malenfant, Feb 14 2011: (Start)
a(n) = determinant of the n X n Toeplitz matrix:
1 -1
1 1 -1
0 1 1 -1
0 0 1 1 -1
-1 0 0 1 1 -1
. . .
d_n d_(n-1) d_(n-2)...1
where d_q = (-1)^(m+1) if q = m(3m-1)/2 = p_m, the m-th generalized pentagonal
number (A001318), otherwise d_q = 0. Note that the 1's run along the diagonal and
the -1's are on the superdiagonal. The (n-1) row (not written) would end with ... 1
-1. (End)
Empirical: let F*(x) = Sum_{n=0..infinity} p(n)*exp(-Pi*x*(n+1)), then F*(2/5) =
1/sqrt(5) to a precision of 13 digits.
F*(4/5) = 1/2+3/2/sqrt(5)-sqrt(1/2*(1+3/sqrt(5))) to a precision of 28 digits.
These are the only values found for a/b when a/b is from F60, Farey fractions up to
60. The number for F*(4/5) is one of the real roots of 25*x^4 - 50*x^3 - 10*x^2 -
10*x + 1. Note here the exponent (n+1) compared to the standard notation with n
starting at 0. - Simon Plouffe, Feb 23 2011
The constant (2^(7/8)*GAMMA(3/4))/(exp(Pi/6)*Pi^(1/4)) = 1.0000034873... when
expanded in base exp(4*Pi) will give the first 52 terms of a(n), n>0, the precision
needed is 300 decimal digits. - Simon Plouffe, Mar 02 2011
a(n) = A035363(2n). - Omar E. Pol, Nov 20 2009
G.f.: A(x)=1+x/(G(0)-x); G(k) = 1 + x - x^(k+1) - x*(1-x^(k+1))/G(k+1); (continued
fraction Euler's kind, 1-step ). - Sergei N. Gladkovskii, Jan 25 2012
Convolution of A010815 with A000712. - Gary W. Adamson, Jul 20 2012
G.f.: 1 + x*(1 - G(0))/(1-x) where G(k) = 1 - 1/(1-x^(k+1))/(1-x/(x-1/G(k+1) ));
(continued fraction). - Sergei N. Gladkovskii, Jan 22 2013
G.f.: Q(0) where Q(k) = 1 + x^(4*k+1)/( (x^(2*k+1)-1)^2 - x^(4*k+3)*(x^(2*k+1)-
1)^2/( x^(4*k+3) + (x^(2*k+2)-1)^2/Q(k+1) )); (continued fraction). - Sergei N.
Gladkovskii, Feb 16 2013
a(n) = 24*spt(n) + 12*N_2(n) - Tr(n) = 24*A092269(n) + 12*A220908(n) - A183011(n),
n >= 1. - Omar E. Pol, Feb 17 2013
G.f.: 1/(x; x)_{inf} where (a; q)_k is the q-Pochhammer symbol. - Vladimir
Reshetnikov, Apr 24 2013
a(n) = A066186(n)/n, n >= 1. - Omar E. Pol, Aug 16 2013
From Peter Bala, Dec 23 2013: (Start)
a(n-1) = Sum_{parts k in all partitions of n} mu(k), where mu(k) is the
arithmetical Möbius function (see A008683).
Let P(2,n) denote the set of partitions of n into parts k >= 2. Then a(n-2) = -
Sum_{parts k in all partitions in P(2,n)} mu(k).
n*( a(n) - a(n-1) ) = Sum_{parts k in all partitions in P(2,n)} k (see A138880).
Let P(3,n) denote the set of partitions of n into parts k >= 3. Then
a(n-3) = (1/2)*Sum_{parts k in all partitions in P(3,n)} phi(k), where phi(k) is
the Euler totient function (see A000010). Using this result and Mertens's theorem
on the average order of the phi function, we can find an approximate 3-term
recurrence for the partition function: a(n) ~ a(n-1) + a(n-2) + (Pi^2/(3*n) -
1)*a(n-3). For example, substituting the values a(47) = 124754, a(48) = 147273 and
a(49) = 173525 into the recurrence gives the approximation a(50) ~ 204252.48...
compared with the true value a(50) = 204226. (End)
a(n) = Sum_{k=1..n+1} (-1)^(n+1-k)*A000203(k)*A002040(n+1-k). - Mircea Merca, Feb
27 2014
a(n) = A240690(n) + A240690(n+1), n >= 1. - Omar E. Pol, Mar 16 2015
From Gary W. Adamson, Jun 22 2015: (Start)
A production matrix for the sequence with offset 1 is M, an infinite n x n matrix
of the following form:
a, 1, 0, 0, 0, 0, ...
b, 0, 1, 0, 0, 0, ...
c, 0, 0, 1, 0, 0, ...
d, 0, 0, 0, 1, 0, ...
.
.
... such that (a, b, c, d, ...) is the signed version of A080995 with offset 1:
(1,1,0,0,-1,0,-1,...)
and a(n) is the upper left term of M^n.
This operation is equivalent to the g.f. (1 + x + 2x^2 + 3x^3 + 5x^4 + ...) = 1/(1
- x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + ...). (End)
G.f.: x^(1/24)/eta(log(x)/(2 Pi i)). - Thomas Baruchel, Jan 09 2016, after Michael
Somos (after Richard Dedekind).
a(n) = Sum_{k=-inf..+inf} (-1)^k a(n-k(3k-1)/2) with a(0)=1 and a(negative)=0. The
sum can be restricted to the (finite) range from k = (1-sqrt(1-24n))/6 to
(1+sqrt(1-24n))/6), since all terms outside this range are zero. - Jos Koot, Jun 01
2016
G.f.: (conjecture) (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) is A000009:
(1, 1, 1, 2, 2, 3, 4, ...). - Gary W. Adamson, Sep 18 2016; Doron Zeilberger
observed today that "This follows immediately from Euler's formula 1/(1-z) =
(1+z)*(1+z^2)*(1+z^4)*(1+z^8)*..." Gary W. Adamson, Sep 20 2016
a(n) ~ 2*Pi * BesselI(3/2, sqrt(24*n-1)*Pi/6) / (24*n-1)^(3/4). - Vaclav Kotesovec,
Jan 11 2017
G.f.: Product_{k>=1} (1 + x^k)/(1 - x^(2*k)). - Ilya Gutkovskiy, Jan 23 2018
a(n) = p(1, n) where p(k, n) = p(k+1, n) + p(k, n-k) if k < n, 1 if k = n, and 0 if
k > n. p(k, n) is the number of partitions of n into parts >= k. - Lorraine Lee,
Jan 28 2020
Sum_{n>=1} 1/a(n) = A078506. - Amiram Eldar, Nov 01 2020
Sum_{n>=0} a(n)/2^n = A065446. - Amiram Eldar, Jan 19 2021
From Simon Plouffe, Mar 12 2021: (Start)
Sum_{n>=0} a(n)/exp(Pi*n) = 2^(3/8)*Gamma(3/4)/(Pi^(1/4)*exp(Pi/24)).
Sum_{n>=0} a(n)/exp(2*Pi*n) = 2^(1/2)*Gamma(3/4)/(Pi^(1/4)*exp(Pi/12)).
[corrected by Vaclav Kotesovec, May 12 2023] (End)
[These are the reciprocals of phi(exp(-Pi)) (A259148) and phi(exp(-2*Pi))
(A259149), where phi(q) is the Euler modular function. See B. C. Berndt (RLN, Vol.
V, p. 326), and formulas (13) and (14) in I. Mező, 2013. - Peter Luschny, Mar 13
2021]
a(n) = A000009(n) + A035363(n) + A006477(n). - R. J. Mathar, Feb 01 2022
a(n) = A008284(2*n,n) is also the number of partitions of 2n into n parts. - Ryan
Brooks, Jun 11 2022
a(n) = A000700(n) + A330644(n). - R. J. Mathar, Jun 15 2022
a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*n*sqrt(3)) * (1 + Sum_{r>=1} w(r)/n^(r/2)), where
w(r) = 1/(-4*sqrt(6))^r * Sum_{k=0..(r+1)/2} binomial(r+1,k) * (r+1-k) / (r+1-2*k)!
* (Pi/6)^(r-2*k) [Cormac O'Sullivan, 2023, pp. 2-3]. - Vaclav Kotesovec, Mar 15
2023
EXAMPLE
a(5) = 7 because there are seven partitions of 5, namely: {1, 1, 1, 1, 1}, {2, 1,
1, 1}, {2, 2, 1}, {3, 1, 1}, {3, 2}, {4, 1}, {5}. - Bob Selcoe, Jul 08 2014
G.f. = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 11*x^6 + 15*x^7 + 22*x^8 + ...
G.f. = 1/q + q^23 + 2*q^47 + 3*q^71 + 5*q^95 + 7*q^119 + 11*q^143 + 15*q^167 + ...
From Gregory L. Simay, Nov 08 2015: (Start)
There are up to a(4)=5 segmented partitions of the partitions of n with exactly 4
parts. They are a(n,4, <4>), a(n,4,<3,1>), a(n,4,<2,2>), a(n,4,<2,1,1>),
a(n,4,<1,1,1,1>).
The partition 8,8,8,8 is counted in a(32,4,<4>).
The partition 9,9,9,5 is counted in a(32,4,<3,1>).
The partition 11,11,5,5 is counted in a(32,4,<2,2>).
The partition 13,13,5,1 is counted in a(32,4,<2,1,1>).
The partition 14,9,6,3 is counted in a(32,4,<1,1,1,1>).
a(n odd,4,<2,2>) = 0.
a(12, 6, <2,2,2>) = a(6,3,<1,1,1>) = a(6-3,3) = a(3,3) = 1. The lone partition is
3,3,2,2,1,1.
(End)
MAPLE
A000041 := n -> combinat:-numbpart(n): [seq(A000041(n), n=0..50)]; # Warning: Maple
10 and 11 give incorrect answers in some cases: A110375.
spec := [B, {B=Set(Set(Z, card>=1))}, unlabeled ];
[seq(combstruct[count](spec, size=n), n=0..50)];
with(combstruct):ZL0:=[S, {S=Set(Cycle(Z, card>0))}, unlabeled]: seq(count(ZL0,
size=n), n=0..45); # Zerinvary Lajos, Sep 24 2007
G:={P=Set(Set(Atom, card>0))}: combstruct[gfsolve](G, labeled, x);
seq(combstruct[count]([P, G, unlabeled], size=i), i=0..45); # Zerinvary Lajos, Dec
16 2007
# Using the function EULER from Transforms (see link at the bottom of the page).
1, op(EULER([seq(1, n=1..49)])); # Peter Luschny, Aug 19 2020
MATHEMATICA
Table[ PartitionsP[n], {n, 0, 45}]
a[ n_] := SeriesCoefficient[ q^(1/24) / DedekindEta[ Log[q] / (2 Pi I)], {q, 0,
n}]; (* Michael Somos, Jul 11 2011 *)
a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^k, {k, n}], {x, 0, n}]; (* Michael
Somos, Jul 11 2011 *)
CoefficientList[1/QPochhammer[q] + O[q]^100, q] (* Jean-François Alcover, Nov 25
2015 *)
PROG
(Magma) a:= func< n | NumberOfPartitions(n) >; [ a(n) : n in [0..10]];
(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
(PARI) /* The Hardy-Ramanujan-Rademacher exact formula in PARI is as follows (this
is no longer necessary since it is now built in to the numbpart command): */
Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b);
(sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c))
L(n, q) = if(q==1, 1, sum(h=1, q-1, if(gcd(h, q)>1, 0, cos((g(h, q)-2*h*n)*Pi/q))))
g(h, q) = if(q<3, 0, sum(k=1, q-1, k*(frac(h*k/q)-1/2)))
part(n) = round(sum(q=1, max(5, 0.5*sqrt(n)), L(n, q)*Psi(n, q)))
/* Ralf Stephan, Nov 30 2002, fixed by Vaclav Kotesovec, Apr 09 2018 */
(PARI) {a(n) = numbpart(n)};
(PARI) {a(n) = if( n<0, 0, polcoeff( sum( k=1, sqrtint(n), x^k^2 / prod( i=1, k, 1
- x^i, 1 + x * O(x^n))^2, 1), n))};
(PARI) f(n)= my(v, i, k, s, t); v=vector(n, k, 0); v[n]=2; t=0; while(v[1]<n, i=2;
while(v[i]==0, i++); v[i]--; s=sum(k=i, n, k*v[k]); while(i>1, i--; s+=i*(v[i]=(n-
s)\i)); t++); t \\ Thomas Baruchel, Nov 07 2005
(PARI) a(n)=if(n<0, 0, polcoeff(exp(sum(k=1, n, x^k/(1-x^k)/k, x*O(x^n))), n)) \\
Joerg Arndt, Apr 16 2010
(MuPAD) combinat::partitions::count(i) $i=0..54 // Zerinvary Lajos, Apr 16 2007
(Sage) [number_of_partitions(n) for n in range(46)] # Zerinvary Lajos, May 24 2009
(Sage)
@CachedFunction
def A000041(n):
if n == 0: return 1
S = 0; J = n-1; k = 2
while 0 <= J:
T = A000041(J)
S = S+T if is_odd(k//2) else S-T
J -= k if is_odd(k) else k//2
k += 1
return S
[A000041(n) for n in range(50)] # Peter Luschny, Oct 13 2012
(Sage) # uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(1, 0)
b = EulerTransform(a)
print([b(n) for n in range(50)]) # Peter Luschny, Nov 11 2020
(Haskell)
import [Link] (memo2, integral)
a000041 n = a000041_list !! n
a000041_list = map (p' 1) [0..] where
p' = memo2 integral integral p
p _ 0 = 1
p k m = if m < k then 0 else p' k (m - k) + p' (k + 1) m
-- Reinhard Zumkeller, Nov 03 2015, Nov 04 2013
(Maxima) num_partitions(60, list); /* Emanuele Munarini, Feb 24 2014 */
(GAP) List([1..10], n->Size(OrbitsDomain(SymmetricGroup(IsPermGroup, n),
SymmetricGroup(IsPermGroup, n), \^))); # Attila Egri-Nagy, Aug 15 2014
(Perl) use ntheory ":all"; my @p = map { partitions($_) } 0..100; say "[@p]"; #
Dana Jacobsen, Sep 06 2015
(Racket)
#lang racket
; SUM(k, -inf, +inf) (-1)^k p(n-k(3k-1)/2)
; For k outside the range (1-(sqrt(1-24n))/6 to (1+sqrt(1-24n))/6) argument n-k(3k-
1)/2 < 0.
; Therefore the loops below are finite. The hash avoids repeated identical
computations.
(define (p n) ; Nr of partitions of n.
(hash-ref h n
(λ ()
(define r
(+
(let loop ((k 1) (n (sub1 n)) (s 0))
(if (< n 0) s
(loop (add1 k) (- n (* 3 k) 1) (if (odd? k) (+ s (p n)) (- s (p n))))))
(let loop ((k -1) (n (- n 2)) (s 0))
(if (< n 0) s
(loop (sub1 k) (+ n (* 3 k) -2) (if (odd? k) (+ s (p n)) (- s (p n))))))))
(hash-set! h n r)
r)))
(define h (make-hash '((0 . 1))))
; (for ((k (in-range 0 50))) (printf "~s, " (p k))) runs in a moment.
; Jos Koot, Jun 01 2016
(Python)
from [Link] import npartitions
print([npartitions(i) for i in range(101)]) # Indranil Ghosh, Mar 17 2017
(Julia) # DedekindEta is defined in A000594
A000041List(len) = DedekindEta(len, -1)
A000041List(50) |> println # Peter Luschny, Mar 09 2018
CROSSREFS
Cf. A000009, A000079, A000203, A001318, A008284, A065446, A078506, A113685,
A132311, A145006, A145007, A147843, A152537, A168532, A173238, A173239, A173241,
A173304, A174065, A174066, A174068, A176202, A000248.
For successive differences see A002865, A053445, A072380, A081094, A081095.
Antidiagonal sums of triangle A092905. a(n) = A054225(n,0).
Boustrophedon transforms: A000733, A000751.
Cf. A167376 (complement), A061260 (multisets), A000700 (self-conjug), A330644 (not
self-conj).
KEYWORD
core,easy,nonn,nice,changed
AUTHOR
N. J. A. Sloane
EXTENSIONS
Additional comments from Ola Veshta (olaveshta(AT)[Link]), Feb 28 2001
Additional comments from Dan Fux ([Link](AT)[Link] or
danfux(AT)[Link]), Apr 07 2001
STATUS
approved