Displaying 1-10 of 140 results found.
page
1
2
3
4
5
6
7
8
9
10
... 14
The difference between the number of partitions of 2n into odd parts ( A000009) and the number of partitions of 2n into even parts ( A035363).
+20
5
0, 0, 0, 1, 1, 3, 4, 7, 10, 16, 22, 33, 45, 64, 87, 120, 159, 215, 283, 374, 486, 634, 814, 1049, 1335, 1700, 2146, 2708, 3390, 4243, 5276, 6552, 8095, 9989, 12266, 15044, 18375, 22409, 27235, 33049, 39974, 48281, 58148, 69923, 83871, 100452, 120027, 143214, 170515, 202731, 240567, 285073, 337195
FORMULA
Expansion of (f(x^3, x^5) - 1) / f(-x, -x^2) in powers of x where f(, ) is Ramanujan's general theta function. - Michael Somos, Feb 24 2017
EXAMPLE
G.f. = x^3 + x^4 + 3*x^5 + 4*x^6 + 7*x^7 + 10*x^8 + 16*x^9 + 22*x^10 + 33*x^11 + ...
MAPLE
with(numtheory):
b:= proc(n, t) option remember; `if`(n=0, 1, add(add(`if`(
(d+t)::odd, d, 0), d=divisors(j))*b(n-j, t), j=1..n)/n)
end:
a:= n-> b(2*n, 0) -b(2*n, 1):
MATHEMATICA
f[n_] := Length[ IntegerPartitions[n, All, 2Range[n] -1]] - Length[ IntegerPartitions[n, All, 2 Range[n]]]; Array[ f[2#] &, 52]
a[ n_] := SeriesCoefficient[ Sum[ Sign @ SquaresR[1, 16 k + 1] x^k, {k, n}] / QPochhammer[x], {x, 0, n}]; (* Michael Somos, Feb 24 2017 *)
PROG
(PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( sum(k=1, n, issquare(16*k + 1)*x^k, A) / eta(x + A), n))}; /* Michael Somos, Feb 24 2017 */
The difference between the number of partitions of n into odd parts ( A000009) and the number of partitions of n into even parts ( A035363).
+20
2
0, 1, 0, 2, 0, 3, 1, 5, 1, 8, 3, 12, 4, 18, 7, 27, 10, 38, 16, 54, 22, 76, 33, 104, 45, 142, 64, 192, 87, 256, 120, 340, 159, 448, 215, 585, 283, 760, 374, 982, 486, 1260, 634, 1610, 814, 2048, 1049, 2590, 1335, 3264, 1700, 4097, 2146, 5120, 2708, 6378, 3390, 7917, 4243, 9792, 5276
MAPLE
with(numtheory):
b:= proc(n, t) option remember; `if`(n=0, 1, add(add(`if`(
(d+t)::odd, d, 0), d=divisors(j))*b(n-j, t), j=1..n)/n)
end:
a:= n-> b(n, 0) -b(n, 1):
MATHEMATICA
f[n_] := Length[ IntegerPartitions[n, All, 2Range[n] -1]] - Length[ IntegerPartitions[n, All, 2 Range[n]]]; Array[f, 60]
(* Second program: *)
b[n_, t_] := b[n, t] = If[n == 0, 1, Sum[Sum[If[
OddQ[d+t], d, 0], {d, Divisors[j]}]*b[n-j, t], {j, 1, n}]/n];
a[n_] := b[n, 0] - b[n, 1];
a(n) is the number of partitions of n (the partition numbers).
(Formerly M0663 N0244)
+10
3702
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. (2019 ArXiv version), Section 1.3, Identity 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.
KEYWORD
nonn,core,easy,nice,changed
a(n) = Sum_{k=0..n} p(k) where p(k) = number of partitions of k ( A000041).
(Formerly M1054 N0396)
+10
435
1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373, 508, 684, 915, 1212, 1597, 2087, 2714, 3506, 4508, 5763, 7338, 9296, 11732, 14742, 18460, 23025, 28629, 35471, 43820, 53963, 66273, 81156, 99133, 120770, 146785, 177970, 215308, 259891, 313065, 376326, 451501
COMMENTS
Also the total number of all different integers in all partitions of n + 1. E.g., a(3) = 7 because the partitions of 4 comprise the sets {1},{1, 2},{2},{1, 3},{4} of different integers and their total number is 7. - Thomas Wieder, Apr 10 2004 With offset 1, also the number of 1's in all partitions of n. For example, 3 = 2+1 = 1+1+1, a(3) = (zero 1's) + (one 1's) + (three 1's), so a(3) = 4. - Naohiro Nomoto, Jan 09 2002. See the Riordan reference p. 184, last formula, first term, for a proof based on Fine's identity given in Riordan, p. 182 (20). Also, number of partitions of n into parts when there are two kinds of parts of size one.
Also number of graphical forest partitions of 2n+2.
a(n) = count 2 for each partition of n and 1 for each decrement. E.g., the partitions of 4 are 4 (2), 31 (3), 22 (2), 211 (3) and 1111 (2). 2 + 3 + 2 + 3 + 2 = 12. This is related to the Ferrers representation. We can see that taking the Ferrers diagram for each partition of n and adding a new * to all available columns, we generate each partition of n+1, but with repeats ( A058884). - Jon Perry, Feb 06 2004 Also the number of 1-transitions among all integer partitions of n. A 1-transition is the removal of a digit "1" from a partition containing at least one "1" and subsequent addition of that "1" to another digit in that partition. This other digit may be a "1" also, but all digits of equal amount are considered as undistinquishable (unlabeled). E.g., for n=6 one has the partition [1113] for which the following two 1-transitions are possible: [1113] --> [123] and [1113] --> [114]. The 1-transitions of n form a partial order (poset). For n=6 one has 12 1-transitions: [111111] --> [11112], [11112] --> [1113], [11112] --> [1122], [1113] --> [114], [1113] --> [123], [1122] --> [123], [1122] --> [222], [123] --> [33], [123] --> [24], [114] --> [15], [114] --> [24], [15] --> [6]. - Thomas Wieder, Mar 08 2005 Also number of partitions of 2n+1 where one of the parts is greater than n (also where there are more than n parts) and of 2n+2 where one of the parts is greater than n+1 (or with more than n+1 parts). - Henry Bottomley, Aug 01 2005 Also the total number of 1's among all hook-lengths in all partitions of n. E.g., a(4)=7 because hooks of the partitions of n = 4 comprise the multisets {4,3,2,1}, {4,2,1,1}, {3,2,2,1}, {4,1,2,1}, {4,3,2,1} and their total number of 1's is 7. - T. Amdeberhan, Jun 03 2012 With offset 1, a(n) is also the difference between the sum of largest and the sum of second largest elements in all partitions of n. More generally, the number of occurrences of k in all partitions of n equals the difference between the sum of k-th largest and the sum of (k+1)st largest elements in all partitions of n. And more generally, the sum of the number of occurrences of k, k+1, k+2..k+m in all partitions of n equals the difference between the sum of k-th largest and the sum of (k+m+1)st largest elements in all partitions of n. - Omar E. Pol, Oct 25 2012 a(0) = 1 and 2*a(n-1) >= a(n) for all n > 0. Hence a(n) is a complete sequence. - Frank M Jackson, Apr 08 2013 a(n) is the number of conjugacy classes in the order-preserving, order-decreasing and (order-preserving and order-decreasing) injective transformation semigroups. - Ugbene Ifeanyichukwu, Jun 03 2015 a(n) is also the number of unlabeled subgraphs of the n-cycle C_n. For example, for n = 3, there are 3 unlabeled subgraphs of the triangle C_3 with 0 edges, 2 with 1 edge, 1 with 2 edges, and 1 with 3 edges (C_3 itself), so a(3) = 3 + 2 + 1 + 1 = 7. - John P. McSorley, Nov 21 2016 a(n) is also the number of partitions of 2n with all parts either even or equal to 1. Proof: the number of such partitions of 2n with exactly 2k 1's is p(n-k), for k = 0,..,n. Summing over k gives the formula. - Leonard Chastkofsky, Jul 24 2018 a(n) is the total number of polygamma functions that appear in the expansion of the (n+1)st derivative of x! with respect to x. More specifically, a(n) is the number of times the string "PolyGamma" appears in the expansion of D[x!, {x, n + 1}] in Mathematica. For example, D[x!, {x, 3 + 1}] = Gamma[1 + x] PolyGamma[0, 1 + x]^4 + 6 Gamma[1 + x] PolyGamma[0, 1 + x]^2 PolyGamma[1, 1 + x] + 3 Gamma[1 + x] PolyGamma[1, 1 + x]^2 + 4 Gamma[1 + x] PolyGamma[0, 1 + x] PolyGamma[2, 1 + x] + Gamma[1 + x] PolyGamma[3, 1 + x], and we see that the string "PolyGamma" appears a total of a(3) = 7 times in this expansion. - John M. Campbell, Aug 11 2018 With offset 1, also the number of integer partitions of 2n that do not comprise the multiset of vertex-degrees of any multigraph (i.e., non-multigraphical partitions); see A209816 for multigraphical partitions. - Gus Wiseman, Oct 26 2018 Also a(n) is the number of partitions of 2n+1 with exactly one odd part.
Delete the odd part 2k+1, k=0, ..., n, to get a partition of 2n-2k into even parts. There are as many unrestricted partitions of n-k; now sum those numbers from 0 to n to get a(n). - George Beck, Jul 22 2019 In the Young's lattice, a(n) is the number of branches that connect the (n-1)-th layer to the n-th layer. - Shouvik Datta, Sep 19 2021 a(n) is the number of multiset partitions of the multiset {r^n, s^1}, equivalently, factorization patterns of any number m=p^n*q^1 where p and q are primes. - Joerg Arndt, Jan 01 2024 a(n) is the number of positive integers whose divisors are the parts of the partitions of n + 1. - Omar E. Pol, Nov 07 2024
REFERENCES
H. Gupta, An asymptotic formula in partitions. J. Indian Math. Soc., (N. S.) 10 (1946), 73-76.
H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 6.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018 A. M. Odlyzko, Asymptotic Enumeration Methods, p. 19
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.
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).
Stanley, R. P., Exercise 1.26 in Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 59, 1999.
FORMULA
Euler transform of [ 2, 1, 1, 1, 1, 1, 1, ...].
a(n) = (1/n)*Sum_{k=1..n} (sigma(k)+1)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002 G.f.: (1/(1 - x))*Product_{m >= 1} 1/(1 - x^m).
Gupta gives the asymptotic result a(n-1) ~ sqrt(6/Pi^2)* sqrt(n)*p(n), where p(n) is the partition function A000041(n). Let P(2,n) denote the set of partitions of n into parts k >= 2.
a(n-2) = Sum_{parts k in all partitions in P(2,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, leads to the asymptotic result a(n-2) ~ (6/Pi^2)*n*(p(n) - p(n-1)) = (6/Pi^2)* A138880(n) as n -> infinity. (End) a(n) ~ exp(Pi*sqrt(2*n/3)) / (2^(3/2)*Pi*sqrt(n)) * (1 + 11*Pi/(24*sqrt(6*n)) + (73*Pi^2 - 1584)/(6912*n)). - Vaclav Kotesovec, Oct 26 2016 G.f.: exp(Sum_{k>=1} (sigma_1(k) + 1)*x^k/k). - Ilya Gutkovskiy, Aug 21 2018
EXAMPLE
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 12*x^4 + 19*x^5 + 30*x^6 + 45*x^7 + 67*x^8 + ...
For n = 5 consider the partitions of n+1:
--------------------------------------
. Number
Partitions of 6 of 1's
--------------------------------------
6 .......................... 0
3 + 3 ...................... 0
4 + 2 ...................... 0
2 + 2 + 2 .................. 0
5 + 1 ...................... 1
3 + 2 + 1 .................. 1
4 + 1 + 1 .................. 2
2 + 2 + 1 + 1 .............. 2
3 + 1 + 1 + 1 .............. 3
2 + 1 + 1 + 1 + 1 .......... 4
1 + 1 + 1 + 1 + 1 + 1 ...... 6
------------------------------------
35-16 = 19
.
The difference between the sum of the first column and the sum of the second column of the set of partitions of 6 is 35 - 16 = 19 and equals the number of 1's in all partitions of 6, so the 6th term of this sequence is a(5) = 19.
(End)
With offset 1, the a(1) = 1 through a(6) = 19 partitions of 2*n whose greatest part is > n:
(2) (4) (6) (8) (A) (C)
(31) (42) (53) (64) (75)
(51) (62) (73) (84)
(411) (71) (82) (93)
(521) (91) (A2)
(611) (622) (B1)
(5111) (631) (732)
(721) (741)
(811) (822)
(6211) (831)
(7111) (921)
(61111) (A11)
(7221)
(7311)
(8211)
(9111)
(72111)
(81111)
(711111)
With offset 1, the a(1) = 1 through a(6) = 19 partitions of 2*n whose number of parts is > n:
(11) (211) (2211) (22211) (222211) (2222211)
(1111) (3111) (32111) (322111) (3222111)
(21111) (41111) (331111) (3321111)
(111111) (221111) (421111) (4221111)
(311111) (511111) (4311111)
(2111111) (2221111) (5211111)
(11111111) (3211111) (6111111)
(4111111) (22221111)
(22111111) (32211111)
(31111111) (33111111)
(211111111) (42111111)
(1111111111) (51111111)
(222111111)
(321111111)
(411111111)
(2211111111)
(3111111111)
(21111111111)
(111111111111)
(End)
The a(5) = 19 multiset partitions of the multiset {1^5, 2^1} are:
1: {{1, 1, 1, 1, 1, 2}}
2: {{1, 1, 1, 1, 1}, {2}}
3: {{1, 1, 1, 1, 2}, {1}}
4: {{1, 1, 1, 1}, {1, 2}}
5: {{1, 1, 1, 1}, {1}, {2}}
6: {{1, 1, 1, 2}, {1, 1}}
7: {{1, 1, 1, 2}, {1}, {1}}
8: {{1, 1, 1}, {1, 1, 2}}
9: {{1, 1, 1}, {1, 1}, {2}}
10: {{1, 1, 1}, {1, 2}, {1}}
11: {{1, 1, 1}, {1}, {1}, {2}}
12: {{1, 1, 2}, {1, 1}, {1}}
13: {{1, 1, 2}, {1}, {1}, {1}}
14: {{1, 1}, {1, 1}, {1, 2}}
15: {{1, 1}, {1, 1}, {1}, {2}}
16: {{1, 1}, {1, 2}, {1}, {1}}
17: {{1, 1}, {1}, {1}, {1}, {2}}
18: {{1, 2}, {1}, {1}, {1}, {1}}
19: {{1}, {1}, {1}, {1}, {1}, {2}}
(End)
MAPLE
with(combinat): a:=n->add(numbpart(j), j=0..n): seq(a(n), n=0..44); # Zerinvary Lajos, Aug 26 2008
MATHEMATICA
CoefficientList[ Series[1/(1 - x)*Product[1/(1 - x^k), {k, 75}], {x, 0, 45}], x] (* Robert G. Wilson v, Jul 13 2004 *) Table[ Count[ Flatten@ IntegerPartitions@ n, 1], {n, 45}] (* Robert G. Wilson v, Aug 06 2008 *) Join[{1}, Accumulate[PartitionsP[Range[50]]]+1] (* _Harvey P. Dale, Mar 12 2013 *)
a[ n_] := SeriesCoefficient[ 1 / (1 - x) / QPochhammer[ x], {x, 0, n}]; (* Michael Somos, Nov 09 2013 *)
PROG
(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / prod(m=1, n, 1 - x^m, 1 + x * O(x^n)) / (1 - x), n))}; /* Michael Somos, Nov 08 2002 */ (PARI) x='x+O('x^66); Vec(1/((1-x)*eta(x))) /* Joerg Arndt, May 15 2011 */ (PARI) a(n) = sum(k=0, n, numbpart(k)); \\ Michel Marcus, Sep 16 2016 (Haskell)
a000070 = p a028310_list where
p _ 0 = 1
p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
(Sage)
p = [number_of_partitions(n) for n in range(leng)]
return [add(p[:k+1]) for k in range(leng)]
(GAP) List([0..45], n->Sum([0..n], k->NrPartitions(k))); # Muniru A Asiru, Jul 25 2018 (Python)
from itertools import accumulate
def A000070iter(n):
L = [0]*n; L[0] = 1
def numpart(n):
S = 0; J = n-1; k = 2
while 0 <= J:
T = L[J]
S = S+T if (k//2)%2 else S-T
J -= k if (k)%2 else k//2
k += 1
return S
for j in range(1, n): L[j] = numpart(j)
return accumulate(L)
(Python) # Using function A365676Row. Compare also A365675. from itertools import accumulate
def A000070List(size: int) -> list[int]:
return [sum(accumulate(reversed(A365676Row(n)))) for n in range(size)]
CROSSREFS
Cf. A014153, A024786, A026794, A026905, A058884, A093694, A133735, A137633, A010815, A027293, A035363, A028310, A000712, A000990.
Number of overpartitions of n: an overpartition of n is an ordered sequence of nonincreasing integers that sum to n, where the first occurrence of each integer may be overlined.
+10
191
1, 2, 4, 8, 14, 24, 40, 64, 100, 154, 232, 344, 504, 728, 1040, 1472, 2062, 2864, 3948, 5400, 7336, 9904, 13288, 17728, 23528, 31066, 40824, 53408, 69568, 90248, 116624, 150144, 192612, 246256, 313808, 398640, 504886, 637592, 802936, 1008448
COMMENTS
The over-partition function.
Also the number of jagged partitions of n.
According to Ramanujan (1913) a(n) is close to (cosh(x)-sinh(x)/x)/(4*n) where x=Pi*sqrt(n). - Michael Somos, Mar 17 2003 Number of partitions of 2n with all odd parts occurring with even multiplicities. There is no restriction on the even parts. Cf. A006950, A046682. - Mamuka Jibladze, Sep 05 2003 Number of partitions of n where there are two kinds of odd parts. - Joerg Arndt, Jul 30 2011. Or, in Gosper's words, partitions into red integers and blue odd integers. - N. J. A. Sloane, Jul 04 2016. Coincides with the sequence of numbers of nilpotent conjugacy classes in the Lie algebras sp(n), n=0,1,2,3,... (the case n=0 being degenerate). A006950, this sequence and A000041 together cover the nilpotent conjugacy classes in the classical A,B,C,D series of Lie algebras. - Alexander Elashvili, Sep 08 2003 Also, number of 01-partitions of n. A 01-partition of n is a weakly decreasing sequence of m nonnegative integers n(i) such that sum(n(i))=n, n(m)>0, n(j)>=n(j+1)-1 and n(j)>=n(j+2). They are special cases of jagged partitions.
a(8n+7) is divisible by 64 (from Fortin/Jacob/Mathieu paper).
Smallest sequence of even numbers (except a(0)) which is the Euler transform of a sequence of positive integers. - Franklin T. Adams-Watters, Oct 16 2006 Equals the infinite product [1,2,2,2,...] * [1,0,2,0,2,0,2,...] * [1,0,0,2,0,0,2,0,0,2,...] * ... . - Gary W. Adamson, Jul 05 2009 The overlining method is equivalent to enumerating the k-subsets of the distinct parts of the i-th partition. - Richard Joseph Boland, Sep 02 2021
REFERENCES
J. H. Conway and N. J. A. Sloane, "Sphere Packings, Lattices and Groups", Springer-Verlag, p. 103.
R. W. Gosper, Experiments and discoveries in q-trigonometry, in Symbolic Computation, Number Theory, Special Functions, Physics and Combinatorics. Editors: F. G. Garvan and M. E. H. Ismail. Kluwer, Dordrecht, Netherlands, 2001, pp. 79-105. See the function g(q).
James R. Newman, The World of Mathematics, Simon and Schuster, 1956, Vol. I p. 372.
LINKS
Sylvie Corteel and Jeremy Lovejoy, Overpartitions, Trans. Amer. Math. Soc., 356 (2004), 1623-1635. J.-F. Fortin, P. Jacob and P. Mathieu, Jagged partitions, The Ramanujan Journal, Vol. 10, No. 2 (2005), pp. 215-235; arXiv preprint, arXiv:math/0310079 [math.CO], 2003-2005. R. W. Gosper, Experiments and discoveries in q-trigonometry, in F. G. Garvan and M. E. H. Ismail (eds.), Symbolic computation, number theory, special functions, physics and combinatorics, Springer, Boston, MA, 2001, pp. 79-105; preprint.
FORMULA
Euler transform of period 2 sequence [2, 1, ...]. - Michael Somos, Mar 17 2003 G.f.: Product_{m>=1} (1 + q^m)/(1 - q^m).
G.f.: 1 / (Sum_{m=-inf..inf} (-q)^(m^2)) = 1/theta_4(q).
G.f.: 1 / Product_{m>=1} (1 - q^(2*m)) * (1 - q^(2*m-1))^2.
G.f.: exp( Sum_{n>=1} 2*x^(2*n-1)/(1 - x^(2*n-1))/(2*n-1) ). - Paul D. Hanna, Aug 06 2009 G.f.: exp( Sum_{n>=1} (sigma(2*n) - sigma(n))*x^n/n ). - Joerg Arndt, Jul 30 2011 G.f.: Product_{n>=0} theta_3(q^(2^n))^(2^n). - Joerg Arndt, Aug 03 2011 Expansion of eta(q^2) / eta(q)^2 in powers of q. - Michael Somos, Nov 01 2008 Expansion of 1 / phi(-q) in powers of q where phi() is a Ramanujan theta function. - Michael Somos, Nov 01 2008 Recurrence: a(n) = 2*Sum_{m>=1} (-1)^(m+1) * a(n-m^2).
a(n) = (1/n)*Sum_{k=1..n} (sigma(2*k) - sigma(k))*a(n-k). - Vladeta Jovovic, Dec 05 2004 G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^4)) where f(u, v, w) = w^4 * (u^4 + v^4) - 2 * u^2 * v^6. - Michael Somos, Nov 01 2008 G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u6^3 * (u1^2 + u3^2) - 2 * u1 * u2 * u3^3. - Michael Somos, Nov 01 2008 G.f. A(x) satisfies 0 = f(A(x), A(x^2), A(x^3), A(x^6)) where f(u1, u2, u3, u6) = u2^3 * (u3^2 - 3 * u1^2) + 2 * u1^3 * u3 * u6. - Michael Somos, Nov 01 2008 G.f. is a period 1 Fourier series which satisfies f(-1 / (16 t)) = 32^(-1/2) (t/i)^(-1/2) g(t) where q = exp(2 Pi i t) and g() is the g.f. for A106507. - Michael Somos, Nov 01 2008 a(n) ~ Pi * BesselI(3/2, Pi*sqrt(n)) / (4*sqrt(2)*n^(3/4)). - Vaclav Kotesovec, Jan 11 2017 Let T(n,k) = the number of partitions of n with parts 1 through k of two kinds, T(n,0) = A000041(n), the number of partitions of n. Then a(n) = T(n,0) + T(n-1,1) + T(n-3,2) + T(n-6,3) + T(n-10,4) + T(n-15,5) + ... . Gregory L. Simay, May 29 2019 a(n) = Sum_{i=1..p(n)} 2^(d(n,i)), where d(n,i) is the number of distinct parts in the i-th partition of n. - Richard Joseph Boland, Sep 02 2021 G.f.: A(x) = exp( Sum_{n >= 1} x^n*(2 + x^n)/(n*(1 - x^(2*n))) ). - Peter Bala, Dec 23 2021 G.f. A(q) satisfies (3*A(q)/A(q^9) - 1)^3 = 9*A(q)^4/A(q^3)^4 - 1. - Paul D. Hanna, Oct 14 2024
EXAMPLE
G.f. = 1 + 2*q + 4*q^2 + 8*q^3 + 14*q^4 + 24*q^5 + 40*q^6 + 64*q^7 + 100*q^8 + ...
For n = 4 the 14 overpartitions of 4 are [4], [4'], [2, 2], [2', 2], [3, 1], [3', 1], [3, 1'], [3', 1'], [2, 1, 1], [2', 1, 1], [2, 1', 1], [2', 1', 1], [1, 1, 1, 1], [1', 1, 1, 1]. - Omar E. Pol, Jan 19 2014
MAPLE
mul((1+x^n)/(1-x^n), n=1..256): seq(coeff(series(%, x, n+1), x, n), n=0..40);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
b(n, i-1) +2*add(b(n-i*j, i-1), j=1..n/i)))
end:
a:= n-> b(n$2):
a_list := proc(len) series(1/JacobiTheta4(0, x), x, len+1); seq(coeff(%, x, j), j=0..len) end: a_list(39); # Peter Luschny, Mar 14 2017
MATHEMATICA
max = 39; f[x_] := Exp[Sum[(DivisorSigma[1, 2*n] - DivisorSigma[1, n])*(x^n/n), {n, 1, max}]]; CoefficientList[ Series[f[x], {x, 0, max}], x] (* Jean-François Alcover, Jun 11 2012, after Joerg Arndt *) a[ n_] := SeriesCoefficient[ QHypergeometricPFQ[ {-1}, {}, x, x], {x, 0, n}]; (* Michael Somos, Mar 11 2014 *) Table[Sum[PartitionsP[n-k]*PartitionsQ[k], {k, 0, n}], {n, 0, 50}] (* Vaclav Kotesovec, Nov 28 2015 *) nmax = 100; p = ConstantArray[0, nmax+1]; p[[1]] = 1; Do[p[[n+1]] = 0; k = 1; While[n + 1 - k^2 > 0, p[[n+1]] += (-1)^(k+1)*p[[n + 1 - k^2]]; k++; ]; p[[n+1]] = 2*p[[n+1]]; , {n, 1, nmax}]; p (* Vaclav Kotesovec, Apr 11 2017 *) a[ n_] := SeriesCoefficient[ 1 / EllipticTheta[ 4, 0, x], {x, 0, n}]; (* Michael Somos, Nov 15 2018 *) a[n_] := Sum[2^Length[Union[IntegerPartitions[n][[i]]]], {i, 1, PartitionsP[n]}]; (* Richard Joseph Boland, Sep 02 2021 *) n = 39; CoefficientList[Product[(1 + x^k)/(1 - x^k), {k, 1, n}] + O[x]^(n + 1), x] (* Oliver Seipel, Sep 19 2021 *)
PROG
(PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^2 + A) / eta(x + A)^2, n))}; /* Michael Somos, Nov 01 2008 */ (PARI) {a(n)=polcoeff(exp(sum(m=1, n\2+1, 2*x^(2*m-1)/(1-x^(2*m-1)+x*O(x^n))/(2*m-1))), n)} /* Paul D. Hanna, Aug 06 2009 */ (PARI) N=66; x='x+O('x^N); gf=exp(sum(n=1, N, (sigma(2*n)-sigma(n))*x^n/n)); Vec(gf) /* Joerg Arndt, Jul 30 2011 */ (PARI) lista(nn) = {q='q+O('q^nn); Vec(eta(q^2)/eta(q)^2)} \\ Altug Alkan, Mar 20 2018 (Julia) # JacobiTheta4 is defined in A002448. A015128List(len) = JacobiTheta4(len, -1)
(SageMath) # uses[EulerTransform from A166861] a = BinaryRecurrenceSequence(0, 1, 1, 2)
b = EulerTransform(a)
CROSSREFS
See A004402 for a version with signs.
Triangle of numbers of partitions of n with total number of odd parts equal to k from {0,...,n}.
+10
136
1, 0, 1, 1, 0, 1, 0, 2, 0, 1, 2, 0, 2, 0, 1, 0, 4, 0, 2, 0, 1, 3, 0, 5, 0, 2, 0, 1, 0, 7, 0, 5, 0, 2, 0, 1, 5, 0, 9, 0, 5, 0, 2, 0, 1, 0, 12, 0, 10, 0, 5, 0, 2, 0, 1, 7, 0, 17, 0, 10, 0, 5, 0, 2, 0, 1, 0, 19, 0, 19, 0, 10, 0, 5, 0, 2, 0, 1, 11, 0, 28, 0, 20, 0, 10, 0, 5, 0, 2, 0, 1, 0, 30, 0, 33, 0, 20, 0, 10, 0, 5, 0, 2, 0, 1
COMMENTS
The partition (0) of n=0 is included. For n>0 no part 0 appears.
The first (k=0) column gives the number of partitions without odd parts, i.e., those with even parts only. See A035363. Without the alternating zeros this becomes a triangle with columns given by the rows of the S_n(m) table shown in the Riordan reference.
T(2n+k,k) = the number of partitions of n with parts 1..k of two kinds. If n<=k, then T(2n+k) = A000712(n), the number of partitions of n with parts of two kinds. T(2n+k) = the convolution of A000041(n) and the number of partitions of n+k having exactly k parts. T(2n+k) = d(n,k) where d(n,0) = p(n) and d(n,k) = d(n,k-1) + d(n-k,k-1) + d(n-2k,k-1) + ... (End)
T(n,k) = number of partitions (p1 >= p2 >= p3 >= ...) of n having alternating sum p1 - p2 + p3 - ... = k. Example: T(5,3) = 2 because there are two partitions (3,1,1) and (4,1) of 5 with alternating sum 3.
The equidistribution of the partition statistics "alternating sum" and "total number of odd parts" follows by conjugation. (End)
REFERENCES
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.
FORMULA
a(n, k) = number of partitions of n>=0, which have exactly k odd parts (and possibly even parts) for k from {0, ..., n}.
G.f.: G(t,x) = 1/Product_{j>=1} (1-t*x^(2*j-1))*(1-x^(2*j)). - Emeric Deutsch, Feb 17 2006 G.f. T(2n+k,k) = g.f. d(n,k) = (1/Product_{j=1..k} (1-x^j)) * g.f. p(n). - Gregory L. Simay, Oct 31 2015
EXAMPLE
The triangle a(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10
0: 1
1: 0 1
2: 1 0 1
3: 0 2 0 1
4: 2 0 2 0 1
5: 0 4 0 2 0 1
6: 3 0 5 0 2 0 1
7: 0 7 0 5 0 2 0 1
8: 5 0 9 0 5 0 2 0 1
9: 0 12 0 10 0 5 0 2 0 1
10: 7 0 17 0 10 0 5 0 2 0 1
a(0,0) = 1 because n=0 has no odd part, only one even part, 0, by definition. a(5,3) = 2 because there are two partitions (1,1,3) and (1,1,1,2) of 5 with exactly 3 odd parts.
T(10,4) = T(2*3+4,4) = d(3,4) = A000712(3) = 10. T(10,2) = T(2*4+2,2) = d(4,2) = d(4,1)+d(2,1)+d(0,1) = d(4,0)+d(3,0)+d(2,0)+d(1,0)+d(0,0) + d(2,0)+d(1,0)+d(0,0) + d(0,0) = convolution sum p(4)+p(3)+2*p(2)+2*p(1)+3*p(0) = 5+3+2*2+2*1+3*1 = 17.
T(9,1) = T(8,0) + T(7,1) = 5 + 7 = 12.
(End)
MAPLE
g:=1/product((1-t*x^(2*j-1))*(1-x^(2*j)), j=1..20): gser:=simplify(series(g, x=0, 22)): P[0]:=1: for n from 1 to 18 do P[n]:=coeff(gser, x^n) od: for n from 0 to 18 do seq(coeff(P[n], t, j), j=0..n) od; # yields sequence in triangular form # Emeric Deutsch, Feb 17 2006
MATHEMATICA
T[n_, k_] := T[n, k] = Which[n<k, 0, n == k, 1, Mod[n-k+1, 2] == 0, 0, k == 0, Sum[T[Quotient[n, 2], m], {m, 0, n}], True, T[n-1, k-1]+T[n-2*k, k]]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Mar 05 2014, after Paul D. Hanna *) Table[Length[Select[IntegerPartitions[n], Count[#, _?OddQ]==k&]], {n, 0, 15}, {k, 0, n}] (* Gus Wiseman, Jun 20 2021 *)
PROG
(PARI)
{T(n, k)=if(n>=k, if(n==k, 1, if((n-k+1)%2==0, 0, if(k==0, sum(m=0, n, T(n\2, m)), T(n-1, k-1)+T(n-2*k, k)))))}
for(n=0, 20, for(k=0, n, print1(T(n, k), ", ")); print(""))
CROSSREFS
The strict version (without zeros) is A152146 interleaved with A152157. The reverse version (without zeros) is the right half of A344612. The strict reverse version (without zeros) is the right half of A344739.
Number of palindromic partitions of n.
+10
126
1, 1, 2, 2, 4, 4, 7, 7, 12, 12, 19, 19, 30, 30, 45, 45, 67, 67, 97, 97, 139, 139, 195, 195, 272, 272, 373, 373, 508, 508, 684, 684, 915, 915, 1212, 1212, 1597, 1597, 2087, 2087, 2714, 2714, 3506, 3506, 4508, 4508, 5763, 5763, 7338, 7338, 9296, 9296, 11732, 11732, 14742, 14742, 18460, 18460, 23025, 23025, 28629, 28629
COMMENTS
That is, the number of partitions of n into parts which can be listed in palindromic order.
Alternatively, number of partitions of n into parts from the set {1,2,4,6,8,10,12,...}. - T. D. Noe, Aug 05 2005 Also number of partitions of n with at most one part occurring an odd number of times. - Reinhard Zumkeller, Dec 18 2013 The first Mathematica program computes terms of A025065; the second computes the k palindromic partitions of user-chosen n. - Clark Kimberling, Jan 20 2014 a(n) is the number of partitions p of n+1 such that 2*max(p) > n+1. - Clark Kimberling, Apr 20 2014. Also the number of integer partitions of n + 2 that are the vertex-degrees of some hypertree. For example, the a(6) = 7 partitions of 8 that are the vertex-degrees of some hypertree, together with a realizing hypertree are:
(41111): {{1,2},{1,3},{1,4},{1,5}}
(32111): {{1,2},{1,3},{1,4},{2,5}}
(22211): {{1,2},{1,3},{2,4},{3,5}}
(311111): {{1,2},{1,3},{1,4,5,6}}
(221111): {{1,2},{1,3},{2,4,5,6}}
(2111111): {{1,2},{1,3,4,5,6,7}}
(11111111): {{1,2,3,4,5,6,7,8}}
(End)
Conjecture: a(n) is the length of maximal initial segment of A308355(n-1) that is identical to row n of A128628, for n >= 2. - Clark Kimberling, May 24 2019 The Heinz numbers of palindromic partitions are given by A265640. The Heinz number of a partition (y_1,...,y_k) is prime(y_1)*...*prime(y_k), giving a bijective correspondence between positive integers and integer partitions. Also the number of integer partitions of n with a part greater than or equal to n/2. This is equivalent to Clark Kimberling's final comment above. The Heinz numbers of these partitions are given by A344414. For example, the a(1) = 1 through a(8) = 12 partitions are: (1) (2) (3) (4) (5) (6) (7) (8)
(11) (21) (22) (32) (33) (43) (44)
(31) (41) (42) (52) (53)
(211) (311) (51) (61) (62)
(321) (421) (71)
(411) (511) (422)
(3111) (4111) (431)
(521)
(611)
(4211)
(5111)
(41111)
Also the number of integer partitions of n with at least n/2 parts. The Heinz numbers of these partitions are given by A344296. For example, the a(1) = 1 through a(8) = 12 partitions are: (1) (2) (21) (22) (221) (222) (2221) (2222)
(11) (111) (31) (311) (321) (3211) (3221)
(211) (2111) (411) (4111) (3311)
(1111) (11111) (2211) (22111) (4211)
(3111) (31111) (5111)
(21111) (211111) (22211)
(111111) (1111111) (32111)
(41111)
(221111)
(311111)
(2111111)
(11111111)
(End)
FORMULA
G.f.: 1/((1-q)*prod(n>=1, 1-q^(2*n))). [ Joerg Arndt, Mar 11 2014]
EXAMPLE
The partitions for the first few values of n are as follows:
n: partitions .......................... number
1: 1 ................................... 1
2: 2 11 ................................ 2
3: 3 111 ............................... 2
4: 4 22 121 1111 ....................... 4
5: 5 131 212 11111 ..................... 4
6: 6 141 33 222 1221 11211 111111 ...... 7
7: 7 151 313 11311 232 21112 1111111 ... 7
Partitions into 1,2,4,6,... for the first values of n:
1: 1 ....................................... 1
2: 2 11 .................................... 2
3: 21 111 .................................. 2
4: 4 22 211 1111 ........................... 4
5: 41 221 2111 11111 ....................... 4
6: 6 42 4211 222 2211 21111 111111.......... 7
7: 61 421 42111 2221 22111 211111 1111111 .. 7. (End)
MATHEMATICA
Map[Length[Select[IntegerPartitions[#], Count[OddQ[Transpose[Tally[#]][[2]]], True] <= 1 &]] &, Range[40]] (* Peter J. C. Moses, Jan 20 2014 *) n = 8; Select[IntegerPartitions[n], Count[OddQ[Transpose[Tally[#]][[2]]], True] <= 1 &] (* Peter J. C. Moses, Jan 20 2014 *) CoefficientList[Series[1/((1 - x) Product[1 - x^(2 n), {n, 1, 50}]), {x, 0, 60}], x] (* Clark Kimberling, Mar 14 2014 *)
PROG
(Haskell)
a025065 = p (1:[2, 4..]) where
p [] _ = 0
p _ 0 = 1
p ks'@(k:ks) m | m < k = 0
| otherwise = p ks' (m - k) + p ks m
(Haskell)
import Data.List (group)
a025065 = length . filter (<= 1) .
map (sum . map ((`mod` 2) . length) . group) . ps 1
where ps x 0 = [[]]
ps x y = [t:ts | t <- [x..y], ts <- ps t (y - t)]
(PARI) N=66; q='q+O('q^N); Vec( 1/((1-q)*eta(q^2)) ) \\ Joerg Arndt, Mar 11 2014
CROSSREFS
The ordered version (palindromic compositions) is A016116. The case of palindromic prime signature is A242414. Palindromic partitions are ranked by A265640, with complement A229153. The case of palindromic plane trees is A319436. The multiplicative version (palindromic factorizations) is A344417. A000569 counts graphical partitions.
Cf. A000041, A067538, A143773, A209816, A338914, A338915, A340387, A344296, A344414, A344415, A344416.
EXTENSIONS
Prepended a(0)=1, added more terms, Joerg Arndt, Mar 11 2014
Number of partitions of n if there are two kinds of 1's and two kinds of 2's.
(Formerly M1361 N0525)
+10
74
1, 2, 5, 9, 17, 28, 47, 73, 114, 170, 253, 365, 525, 738, 1033, 1422, 1948, 2634, 3545, 4721, 6259, 8227, 10767, 13990, 18105, 23286, 29837, 38028, 48297, 61053, 76926, 96524, 120746, 150487, 187019, 231643, 286152, 352413, 432937, 530383, 648245
COMMENTS
Also number of partitions of 2*n with exactly 2 odd parts (offset 1). - Vladeta Jovovic, Jan 12 2005 Also number of transitions from one partition of n+2 to another, where a transition consists of replacing any two parts with their sum. Remove all 1' and 2' from the partition, replacing them with ((number of 2') + 1) and ((number of 1') + (number of 2') + 1); these are the two parts being summed. Number of partitions of n into parts of 2 kinds with at most 2 parts of the second kind, or of n+2 into parts of 2 kinds with exactly 2 parts of the second kind. - Franklin T. Adams-Watters, Mar 20 2006 From Christian Gutschwager (gutschwager(AT)math.uni-hannover.de), Feb 10 2010: (Start)
a(n) is also the number of pairs of partitions of n+2 which differ by only one box (for bijection see Gutschwager link).
a(n) is also the number of partitions of n with two parts marked.
a(n) is also the number of partitions of n+1 with two different parts marked. (End)
a(n) = P(/2,n), a particular case of P(/k,n) defined as follows: P(/0,n) = A000041(n) and P(/k,n) = P(/k-1, n) + P(/k-1,n-k) + P(/k-1, n-2k) + ... Also, P(/k,n) = the convolution of A000041 and the partitions of n with exactly k parts, and g.f. P(/k,n) = (g.f. for P(n)) * 1/(1-x)...(1-x^k). - Gregory L. Simay, Mar 22 2018 a(n) is also the sum of binomial(D(p),2) in partitions p of (n+3), where D(p)= number of different sizes of parts in p. - Emily Anible, Apr 03 2018 Also partitions of 2*(n+1) with alternating sum 2. Also partitions of 2*(n+1) with reverse-alternating sum -2 or 2. - Gus Wiseman, Jun 21 2021 Define the distance graph of the partitions of n using the distance function in A366156 as follows: two vertices (partitions) share an edge if and only if the distance between the vertices is 2. Then a(n) is the number of edges in the distance graph of the partitions of n. - Clark Kimberling, Oct 12 2023
REFERENCES
H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.
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).
FORMULA
Euler transform of 2 2 1 1 1 1 1...
G.f.: 1/( (1-x) * (1-x^2) * Product_{k>=1} (1-x^k) ).
a(n) = Sum_{j=0..floor(n/2)} A000070(n-2*j), n>=0. a(n) ~ sqrt(3) * exp(Pi*sqrt(2*n/3)) / (4*Pi^2) * (1 + 35*Pi/(24*sqrt(6*n))). - Vaclav Kotesovec, Aug 18 2015, extended Nov 05 2016
EXAMPLE
a(3) = 9 because we have 3, 2+1, 2+1', 2'+1, 2'+1', 1+1+1, 1+1+1', 1+1'+1' and 1'+1'+1'.
The a(0) = 1 through a(4) = 9 partitions of 2*(n+1) with exactly 2 odd parts:
(1,1) (3,1) (3,3) (5,3)
(2,1,1) (5,1) (7,1)
(3,2,1) (3,3,2)
(4,1,1) (4,3,1)
(2,2,1,1) (5,2,1)
(6,1,1)
(3,2,2,1)
(4,2,1,1)
(2,2,2,1,1)
The a(0) = 1 through a(4) = 9 partitions of 2*(n+1) with alternating sum 2:
(2) (3,1) (4,2) (5,3)
(2,1,1) (2,2,2) (3,3,2)
(3,2,1) (4,3,1)
(3,1,1,1) (3,2,2,1)
(2,1,1,1,1) (4,2,1,1)
(2,2,2,1,1)
(3,2,1,1,1)
(3,1,1,1,1,1)
(2,1,1,1,1,1,1)
(End)
MAPLE
with(numtheory): etr:= proc(p) local b; b:=proc(n) option remember; local d, j; if n=0 then 1 else add(add(d*p(d), d=divisors(j)) *b(n-j), j=1..n)/n fi end end: a:= etr(n->`if`(n<3, 2, 1)): seq(a(n), n=0..40); # Alois P. Heinz, Sep 08 2008
MATHEMATICA
CoefficientList[Series[1/((1 - x) (1 - x^2) Product[1 - x^k, {k, 1, 100}]), {x, 0, 100}], x] (* Ben Branman, Mar 07 2012 *) etr[p_] := Module[{b}, b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*p[d], {d, Divisors[j]}]*b[n - j], {j, 1, n}]/n]; b]; a = etr[If[# < 3, 2, 1]&]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Apr 09 2014, after Alois P. Heinz *) Table[Length@IntegerPartitions[n, All, Join[{1, 2}, Range[n]]], {n, 0, 15}] (* Robert Price, Jul 28 2020 and Jun 21 2021 *) T[n_, 0] := PartitionsP[n];
T[n_, m_] /; (n >= m (m + 1)/2) := T[n, m] = T[n - m, m - 1] + T[n - m, m];
T[_, _] = 0;
a[n_] := T[n + 3, 2];
ats[y_]:=Sum[(-1)^(i-1)*y[[i]], {i, Length[y]}]; Table[Length[Select[IntegerPartitions[n], ats[#]==2&]], {n, 0, 30, 2}] (* Gus Wiseman, Jun 21 2021*)
PROG
(PARI) my(x = 'x + O('x^66)); Vec( 1/((1-x)*(1-x^2)*eta(x)) ) \\ Joerg Arndt, Apr 29 2013
CROSSREFS
The case of reverse-alternating sum 1 or alternating sum 0 is A000041. The case of reverse-alternating sum -1 or alternating sum 1 is A000070. The case of reverse-alternating sum 2 is A120452. The case of reverse-alternating sum -2 is A344741. A001700 counts compositions with alternating sum 2.
A035363 counts partitions into even parts.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A124754 gives alternating sums of standard compositions (reverse: A344618).
A316524 is the alternating sum of the prime indices of n (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
Cf. A006330, A027187, A239830, A306145, A343941, A344607, A344608, A344619, A344650, A344651, A344740.
EXTENSIONS
More terms from Pab Ter (pabrlos(AT)yahoo.com), May 04 2004
G.f.: Product_{k>=1} (1 + x^(2*k - 1)) / (1 - x^(2*k)).
(Formerly M0524)
+10
67
1, 1, 1, 2, 3, 4, 5, 7, 10, 13, 16, 21, 28, 35, 43, 55, 70, 86, 105, 130, 161, 196, 236, 287, 350, 420, 501, 602, 722, 858, 1016, 1206, 1431, 1687, 1981, 2331, 2741, 3206, 3740, 4368, 5096, 5922, 6868, 7967, 9233, 10670, 12306, 14193, 16357, 18803, 21581
COMMENTS
Also the number of partitions of n in which all odd parts are distinct. There is no restriction on the even parts. E.g., a(9)=13 because "9 = 8+1 = 7+2 = 6+3 = 6+2+1 = 5+4 = 5+3+1 = 5+2+2 = 4+4+1 = 4+3+2 = 4+2+2+1 = 3+2+2+2 = 2+2+2+2+1". - Noureddine Chair, Feb 03 2005 Number of partitions of n in which each even part occurs with even multiplicity. There is no restriction on the odd parts.
Also the number of partitions of n into parts not congruent to 2 mod 4. - James A. Sellers, Feb 08 2002 Coincides with the sequence of numbers of nilpotent conjugacy classes in the Lie algebras o(n) of skew-symmetric n X n matrices, n=0,1,2,3,... (the cases n=0,1 being degenerate). This sequence, A015128 and A000041 together cover the nilpotent conjugacy classes in the classical A,B,C,D series of Lie algebras. - Alexander Elashvili, Sep 08 2003 Poincaré series [or Poincare series] (or Molien series) for symmetric invariants in F_2(b_1, b_2, ... b_n) ⊗ E(e_1, e_2, ... e_n) with b_i 2-dimensional, e_i one-dimensional and the permutation action of S_n, in the case n=2.
It appears that this sequence is related to the generalized hexagonal numbers ( A000217) in the same way as the partition numbers A000041 are related to the generalized pentagonal numbers A001318. (See the table in comments section of A195825.) Conjecture: this is 1 together with the row sums of triangle A195836, also column 1 of A195836, also column 2 of the square array A195825. - Omar E. Pol, Oct 09 2011 Since this is also column 2 of A195825 so the sequence contains only one plateau [1, 1, 1] of level 1 and length 3. For more information see A210843. - Omar E. Pol, Jun 27 2012 Also the number of ways to stack n triangles in a valley (pointing upwards or downwards depending on row parity). - Seiichi Manyama, Jul 07 2018
REFERENCES
A. Adem and R. J. Milgram, Cohomology of Finite Groups, Springer-Verlag, 2nd. ed., 2004; p. 108.
M. D. Hirschhorn, The Power of q, Springer, 2017. See pod, page 297.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
FORMULA
Expansion of 1 / psi(-x) in powers of x where psi() is a Ramanujan theta function.
Expansion of q^(1/8) * eta(q^2) / (eta(q) * eta(q^4)) in powers of q.
G.f.: exp( Sum_{n>=1} [Sum_{d|n} (-1)^(n-d)*d] * x^n/n ). - Paul D. Hanna, Jul 22 2009 a(n) ~ (8*n+1) * cosh(sqrt(8*n-1)*Pi/4) / (16*sqrt(2)*n^2) - sinh(sqrt(8*n-1)*Pi/4) / (2*Pi*n^(3/2)) ~ exp(Pi*sqrt(n/2))/(4*sqrt(2)*n) * (1 - (2/Pi + Pi/16)/sqrt(2*n) + (3/16 + Pi^2/1024)/n). - Vaclav Kotesovec, Aug 17 2015, extended Jan 09 2017 Can be computed recursively by Sum_{j>=0} (-1)^(ceiling(j/2)) a(n - j(j+1)/2) = 0, for n > 0. [Merca, Theorem 4.3] - Eric M. Schmidt, Sep 21 2017
EXAMPLE
G.f. = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 5*x^6 + 7*x^7 + 10*x^8 + 13*x^9 + ...
G.f. = q^-1 + q^7 + q^15 + 2*q^23 + 3*q^31 + 4*q^39 + 5*q^47 + 7*q^55 + 10*q^63 + ...
n | the ways to stack n triangles in a valley
--+------------------------------------------------------
1 | *---*
| \ /
| *
|
2 | *
| / \
| *---*
| \ /
| *
|
3 | *---* *---*
| / \ / \ / \
| *---* *---*
| \ / \ /
| * *
|
4 | * *
| / \ / \
| *---* *---*---* *---*
| / \ / \ / \ / \ / \
| *---* *---* *---*
| \ / \ / \ /
| * * *
|
5 | *---* * * *---*
| / \ / / \ / \ \ / \
| *---* *---*---* *---*---* *---*
| / \ / \ / \ / \ / \ / \ / \
| *---* *---* *---* *---*
| \ / \ / \ / \ /
| * * * *
|
6 | *
| / \
| *---* *---* * * *---*
| / \ / / \ / / \ / \ \ / \
| *---* *---*---* *---*---* *---*---*
| / \ / \ / \ / \ / \ / \ / \ /
| *---* *---* *---* *---*
| \ / \ / \ / \ /
| * * * *
| *
| / \
| *---*
| \ / \
| *---*
| \ / \
| *---*
| \ /
| *
(End)
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
b(n, i-1)+`if`(i>n, 0, b(n-i, i-irem(i, 2)))))
end:
a:= n-> b(n, n):
MATHEMATICA
CoefficientList[ Series[ Product[(1 + x^(2k - 1))/(1 - x^(2k)), {k, 25}], {x, 0, 50}], x] (* Robert G. Wilson v, Jun 28 2012 *) CoefficientList[Series[x*QPochhammer[-1/x, x^2] / ((1+x)*QPochhammer[x^2, x^2]), {x, 0, 50}], x] (* Vaclav Kotesovec, Aug 17 2015 *) CoefficientList[Series[2*(-x)^(1/8) / EllipticTheta[2, 0, Sqrt[-x]], {x, 0, 50}], x] (* Vaclav Kotesovec, Aug 17 2015 *) b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, b[n, i-1] + If[i>n, 0, b[n-i, i-Mod[i, 2]]]]];
a[n_] := b[n, n];
PROG
(PARI) {a(n)=polcoeff(exp(sum(m=1, n+1, sumdiv(m, d, (-1)^(m-d)*d)*x^m/m)+x*O(x^n)), n)} \\ Paul D. Hanna, Jul 22 2009 (GW-BASIC)' A program with two A-numbers (Note that here A000217 are the generalized hexagonal numbers): 20 For n = 1 to 51: For j = 1 to n
40 Next j: Print a(n-1); : Next n ' Omar E. Pol, Jun 10 2012
Search completed in 0.113 seconds
|