Displaying 1-10 of 60 results found.
a(n) = |{0 < k < n: p = phi(k)/2 + phi(n-k)/12 + 1 and A047967(p) are both prime}|.
+20
5
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 2, 0, 0, 2, 1, 0, 1, 0, 3, 1, 0, 1, 1, 1, 2, 1, 2, 0, 1, 2, 2, 2, 1, 2, 1, 1, 3, 1, 1, 4, 2, 0, 1, 3, 2, 2, 0, 2, 2, 4, 2, 3, 0, 3, 2
COMMENTS
Conjecture: a(n) > 0 for all n > 98.
We have verified this for n up to 36000.
The conjecture implies that there are infinitely many primes p with A047967(p) prime.
EXAMPLE
a(36) = 1 since phi(23)/2 + phi(13)/12 + 1 = 13 with A047967(13) = 83 prime. a(71) = 1 since phi(43)/2 + phi(28)/12 + 1 = 23 with A047967(23) = 1151 prime.
MATHEMATICA
pq[n_]:=PrimeQ[n]&&PrimeQ[PartitionsP[n]-PartitionsQ[n]]
f[n_, k_]:=EulerPhi[k]/2+EulerPhi[n-k]/12+1
a[n_]:=Sum[If[pq[f[n, k]], 1, 0], {k, 1, n-1}]
Table[a[n], {n, 1, 100}]
2, 3, 4, 13, 18, 23, 44, 52, 54, 67, 82, 93, 139, 155, 166, 185, 196, 249, 299, 333, 382, 559, 574, 911, 939, 1076, 1077, 1386, 1707, 1710, 1872, 2041, 2120, 2172, 2234, 2810, 3272, 3407, 3442, 3469, 3551, 3657, 3694, 4185, 4282, 4469, 4554, 5273, 5315, 5729
COMMENTS
According to the conjecture in A236439, this sequence should have infinitely many terms.
MATHEMATICA
pq[n_]:=PrimeQ[PartitionsQ[n]^2+(PartitionsP[n]-PartitionsQ[n])^2]
n=0; Do[If[pq[m], n=n+1; Print[n, " ", m]], {m, 1, 10000}]
a(n) = |{0 < k <= n: k*p(n)*q(n)*r(n) - 1 is prime}|, where p(.), q(.) and r(.) are given by A000041, A000009 and A047967 respectively.
+20
4
0, 1, 3, 3, 4, 3, 2, 5, 4, 4, 2, 3, 2, 3, 5, 6, 3, 4, 2, 3, 5, 4, 1, 6, 2, 7, 3, 5, 5, 3, 5, 8, 7, 1, 7, 3, 8, 5, 11, 7, 7, 2, 6, 7, 3, 7, 7, 5, 5, 9, 7, 7, 4, 4, 6, 5, 9, 7, 8, 11, 4, 5, 6, 8, 5, 10, 5, 6, 9, 7, 10, 6, 5, 5, 10, 9, 8, 3, 4, 1
COMMENTS
Conjecture: (i) a(n) > 0 for all n > 1. If n > 1 is not equal to 25, then k*p(n)*q(n)*r(n) + 1 is prime for some k = 1, ..., n.
(ii) For any integer n > 1, there is a number k among 1, ..., n with k*p(n)*q(n) - 1 (or k*p(n)*q(n) + 1) prime.
(iii) For each n > 1, there is a positive integer k < n with k*p(n) + 1 (or k*q(n) + 1) prime. If n > 1, then k*p(n) - 1 is prime for some k = 1, ..., n. If n > 2, then k*q(n) - 1 is prime for some 0 < k < n.
We have verified that a(n) > 0 for all n = 2, ..., 83000.
EXAMPLE
a(2) = 1 since 2*p(2)*q(2)*r(2) - 1 = 2*2*1*1 - 1 = 3 is prime.
a(23) = 1 since 12*p(23)*q(23)*r(23) - 1 = 12*1255*104*1151 - 1 = 1802742239 is prime.
MATHEMATICA
p[n_]:=PartitionsP[n]
q[n_]:=PartitionsQ[n]
f[n_]:=p[n]*q[n]*(p[n]-q[n])
a[n_]:=Sum[If[PrimeQ[k*f[n]-1], 1, 0], {k, 1, n}]
Table[a[n], {n, 1, 80}]
Primes p with A047967(p) also prime.
+20
3
13, 23, 43, 53, 71, 83, 107, 257, 269, 313, 1093, 2659, 2851, 3527, 8243, 20173, 20717, 24329, 26161, 26237, 31583, 53611, 60719, 74717, 83401, 118259, 118369, 130817, 133811, 145109, 152381, 169111, 178613, 183397, 205963
COMMENTS
According to the conjecture in A236417, this sequence should have infinitely many terms.
EXAMPLE
a(1) = 13 with 13 and A047967(13) = 83 both prime.
MATHEMATICA
pq[n_]:=PrimeQ[n]&&PrimeQ[PartitionsP[n]-PartitionsQ[n]]
n=0; Do[If[pq[m], n=n+1; Print[n, " ", m]], {m, 1, 10000}]
Select[Prime[Range[20000]], PrimeQ[PartitionsP[#]-PartitionsQ[#]]&] (* Harvey P. Dale, Jan 02 2022 *)
CROSSREFS
Cf. A000040, A047967, A234530, A234569, A234644, A235344, A235346, A236413, A236417, A236419, A236440.
a(n) = |{0 < k <= n: p(n)*q(k)*r(k) + 1 is prime}|, where p(.), q(.) and r(.) are given by A000041, A000009 and A047967 respectively.
+20
3
0, 1, 1, 2, 1, 2, 4, 3, 4, 3, 7, 4, 5, 6, 4, 4, 6, 4, 7, 1, 4, 6, 2, 8, 6, 6, 5, 4, 5, 4, 8, 5, 9, 3, 4, 2, 3, 10, 5, 11, 5, 10, 5, 6, 3, 6, 8, 7, 9, 6, 6, 3, 10, 3, 9, 9, 6, 10, 8, 8, 7, 4, 6, 6, 6, 5, 3, 9, 4, 8, 12, 5, 2, 8, 8, 3, 6, 10, 9, 9
COMMENTS
Conjecture: (i) a(n) > 0 for all n > 1, and a(n) = 1 only for n = 2, 3, 5, 20. If n > 2, then p(n)*q(k)*r(k) - 1 is prime for some k = 1, ..., n.
(ii) If n > 2 is not equal to 22, then p(n)*q(n)*q(k) - 1 is prime for some k = 1, ..., n. If n > 13, then p(n)*q(k)*q(n-k) - 1 is prime for some 1 < k < n/2.
EXAMPLE
a(5) = 1 since p(5)*q(4)*r(4) + 1 = 7*2*3 + 1 = 43 is prime.
a(20) = 1 since p(20)*q(13)*r(13) + 1 = 627*18*83 + 1 = 936739 is prime.
MATHEMATICA
p[n_, k_]:=PrimeQ[PartitionsP[n]*PartitionsQ[k]*(PartitionsP[k]-PartitionsQ[k])+1]
a[n_]:=Sum[If[p[n, k], 1, 0], {k, 1, n}]
Table[a[n], {n, 1, 80}]
a(n) = |{0 < k < n-2: A000009(m)^2 + A047967(m)^2 is prime with m = k + phi(n-k)/2}|, where phi(.) is Euler's totient function.
+20
2
0, 0, 0, 1, 2, 3, 3, 2, 2, 2, 1, 1, 1, 1, 2, 2, 1, 1, 4, 2, 3, 2, 3, 5, 4, 3, 2, 6, 6, 4, 2, 1, 8, 4, 4, 3, 1, 6, 4, 3, 3, 3, 3, 3, 4, 4, 5, 3, 4, 5, 3, 3, 7, 4, 5, 5, 5, 11, 7, 6, 3, 7, 8, 6, 5, 5, 8, 6, 7, 11, 7, 5, 7, 8, 7, 7, 5, 10, 10, 5, 6, 8, 6, 10, 8, 6, 8, 11, 10, 6, 10, 7, 7, 9, 4, 9, 11, 8, 13, 7
COMMENTS
Conjecture: a(n) > 0 for all n > 3.
We have verified this for n up to 50000.
The conjecture implies that there are infinitely many positive integers m with A000009(m)^2 + A047967(m)^2 prime. See A236440 for such numbers m.
EXAMPLE
a(14) = 1 since 2 + phi(12)/2 = 4 with A000009(4)^2 + A047967(4)^2 = 2^2 + 3^2 = 13 prime. a(17) = 1 since 10 + phi(7)/2 = 13 with A000009(13)^2 + A047967(13)^2 = 18^2 + 83^2 = 7213 prime.
MATHEMATICA
p[n_]:=PrimeQ[PartitionsQ[n]^2+(PartitionsP[n]-PartitionsQ[n])^2]
a[n_]:=Sum[If[p[k+EulerPhi[n-k]/2], 1, 0], {k, 1, n-3}]
Table[a[n], {n, 1, 100}]
Number of ordered ways to write n = k + m with k > 0 and m > 0 such that A000009(k) + A047967(m) is prime.
+20
2
0, 0, 1, 3, 3, 4, 3, 4, 3, 5, 2, 3, 4, 3, 1, 4, 4, 1, 2, 4, 4, 2, 4, 4, 3, 5, 8, 5, 4, 5, 7, 4, 3, 5, 2, 7, 5, 3, 5, 4, 5, 9, 4, 5, 5, 5, 8, 6, 7, 7, 8, 9, 5, 9, 7, 8, 13, 5, 4, 8, 4, 8, 3, 9, 9, 6, 7, 8, 6, 9, 7, 7, 4, 10, 7, 6, 8, 8, 5, 9, 6, 10, 5, 10, 12, 6, 11, 5, 5, 9, 8, 8, 4, 4, 11, 8, 8, 12, 6, 8
COMMENTS
Conjecture: (i) a(n) > 0 for all n > 2.
(ii) If n > 2 is neither 18 nor 30, then n can be written as k + m with k > 0 and m > 0 such that A000009(k)^2 + A047967(m)^2 is prime. (iii) Any integer n > 4 can be written as k + m with k > 0 and m > 0 such that A000009(k)* A047967(m) - 1 (or A000009(k)* A047967(m) + 1) is prime.
EXAMPLE
a(15) = 1 since 15 = 13 + 2 with A000009(13) + A047967(13) = 18 + 1 = 19 prime. a(18) = 1 since 18 = 3 + 15 with A000009(3) + A047967(15) = 2 + 149 = 151 prime.
MATHEMATICA
p[n_, k_]:=PrimeQ[PartitionsQ[k]+(PartitionsP[n-k]-PartitionsQ[n-k])]
a[n_]:=Sum[If[p[n, k], 1, 0], {k, 1, n-1}]
Table[a[n], {n, 1, 100}]
a(n) is the number of partitions of n (the partition numbers).
(Formerly M0663 N0244)
+10
3701
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
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)optusnet.com.au), 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)gmail.com), 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)gmx.de), Apr 09 2007
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 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 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) 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)
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 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 a(n) is also the number of partitions of n*(n+3)/2 into n distinct parts. - David García Herrero, Aug 20 2024
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, Vol.II 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).
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 7.2.1.4, 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
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] James Grime and Brady Haran, Partitions, Numberphile video (2016). Johannes W. Meijer, Euler's ship on the Pentagonal Sea, pdf and jpg.
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. 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)
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).
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 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 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 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-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 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)
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>=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)).
[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) = A008284(2*n,n) is also the number of partitions of 2n into n parts. - Ryan Brooks, Jun 11 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 + ...
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).
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 *) a[0] := 1; a[n_] := a[n] = Block[{k=1, s=0, i=n-1}, While[i >= 0, s=s-(-1)^k (a[i]+a[i-k]); k=k+1; i=i-(3 k-2)]; s]; Map[a, Range[0, 49]] (* Oliver Seipel, Jun 01 2024 after Euler *)
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)))
(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
if n == 0: return 1
S = 0; J = n-1; k = 2
while 0 <= 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
(Sage) # uses[EulerTransform from A166861] a = BinaryRecurrenceSequence(1, 0)
b = EulerTransform(a)
(Haskell)
import Data.MemoCombinators (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
(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.
(Python)
from sympy.ntheory import npartitions
print([npartitions(i) for i in range(101)]) # Indranil Ghosh, Mar 17 2017 (Julia) # DedekindEta is defined in A000594A000041List(len) = DedekindEta(len, -1)
CROSSREFS
Cf. A000009, A000079, A000203, A001318, A008284, A026820, A065446, A078506, A113685, A132311, A000248.
EXTENSIONS
Additional comments from Ola Veshta (olaveshta(AT)my-deja.com), Feb 28 2001
Additional comments from Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001
Expansion of Product_{m >= 1} (1 + x^m); number of partitions of n into distinct parts; number of partitions of n into odd parts.
(Formerly M0281 N0100)
+10
1521
1, 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64, 76, 89, 104, 122, 142, 165, 192, 222, 256, 296, 340, 390, 448, 512, 585, 668, 760, 864, 982, 1113, 1260, 1426, 1610, 1816, 2048, 2304, 2590, 2910, 3264, 3658, 4097, 4582, 5120, 5718, 6378
COMMENTS
Partitions into distinct parts are sometimes called "strict partitions".
The number of different ways to run up a staircase with m steps, taking steps of odd sizes (or taking steps of distinct sizes), where the order is not relevant and there is no other restriction on the number or the size of each step taken is the coefficient of x^m.
The result that number of partitions of n into distinct parts = number of partitions of n into odd parts is due to Euler.
Bijection: given n = L1* 1 + L2*3 + L3*5 + L7*7 + ..., a partition into odd parts, write each Li in binary, Li = 2^a1 + 2^a2 + 2^a3 + ... where the aj's are all different, then expand n = (2^a1 * 1 + ...)*1 + ... by removing the brackets and we get a partition into distinct parts. For the reverse operation, just keep splitting any even number into halves until no evens remain.
Euler transform of period 2 sequence [1,0,1,0,...]. - Michael Somos, Dec 16 2002 Number of different partial sums 1+[1,2]+[1,3]+[1,4]+..., where [1,x] indicates a choice. E.g., a(6)=4, as we can write 1+1+1+1+1+1, 1+2+3, 1+2+1+1+1, 1+1+3+1. - Jon Perry, Dec 31 2003 a(n) is the sum of the number of partitions of x_j into at most j parts, where j is the index for the j-th triangular number and n-T(j)=x_j. For example; a(12)=partitions into <= 4 parts of 12-T(4)=2 + partitions into <= 3 parts of 12-T(3)=6 + partitions into <= 2 parts of 12-T(2)=9 + partitions into 1 part of 12-T(1)=11 = (2)(11) + (6)(51)(42)(411)(33)(321)(222) + (9)(81)(72)(63)(54)+(11) = 2+7+5+1 = 15. - Jon Perry, Jan 13 2004 Number of partitions of n where if k is the largest part, all parts 1..k are present. - Jon Perry, Sep 21 2005 Jack Grahl and Franklin T. Adams-Watters prove this claim of Jon Perry's by observing that the Ferrers dual of a "gapless" partition is guaranteed to have distinct parts; since the Ferrers dual is an involution, this establishes a bijection between the two sets of partitions. - Allan C. Wechsler, Sep 28 2021 The number of connected threshold graphs having n edges. - Michael D. Barrus (mbarrus2(AT)uiuc.edu), Jul 12 2007
Starting with offset 1 = row sums of triangle A146061 and the INVERT transform of A000700 starting: (1, 0, 1, -1, 1, -1, 1, -2, 2, -2, 2, -3, 3, -3, 4, -5, ...). - Gary W. Adamson, Oct 26 2008 Number of partitions of n in which the largest part occurs an odd number of times and all other parts occur an even number of times. (Such partitions are the duals of the partitions with odd parts.) - David Wasserman, Mar 04 2009 Considering all partitions of n into distinct parts: there are A140207(n) partitions of maximal size which is A003056(n), and A051162(n) is the greatest number occurring in these partitions. - Reinhard Zumkeller, Jun 13 2009 Number of symmetric unimodal compositions of n+1 where the maximal part appears once. Also number of symmetric unimodal compositions of n where the maximal part appears an odd number of times. - Joerg Arndt, Jun 11 2013 Because for these partitions the exponents of the parts 1, 2, ... are either 0 or 1 (j^0 meaning that part j is absent) one could call these partitions also 'fermionic partitions'. The parts are the levels, that is the positive integers, and the occupation number is either 0 or 1 (like Pauli's exclusion principle). The 'fermionic states' are denoted by these partitions of n. - Wolfdieter Lang, May 14 2014 The set of partitions containing only odd parts forms a monoid under the product described in comments to A047993. - Richard Locke Peterson, Aug 16 2018 a(n) equals the number of permutations p of the set {1,2,...,n+1}, written in one line notation as p = p_1p_2...p_(n+1), satisfying p_(i+1) - p_i <= 1 for 1 <= i <= n, (i.e., those permutations that, when read from left to right, never increase by more than 1) whose major index maj(p) := Sum_{p_i > p_(i+1)} i equals n. For example, of the 16 permutations on 5 letters satisfying p_(i+1) - p_i <= 1, 1 <= i <= 4, there are exactly two permutations whose major index is 4, namely, 5 3 4 1 2 and 2 3 4 5 1. Hence a(4) = 2. See the Bala link in A007318 for a proof. - Peter Bala, Mar 30 2022 Conjecture: Each positive integer n can be written as a_1 + ... + a_k, where a_1,...,a_k are strict partition numbers (i.e., terms of the current sequence) with no one dividing another. This has been verified for n = 1..1350. - Zhi-Wei Sun, Apr 14 2023 Conjecture: For each integer n > 7, a(n) divides none of p(n), p(n) - 1 and p(n) + 1, where p(n) is the number of partitions of n given by A000041. This has been verified for n up to 10^5. - Zhi-Wei Sun, May 20 2023 [Verified for n <= 2*10^6. - Vaclav Kotesovec, May 23 2023]
REFERENCES
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education, Vol. 31, No. 1, pp. 24-28, Winter 1997. MathEduc Database (Zentralblatt MATH, 1997c.01891).
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.
George E. Andrews, The Theory of Partitions, Cambridge University Press, 1998, p. 19.
George E. Andrews, Number Theory, Dover Publications, 1994, Theorem 12-3, pp. 154-5, and (13-1-1) p. 163.
Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; see p. 196.
T. J. I'a. Bromwich, Introduction to the Theory of Infinite Series, Macmillan, 2nd. ed. 1949, p. 116, Problem 18.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 99.
William Dunham, The Mathematical Universe, pp. 57-62, J. Wiley, 1994.
Leonhard Euler, De partitione numerorum, Novi commentarii academiae scientiarum Petropolitanae 3 (1750/1), 1753, reprinted in: Commentationes Arithmeticae. (Opera Omnia. Series Prima: Opera Mathematica, Volumen Secundum), 1915, Lipsiae et Berolini, 254-294.
Ian P. Goulden and David M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (2.5.1).
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 277, Theorems 344, 346.
Carlos J. Moreno and Samuel S. Wagstaff, Jr., Sums of Squares of Integers, Chapman and Hall, 2006, p. 253.
Srinivasa Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. See Table V on page 309.
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
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 836. Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009; see pages 48 and 499. James Mc Laughlin, Andrew V. Sills, and Peter Zimmer, Rogers-Ramanujan-Slater Type Identities, Electronic J. Combinatorics, DS15, 1-59, May 31, 2008; see also arXiv version, arXiv:1901.00946 [math.NT], 2019. Donald J. Newman, A Problem Seminar, pp. 18;93;102-3 Prob. 93 Springer-Verlag NY 1982.
FORMULA
G.f.: Product_{m>=1} (1 + x^m) = 1/Product_{m>=0} (1-x^(2m+1)) = Sum_{k>=0} Product_{i=1..k} x^i/(1-x^i) = Sum_{n>=0} x^(n*(n+1)/2) / Product_{k=1..n} (1-x^k).
G.f.: Sum_{n>=0} x^n*Product_{k=1..n-1} (1+x^k) = 1 + Sum_{n>=1} x^n*Product_{k>=n+1} (1+x^k). - Joerg Arndt, Jan 29 2011 Product_{k>=1} (1+x^(2k)) = Sum_{k>=0} x^(k*(k+1))/Product_{i=1..k} (1-x^(2i)) - Euler (Hardy and Wright, Theorem 346).
Asymptotics: a(n) ~ exp(Pi l_n / sqrt(3)) / ( 4 3^(1/4) l_n^(3/2) ) where l_n = (n-1/24)^(1/2) (Ayoub).
For n > 1, a(n) = (1/n)*Sum_{k=1..n} b(k)*a(n-k), with a(0)=1, b(n) = A000593(n) = sum of odd divisors of n; cf. A000700. - Vladeta Jovovic, Jan 21 2002 a(n) = t(n, 0), t as defined in A079211. Expansion of 1 / chi(-x) = chi(x) / chi(-x^2) = f(-x) / phi(x) = f(x) / phi(-x^2) = psi(x) / f(-x^2) = f(-x^2) / f(-x) = f(-x^4) / psi(-x) in powers of x where phi(), psi(), chi(), f() are Ramanujan theta functions. - Michael Somos, Mar 12 2011 G.f. is a period 1 Fourier series which satisfies f(-1 / (1152 t)) = 2^(-1/2) / f(t) where q = exp(2 Pi i t). - Michael Somos, Aug 16 2007 Expansion of q^(-1/24) * eta(q^2) / eta(q) in powers of q.
Expansion of q^(-1/24) 2^(-1/2) f2(t) in powers of q = exp(2 Pi i t) where f2() is a Weber function. - Michael Somos, Oct 18 2007 Given g.f. A(x), then B(x) = x * A(x^3)^8 satisfies 0 = f(B(x), B(x^2)) where f(u, v) = v - u^2 + 16*u*v^2 . - Michael Somos, May 31 2005 Given g.f. A(x), then B(x) = x * A(x^8)^3 satisfies 0 = f(B(x), B(x^3)) where f(u, v) = (u^3 - v) * (u + v^3) - 9 * u^3 * v^3. - Michael Somos, Mar 25 2008 From Evangelos Georgiadis, Andrew V. Sutherland, Kiran S. Kedlaya (egeorg(AT)mit.edu), Mar 03 2009: (Start)
a(0)=1; a(n) = 2*(Sum_{k=1..floor(sqrt(n))} (-1)^(k+1) a(n-k^2)) + sigma(n) where sigma(n) = (-1)^j if (n=(j*(3*j+1))/2 OR n=(j*(3*j-1))/2) otherwise sigma(n)=0 (simpler: sigma = A010815). (End) The product g.f. = (1/(1-x))*(1/(1-x^3))*(1/(1-x^5))*...; = (1,1,1,...)*
(1,0,0,1,0,0,1,0,0,1,...)*(1,0,0,0,0,1,0,0,0,0,1,0,0,0,0,1,...) * ...; =
a*b*c*... where a, a*b, a*b*c, ... converge to A000009: 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... = a*b
1, 1, 1, 2, 2, 3, 4, 4, 5, 6, ... = a*b*c
1, 1, 1, 2, 2, 3, 4, 5, 6, 7, ... = a*b*c*d
1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ... = a*b*c*d*e
1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ... = a*b*c*d*e*f
... (cf. analogous example in A000041). (End) a(n) = P(n) - P(n-2) - P(n-4) + P(n-10) + P(n-14) + ... + (-1)^m P(n-2p_m) + ..., where P(n) is the partition function ( A000041) and p_m = m(3m-1)/2 is the m-th generalized pentagonal number ( A001318). - Jerome Malenfant, Feb 16 2011 G.f.: 1/2 (-1; x)_{inf} where (a; q)_k is the q-Pochhammer symbol. - Vladimir Reshetnikov, Apr 24 2013 More precise asymptotics: a(n) ~ exp(Pi*sqrt((n-1/24)/3)) / (4*3^(1/4)*(n-1/24)^(3/4)) * (1 + (Pi^2-27)/(24*Pi*sqrt(3*(n-1/24))) + (Pi^4-270*Pi^2-1215)/(3456*Pi^2*(n-1/24))). - Vaclav Kotesovec, Nov 30 2015 a(n) ~ exp(Pi*sqrt(n/3))/(4*3^(1/4)*n^(3/4)) * (1 + (Pi/(48*sqrt(3)) - (3*sqrt(3))/(8*Pi))/sqrt(n) + (Pi^2/13824 - 5/128 - 45/(128*Pi^2))/n).
a(n) ~ exp(Pi*sqrt(n/3) + (Pi/(48*sqrt(3)) - 3*sqrt(3)/(8*Pi))/sqrt(n) - (1/32 + 9/(16*Pi^2))/n) / (4*3^(1/4)*n^(3/4)).
(End)
a(n) ~ Pi*BesselI(1, Pi*sqrt((n+1/24)/3)) / sqrt(24*n+1). - Vaclav Kotesovec, Nov 08 2016 G.f.: (1 + x)*Sum_{n >= 0} x^(n*(n+3)/2)/Product_{k = 1..n} (1 - x^k) =
(1 + x)*(1 + x^2)*Sum_{n >= 0} x^(n*(n+5)/2)/Product_{k = 1..n} (1 - x^k) = (1 + x)*(1 + x^2)*(1 + x^3)*Sum_{n >= 0} x^(n*(n+7)/2)/Product_{k = 1..n} (1 - x^k) = ....
G.f.: (1/2)*Sum_{n >= 0} x^(n*(n-1)/2)/Product_{k = 1..n} (1 - x^k) =
(1/2)*(1/(1 + x))*Sum_{n >= 0} x^((n-1)*(n-2)/2)/Product_{k = 1..n} (1 - x^k) = (1/2)*(1/((1 + x)*(1 + x^2)))*Sum_{n >= 0} x^((n-2)*(n-3)/2)/Product_{k = 1..n} (1 - x^k) = ....
G.f.: Sum_{n >= 0} x^n/Product_{k = 1..n} (1 - x^(2*k)) = (1/(1 - x)) * Sum_{n >= 0} x^(3*n)/Product_{k = 1..n} (1 - x^(2*k)) = (1/((1 - x)*(1 - x^3))) * Sum_{n >= 0} x^(5*n)/Product_{k = 1..n} (1 - x^(2*k)) = (1/((1 - x)*(1 - x^3)*(1 - x^5))) * Sum_{n >= 0} x^(7*n)/Product_{k = 1..n} (1 - x^(2*k)) = .... (End)
G.f.: A(x) = Sum_{n >= 0} x^(n*(2*n-1))/Product_{k = 1..2*n} (1 - x^k). (Set z = x and q = x^2 in Mc Laughlin et al., Section 1.3, Entry 7.)
Similarly, A(x) = Sum_{n >= 0} x^(n*(2*n+1))/Product_{k = 1..2*n+1} (1 - x^k). (End)
G.f.: A(x) = exp ( Sum_{n >= 1} x^n/(n*(1 - x^(2*n))) ) = exp ( Sum_{n >= 1} (-1)^(n+1)*x^n/(n*(1 - x^n)) ). - Peter Bala, Dec 23 2021 Sum_{n>=0} a(n)/exp(Pi*n) = exp(Pi/24)/2^(1/8) = A292820. - Simon Plouffe, May 12 2023 [Proof: Sum_{n>=0} a(n)/exp(Pi*n) = phi(exp(-2*Pi)) / phi(exp(-Pi)), where phi(q) is the Euler modular function. We have phi(exp(-2*Pi)) = exp(Pi/12) * Gamma(1/4) / (2 * Pi^(3/4)) and phi(exp(-Pi)) = exp(Pi/24) * Gamma(1/4) / (2^(7/8) * Pi^(3/4)), see formulas (14) and (13) in I. Mező, 2013. - Vaclav Kotesovec, May 12 2023] a(2*n) = Sum_{j=1..n} p(n+j, 2*j) and a(2*n+1) = Sum_{j=1..n+1} p(n+j,2*j-1), where p(n, s) is the number of partitions of n having exactly s parts. - Gregory L. Simay, Aug 30 2023
EXAMPLE
G.f. = 1 + x + x^2 + 2*x^3 + 2*x^4 + 3*x^5 + 4*x^6 + 5*x^7 + 6*x^8 + 8*x^9 + ...
G.f. = q + q^25 + q^49 + 2*q^73 + 2*q^97 + 3*q^121 + 4*q^145 + 5*q^169 + ...
The partitions of n into distinct parts (see A118457) for small n are: 1: 1
2: 2
3: 3, 21
4: 4, 31
5: 5, 41, 32
6: 6, 51, 42, 321
7: 7, 61, 52, 43, 421
8: 8, 71, 62, 53, 521, 431
...
MAPLE
N := 100; t1 := series(mul(1+x^k, k=1..N), x, N); A000009 := proc(n) coeff(t1, x, n); end; spec := [ P, {P=PowerSet(N), N=Sequence(Z, card>=1)} ]: [ seq(combstruct[count](spec, size=n), n=0..58) ];
spec := [ P, {P=PowerSet(N), N=Sequence(Z, card>=1)} ]: combstruct[allstructs](spec, size=10); # to get the actual partitions for n=10
local x, m;
product(1+x^m, m=1..n+1) ;
expand(%) ;
coeff(%, x, n) ;
# Alternatively:
simplify(expand(QDifferenceEquations:-QPochhammer(-1, x, 99)/2, x)):
MATHEMATICA
PartitionsQ[Range[0, 60]] (* _Harvey Dale_, Jul 27 2009 *)
a[ n_] := SeriesCoefficient[ Product[ 1 + x^k, {k, n}], {x, 0, n}]; (* Michael Somos, Jul 06 2011 *) a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^k, {k, 1, n, 2}], {x, 0, n}]; (* Michael Somos, Jul 06 2011 *) a[ n_] := With[ {t = Log[q] / (2 Pi I)}, SeriesCoefficient[ q^(-1/24) DedekindEta[2 t] / DedekindEta[ t], {q, 0, n}]]; (* Michael Somos, Jul 06 2011 *) a[ n_] := SeriesCoefficient[ 1 / QPochhammer[ x, x^2], {x, 0, n}]; (* Michael Somos, May 24 2013 *) a[ n_] := SeriesCoefficient[ Series[ QHypergeometricPFQ[ {q}, {q x}, q, - q x], {q, 0, n}] /. x -> 1, {q, 0, n}]; (* Michael Somos, Mar 04 2014 *) a[ n_] := SeriesCoefficient[ QHypergeometricPFQ[{}, {}, q, -1] / 2, {q, 0, n}]; (* Michael Somos, Mar 04 2014 *) nmax = 60; CoefficientList[Series[Exp[Sum[(-1)^(k+1)/k*x^k/(1-x^k), {k, 1, nmax}]], {x, 0, nmax}], x] (* Vaclav Kotesovec, Aug 25 2015 *) nmax = 100; poly = ConstantArray[0, nmax + 1]; poly[[1]] = 1; poly[[2]] = 1; Do[Do[poly[[j + 1]] += poly[[j - k + 1]], {j, nmax, k, -1}]; , {k, 2, nmax}]; poly (* Vaclav Kotesovec, Jan 14 2017 *)
PROG
(PARI) {a(n) = if( n<0, 0, polcoeff( prod( k=1, n, 1 + x^k, 1 + x * O(x^n)), n))}; /* Michael Somos, Nov 17 1999 */ (PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^2 + A) / eta(x + A), n))};
(PARI) {a(n) = my(c); forpart(p=n, if( n<1 || p[1]<2, c++; for(i=1, #p-1, if( p[i+1] > p[i]+1, c--; break)))); c}; /* Michael Somos, Aug 13 2017 */ (PARI) lista(nn) = {q='q+O('q^nn); Vec(eta(q^2)/eta(q))} \\ Altug Alkan, Mar 20 2018 (Magma) Coefficients(&*[1+x^m:m in [1..100]])[1..100] where x is PolynomialRing(Integers()).1; // Sergei Haller (sergei(AT)sergei-haller.de), Dec 21 2006
(Haskell)
import Data.MemoCombinators (memo2, integral)
a000009 n = a000009_list !! n
a000009_list = map (pM 1) [0..] where
pM = memo2 integral integral p
p _ 0 = 1
p k m | m < k = 0
| otherwise = pM (k + 1) (m - k) + pM (k + 1) m
(Maxima)
h(n):=if oddp(n)=true then 1 else 0;
S(n, m):=if n=0 then 1 else if n<m then 0 else if n=m then h(n) else sum(h(k)*S(n-k, k), k, m, n/2)+h(n);
(SageMath) # uses[EulerTransform from A166861] a = BinaryRecurrenceSequence(0, 1)
b = EulerTransform(a)
from functools import lru_cache
from math import isqrt
@lru_cache(maxsize=None)
using Memoize
n == 0 && return 1
s = sum((-1)^k* A000009(n - k^2) for k in 1:isqrt(n))
CROSSREFS
Apart from the first term, equals A052839-1. The rows of A053632 converge to this sequence. When reduced modulo 2 equals the absolute values of A010815. The positions of odd terms given by A001318. a(n) = Sum_{n=1..m} A097306(n, m), row sums of triangle of number of partitions of n into m odd parts. Cf. A001318, A000041, A000700, A003724, A004111, A007837, A010815, A035294, A068049, A078408, A081360, A088670, A109950, A109968, A132312, A146061, A035363, A010054, A057077, A089806, A091602, A237515, A118457 (the partitions), A118459 (partition lengths), A015723 (total number of parts), A230957 (boustrophedon transform). Number of r-regular partitions for r = 2 through 12: A000009, A000726, A001935, A035959, A219601, A035985, A261775, A104502, A261776, A328545, A328546.
Number of complete partitions of n.
+10
84
1, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 31, 39, 55, 71, 100, 125, 173, 218, 291, 366, 483, 600, 784, 971, 1244, 1538, 1957, 2395, 3023, 3693, 4605, 5604, 6942, 8397, 10347, 12471, 15235, 18309, 22267, 26619, 32219, 38414, 46216, 54941, 65838, 77958, 93076, 109908
COMMENTS
A partition of n is complete if every number 1 to n can be represented as a sum of parts of the partition. This generalizes perfect partitions, where the representation for each number must be unique.
A partition is complete iff each part is no more than 1 more than the sum of all smaller parts. (This includes the smallest part, which thus must be 1.) - Franklin T. Adams-Watters, Mar 22 2007 a(n+1) is the number of partitions of n such that each part is no more than 2 more than the sum of all smaller parts (generalizing Adams-Watters's criterion). Bijection: each partition counted by a(n+1) must contain a 1, removing that gives a desired partition of n. - Brian Hopkins, May 16 2017 A partition (x_1, ..., x_k) is complete if and only if 1, x_1, ..., x_k is a "regular sequence" (see A003513 for definition). As a result, the number of complete partitions with n parts is given by A003513(n+1). - Nathaniel Johnston, Jun 29 2023
FORMULA
G.f.: 1 = Sum_{n>=0} a(n)*x^n*Product_{k=1..n+1} (1-x^k). - Paul D. Hanna, Mar 08 2012 a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi + 25*Pi/(24*sqrt(6))) / sqrt(n) + (25/16 - 1679*Pi^2/6912)/n). - Vaclav Kotesovec, May 24 2018, extended Nov 02 2019
EXAMPLE
There are a(5) = 4 complete partitions of 5:
[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], and [1, 1, 3].
G.f.: 1 = 1*(1-x) + 1*x*(1-x)*(1-x^2) + 1*x^2*(1-x)*(1-x^2)*(1-x^3) + 2*x^3*(1-x)*(1-x^2)*(1-x^3)*(1-x^4) + 2*x^4*(1-x)*(1-x^2)*(1-x^3)*(1-x^4)*(1-x^5) + ...
The a(1) = 1 through a(8) = 10 partitions:
(1) (11) (21) (211) (221) (321) (421) (3221)
(111) (1111) (311) (2211) (2221) (3311)
(2111) (3111) (3211) (4211)
(11111) (21111) (4111) (22211)
(111111) (22111) (32111)
(31111) (41111)
(211111) (221111)
(1111111) (311111)
(2111111)
(11111111)
(End)
MAPLE
isCompl := proc(p, n) local m, pers, reps, f, lst, s; reps := {}; pers := combinat[permute](p); for m from 1 to nops(pers) do lst := op(m, pers); for f from 1 to nops(lst) do s := add( op(i, lst), i=1..f); reps := reps union {s}; od; od; for m from 1 to n do if not m in reps then RETURN(false); fi; od; RETURN(true); end: A126796 := proc(n) local prts, res, p; prts := combinat[partition](n); res :=0; for p from 1 to nops(prts) do if isCompl(op(p, prts), n) then res := res+1; fi; od; RETURN(res); end: for n from 1 to 40 do printf("%d %d ", n, A126796(n)); od; # R. J. Mathar, Feb 27 2007 # At the beginning of the 2nd Maple program replace the current 15 by any other positive integer n in order to obtain a(n). - Emeric Deutsch, Mar 04 2007 with(combinat): a:=proc(n) local P, b, k, p, S, j: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i], i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: end: seq(a(n), n=1..30); # Emeric Deutsch, Mar 04 2007 with(combinat): n:=15: P:=partition(n): b:=0: for k from 1 to numbpart(n) do p:=powerset(P[k]): S:={}: for j from 1 to nops(p) do S:=S union {add(p[j][i], i=1..nops(p[j]))} od: if nops(S)=n+1 then b:=b+1 else b:=b: fi: od: b; # Emeric Deutsch, Mar 04 2007
MATHEMATICA
T[n_, k_] := T[n, k] = If[k <= 1, 1, If[n < 2k-1, T[n, Floor[(n+1)/2]], T[n, k-1] + T[n-k, k]]];
a[n_] := T[n, Floor[(n+1)/2]];
nmz[y_]:=Complement[Range[Total[y]], Total/@Subsets[y]]; Table[Length[Select[IntegerPartitions[n], nmz[#]=={}&]], {n, 0, 15}] (* Gus Wiseman, Oct 14 2023 *)
PROG
(PARI) {T(n, k)=if(k<=1, 1, if(n<2*k-1, T(n, floor((n+1)/2)), T(n, k-1)+T(n-k, k)))}
{a(n)=T(n, floor((n+1)/2))} /* If modified to save earlier results, this would be efficient. */ /* Franklin T. Adams-Watters, Mar 22 2007 */ (PARI) /* As coefficients in g.f.: */
{a(n)=local(A=[1, 1]); for(i=1, n+1, A=concat(A, 0); A[#A]=polcoeff(1-sum(m=1, #A, A[m]*x^m*prod(k=1, m, 1-x^k +x*O(x^#A))), #A) ); A[n+1]}
for(n=0, 50, print1(a(n), ", ")) /* Paul D. Hanna, Mar 06 2012 */ (Haskell)
import Data.MemoCombinators (memo3, integral, Memo)
a126796 n = a126796_list !! n
a126796_list = map (pMemo 1 1) [0..] where
pMemo = memo3 integral integral integral p
p _ _ 0 = 1
p s k m
| k > min m s = 0
| otherwise = pMemo (s + k) k (m - k) + pMemo s (k + 1) m
CROSSREFS
For parts instead of sums we have A000009 (sc. coverings), ranks A055932. These partitions have ranks A325781. Cf. A000041, A018818, A046663, A047967, A276024, A304792, A325799, A365543, A365658, A365918, A365921.
Search completed in 0.050 seconds
| 
