This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A000009 M0281 N0100 #566 Jul 28 2025 10:06:31
%S A000009 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,
%T A000009 142,165,192,222,256,296,340,390,448,512,585,668,760,864,982,1113,
%U A000009 1260,1426,1610,1816,2048,2304,2590,2910,3264,3658,4097,4582,5120,5718,6378
%N A000009 Expansion of Product_{m >= 1} (1 + x^m); number of partitions of n into distinct parts; number of partitions of n into odd parts.
%C A000009 Partitions into distinct parts are sometimes called "strict partitions".
%C A000009 Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).
%C A000009 The result that number of partitions of n into distinct parts = number of partitions of n into odd parts is due to Euler.
%C A000009 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.
%C A000009 Euler transform of period 2 sequence [1,0,1,0,...]. - _Michael Somos_, Dec 16 2002
%C A000009 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
%C A000009 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
%C A000009 Number of partitions of n where if k is the largest part, all parts 1..k are present. - _Jon Perry_, Sep 21 2005
%C A000009 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
%C A000009 The number of connected threshold graphs having n edges. - Michael D. Barrus (mbarrus2(AT)uiuc.edu), Jul 12 2007
%C A000009 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
%C A000009 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
%C A000009 Equals A035363 convolved with A010054. The convolution square of A000009 = A022567 = A000041 convolved with A010054. A000041 = A000009 convolved with A035363. - _Gary W. Adamson_, Jun 11 2009
%C A000009 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
%C A000009 Equals left border of triangle A091602 starting with offset 1. - _Gary W. Adamson_, Mar 13 2010
%C A000009 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
%C A000009 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
%C A000009 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
%C A000009 Ewell (1973) gives a number of recurrences. - _N. J. A. Sloane_, Jan 14 2020
%C A000009 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
%C A000009 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
%C A000009 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]
%C A000009 The g.f. Product_{k >= 0} 1 + x^k = Product_{k >= 0} 1 - x^k + 2*x^k == Product_{k >= 0} 1 - x^k == Sum_{k in Z} (-1)^k*x^(k*(3*k-1)/2) (mod 2) by Euler's pentagonal number theorem. It follows that a(n) is odd iff n = k*(3*k - 1)/2 for some integer k, i.e., iff n is a generalized pentagonal number A001318. - _Peter Bala_, Jan 07 2025
%D A000009 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).
%D A000009 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.
%D A000009 George E. Andrews, The Theory of Partitions, Cambridge University Press, 1998, p. 19.
%D A000009 George E. Andrews, Number Theory, Dover Publications, 1994, Theorem 12-3, pp. 154-5, and (13-1-1) p. 163.
%D A000009 Raymond Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; see p. 196.
%D A000009 T. J. I'a. Bromwich, Introduction to the Theory of Infinite Series, Macmillan, 2nd. ed. 1949, p. 116, Problem 18.
%D A000009 Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 99.
%D A000009 William Dunham, The Mathematical Universe, pp. 57-62, J. Wiley, 1994.
%D A000009 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.
%D A000009 Ian P. Goulden and David M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (2.5.1).
%D A000009 G. H. Hardy, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 86.
%D A000009 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.
%D A000009 Carlos J. Moreno and Samuel S. Wagstaff, Jr., Sums of Squares of Integers, Chapman and Hall, 2006, p. 253.
%D A000009 Srinivasa Ramanujan, Collected Papers, Ed. G. H. Hardy et al., Cambridge 1927; Chelsea, NY, 1962. See Table V on page 309.
%D A000009 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000009 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A000009 James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 288-290.
%H A000009 Felix Huber, <a href="/A000009/b000009.txt">Table of n, a(n) for n = 0..10000</a> (terms up to n=2000 from N. J. A. Sloane, up to n=5000 from Reinhard Zumkeller)
%H A000009 Joerg Arndt, <a href="http://www.jjj.de/fxt/#fxtbook">Matters Computational (The Fxtbook)</a>, pp. 348-350.
%H A000009 M. Abramowitz and I. A. Stegun, eds., <a href="http://www.convertit.com/Go/ConvertIt/Reference/AMS55.ASP">Handbook of Mathematical Functions</a>, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy], p. 836.
%H A000009 Francesca Aicardi, <a href="https://doi.org/10.1007/s11853-011-0045-z">Matricial formulae for partitions</a>, Functional Analysis and Other Mathematics, Vol. 3, No. 2 (2011), pp. 127-133; <a href="http://arxiv.org/abs/0806.1273">arXiv preprint</a>, arXiv:0806.1273 [math.NT], 2008.
%H A000009 George E. Andrews, <a href="http://dx.doi.org/10.1090/S0273-0979-07-01180-9">Euler's "De Partitio Numerorum"</a>, Bull. Amer. Math. Soc., 44 (No. 4, 2007), 561-573.
%H A000009 George E. Andrews, <a href="https://georgeandrews1.github.io/pdf/320.pdf">The Bhargava-Adiga Summation and Partitions</a>, 2016. See page 4 equation (2.2).
%H A000009 Brennan Benfield and Arindam Roy, <a href="https://arxiv.org/abs/2404.03153">Log-concavity And The Multiplicative Properties of Restricted Partition Functions</a>, arXiv:2404.03153 [math.NT], 2024.
%H A000009 Helena Bergold, Lukas Egeling, and Hung. P. Hoang, <a href="https://arxiv.org/abs/2411.19208">Signotopes with few plus signs</a>, arXiv:2411.19208 [math.CO], 2024. See p. 14.
%H A000009 Andreas B. G. Blobel, <a href="https://arxiv.org/abs/1904.07808">An Asymptotic Form of the Generating Function Prod_{k=1,oo} (1+x^k/k)</a>, arXiv:1904.07808 [math.CO], 2019.
%H A000009 Alexander Bors, Michael Giudici, and Cheryl E. Praeger, <a href="https://arxiv.org/abs/1910.12570">Documentation for the GAP code file OrbOrd.txt</a>, arXiv:1910.12570 [math.GR], 2019.
%H A000009 Henry Bottomley, <a href="/A000009/a000009.gif">Illustration for A000009, A000041, A047967</a>.
%H A000009 Andrés Eduardo Caicedo and Brittany Shelton, <a href="https://doi.org/10.1080/0025570X.2018.1403233">Of puzzles and partitions: Introducing Partiti</a>, Mathematics Magazine, Vol. 91, No. 1 (2018), pp. 20-23; <a href="https://arxiv.org/abs/1710.04495">arXiv preprint</a>, arXiv:1710.04495 [math.HO], 2017.
%H A000009 Huantian Cao, <a href="http://cobweb.cs.uga.edu/~rwr/STUDENTS/hcao.html">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002.
%H A000009 Huantian Cao, <a href="/A000009/a000009.pdf">AutoGF: An Automated System to Calculate Coefficients of Generating Functions</a>, thesis, 2002. [Local copy, with permission]
%H A000009 H. B. C. Darling, Collected Papers of Ramanujan, <a href="http://www.imsc.res.in/~rao/ramanujan/CamUnivCpapers/Cpaper36/page34.htm">Table for q(n); n=1 through 100</a>.
%H A000009 Alejandro Erickson and Mark Schurch, <a href="https://doi.org/10.1016/j.jda.2012.04.002">Monomer-dimer tatami tilings of square regions</a>, Journal of Discrete Algorithms, Vol. 16 (2012), pp. 258-269; <a href="http://arxiv.org/abs/1110.5103">arXiv preprint</a>, arXiv:1110.5103 [math.CO], 2011.
%H A000009 John A. Ewell, <a href="https://doi.org/10.1016/0097-3165(73)90070-8">Partition recurrences</a>, J. Comb. Theory A, Vol. 14, 125-127, 1973.
%H A000009 Philippe Flajolet and Robert Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, Cambridge University Press, 2009; see pages 48 and 499.
%H A000009 Evangelos Georgiadis, <a href="https://web.archive.org/web/20131109101330/http://web.mit.edu/egeorg/Public/Partitions/PartitionsQ.pdf">Computing Partition Numbers q(n)</a>, Technical Report, February (2009).
%H A000009 Benjamin Hackl, <a href="https://www.youtube.com/watch?v=M4TmnYxS4gk">5 + 5 + 1 + 1 + 1 = 10 + 2 + 1, and why there is more to it than you think.</a>, YouTube video, 2022.
%H A000009 Cristiano Husu, <a href="https://doi.org/10.1016/j.jnt.2018.05.005">The butterfly sequence: the second difference sequence of the numbers of integer partitions with distinct parts</a>, Journal of Number Theory, Vol. 193 (2018), pp. 171-188; <a href="https://arxiv.org/abs/1804.09883">arXiv preprint</a>, arXiv:1804.09883 [math.NT], 2018.
%H A000009 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=108">Encyclopedia of Combinatorial Structures 108</a>.
%H A000009 Martin Klazar, <a href="http://arxiv.org/abs/1808.08449">What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I</a>, arXiv:1808.08449 [math.CO], 2018.
%H A000009 Vaclav Kotesovec, <a href="http://arxiv.org/abs/1509.08708">A method of finding the asymptotics of q-series based on the convolution of generating functions</a>, arXiv:1509.08708 [math.CO], 2015-2016.
%H A000009 Vaclav Kotesovec, <a href="http://mathematica.stackexchange.com/questions/130741/getting-wrong-limit-with-bessel">Getting wrong limit with Bessel</a>, Mathematica Stack Exchange, Nov 09 2016.
%H A000009 Alain Lascoux, <a href="http://dx.doi.org/10.1016/j.disc.2002.02.001">Sylvester's bijection between strict and odd partitions</a>, Discrete Math., Vol. 277, No. 1-3 (2004), pp. 275-278.
%H A000009 Jeremy Lovejoy, <a href="https://doi.org/10.1112/S0024609302001492">The number of partitions into distinct parts modulo powers of 5</a>, Bulletin of the London Mathematical Society, Vol. 35, No. 1 (2003), pp. 41-46; <a href="http://lovejoy.perso.math.cnrs.fr/5powersQ.pdf">alternative link</a>.
%H A000009 James Mc Laughlin, Andrew V. Sills, and Peter Zimmer, <a href="https://doi.org/10.37236/36">Rogers-Ramanujan-Slater Type Identities</a>, Electronic J. Combinatorics, DS15, 1-59, May 31, 2008; see also <a href="https://arxiv.org/abs/1901.00946">arXiv version</a>, arXiv:1901.00946 [math.NT], 2019.
%H A000009 Günter Meinardus, <a href="https://eudml.org/doc/169463">Über Partitionen mit Differenzenbedingungen</a>, Mathematische Zeitschrift (1954/55), Volume 61, page 289-302.
%H A000009 Mircea Merca, <a href="http://dx.doi.org/10.1016/j.jnt.2015.08.014">Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer</a>, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, function q(n).
%H A000009 Mircea Merca, <a href="https://doi.org/10.1007/s11139-016-9856-3">The Lambert series factorization theorem</a>, The Ramanujan Journal, Vol. 44, No. 2 (2017), pp. 417-435; <a href="https://www.researchgate.net/publication/312324402">alternative link</a>.
%H A000009 István Mező, <a href="https://arxiv.org/abs/1106.2703">Several special values of Jacobi theta functions</a> arXiv:1106.2703v3 [math.CA], 2011-2013.
%H A000009 Donald J. Newman, <a href="http://dx.doi.org/10.1007/978-1-4613-8214-0">A Problem Seminar</a>, pp. 18;93;102-3 Prob. 93 Springer-Verlag NY 1982.
%H A000009 Hieu D. Nguyen and Douglas Taggart, <a href="http://citeseerx.ist.psu.edu/pdf/8f2f36f22878c984775ed04368b8893879b99458">Mining the OEIS: Ten Experimental Conjectures</a>, 2013. Mentions this sequence.
%H A000009 Kimeu Arphaxad Ngwava, Nick Gill, and Ian Short, <a href="https://arxiv.org/abs/2005.13869">Nilpotent covers of symmetric groups</a>, arXiv:2005.13869 [math.GR], 2020.
%H A000009 Matthew Parker, <a href="https://oeis.org/A000009/a000009_100K.7z">The first 100K terms (7-Zip compressed file)</a>.
%H A000009 Marko Riedel, <a href="https://math.stackexchange.com/questions/3063971/">Proof of recurrence by V. Jovovic</a>.
%H A000009 Ed Sandifer, How Euler Did It, <a href="http://eulerarchive.maa.org/hedi/HEDI-2005-10.pdf">Philip Naude's problem</a>.
%H A000009 Michael Somos, <a href="/A010815/a010815.txt">Introduction to Ramanujan theta functions</a>.
%H A000009 Zhi-Wei Sun, <a href="https://mathoverflow.net/questions/444761">A representation problem involving strict partition numbers</a>, Question 444761 at MathOverflow, April 14, 2023.
%H A000009 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PartitionFunctionP.html">Partition Function P</a>, <a href="https://mathworld.wolfram.com/PartitionFunctionQ.html">Partition Function Q</a>, <a href="https://mathworld.wolfram.com/PartitionFunctionb.html">Partition Function bk</a>, <a href="https://mathworld.wolfram.com/EulerIdentity.html">Euler Identity</a>, <a href="https://mathworld.wolfram.com/RamanujanThetaFunctions.html">Ramanujan Theta Functions</a>, <a href="https://mathworld.wolfram.com/q-PochhammerSymbol.html">q-Pochhammer Symbol</a>.
%H A000009 Wikipedia, <a href="https://en.wikipedia.org/wiki/Glaisher%27s_theorem">Glaisher's Theorem</a>.
%H A000009 Wolfram Research, <a href="http://functions.wolfram.com/IntegerFunctions/PartitionsQ/11">Generating functions for q(n)</a>.
%H A000009 Mingjia Yang and Doron Zeilberger, <a href="https://arxiv.org/abs/1910.08989">Systematic Counting of Restricted Partitions</a>, arXiv:1910.08989 [math.CO], 2019.
%H A000009 Michael P. Zaletel and Roger S. K. Mong, <a href="https://doi.org/10.1103/PhysRevB.86.245305">Exact matrix product states for quantum Hall wave functions</a>, Physical Review B, Vol. 86, No. 24 (2012), 245305; <a href="http://arxiv.org/abs/1208.4862">arXiv preprint</a>, arXiv:1208.4862 [cond-mat.str-el], 2012. - From _N. J. A. Sloane_, Dec 25 2012
%H A000009 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000009 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).
%F A000009 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
%F A000009 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).
%F A000009 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).
%F A000009 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
%F A000009 a(n) = t(n, 0), t as defined in A079211.
%F A000009 a(n) = Sum_{k=0..n-1} A117195(n,k) = A117192(n) + A117193(n) for n>0. - _Reinhard Zumkeller_, Mar 03 2006
%F A000009 a(n) = A026837(n) + A026838(n) = A118301(n) + A118302(n); a(A001318(n)) = A051044(n); a(A090864(n)) = A118303(n). - _Reinhard Zumkeller_, Apr 22 2006
%F A000009 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
%F A000009 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
%F A000009 Expansion of q^(-1/24) * eta(q^2) / eta(q) in powers of q.
%F A000009 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
%F A000009 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
%F A000009 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
%F A000009 From Evangelos Georgiadis, Andrew V. Sutherland, Kiran S. Kedlaya (egeorg(AT)mit.edu), Mar 03 2009: (Start)
%F A000009 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)
%F A000009 From _Gary W. Adamson_, Jun 13 2009: (Start)
%F A000009 The product g.f. = (1/(1-x))*(1/(1-x^3))*(1/(1-x^5))*...; = (1,1,1,...)*
%F A000009 (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,...) * ...; =
%F A000009 a*b*c*... where a, a*b, a*b*c, ... converge to A000009:
%F A000009 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, ... = a*b
%F A000009 1, 1, 1, 2, 2, 3, 4, 4, 5, 6, ... = a*b*c
%F A000009 1, 1, 1, 2, 2, 3, 4, 5, 6, 7, ... = a*b*c*d
%F A000009 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ... = a*b*c*d*e
%F A000009 1, 1, 1, 2, 2, 3, 4, 5, 6, 8, ... = a*b*c*d*e*f
%F A000009 ... (cf. analogous example in A000041). (End)
%F A000009 a(A004526(n)) = A172033(n). - _Reinhard Zumkeller_, Jan 23 2010
%F A000009 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
%F A000009 a(n) = A054242(n,0) = A201377(n,0). - _Reinhard Zumkeller_, Dec 02 2011
%F A000009 G.f.: 1/2 (-1; x)_{inf} where (a; q)_k is the q-Pochhammer symbol. - _Vladimir Reshetnikov_, Apr 24 2013
%F A000009 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
%F A000009 a(n) = A067661(n) + A067659(n). _Wolfdieter Lang_, Jan 18 2016
%F A000009 From _Vaclav Kotesovec_, May 29 2016: (Start)
%F A000009 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).
%F A000009 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)).
%F A000009 (End)
%F A000009 a(n) = A089806(n)*A010815(floor(n/2)) + a(n-1) + a(n-2) - a(n-5) - a(n-7) + a(n-12) + ... + A057077(m-1)*a(n-A001318(m)) + ..., where n > A001318(m). - _Gevorg Hmayakyan_, Jul 07 2016
%F A000009 a(n) ~ Pi*BesselI(1, Pi*sqrt((n+1/24)/3)) / sqrt(24*n+1). - _Vaclav Kotesovec_, Nov 08 2016
%F A000009 a(n) = A000041(n) - A047967(n). - _R. J. Mathar_, Nov 20 2017
%F A000009 Sum_{n>=1} 1/a(n) = A237515. - _Amiram Eldar_, Nov 15 2020
%F A000009 From _Peter Bala_, Jan 15 2021: (Start)
%F A000009 G.f.: (1 + x)*Sum_{n >= 0} x^(n*(n+3)/2)/Product_{k = 1..n} (1 - x^k) =
%F A000009 (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) = ....
%F A000009 G.f.: (1/2)*Sum_{n >= 0} x^(n*(n-1)/2)/Product_{k = 1..n} (1 - x^k) =
%F A000009 (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) = ....
%F A000009 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)
%F A000009 From _Peter Bala_, Feb 02 2021: (Start)
%F A000009 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.)
%F A000009 Similarly, A(x) = Sum_{n >= 0} x^(n*(2*n+1))/Product_{k = 1..2*n+1} (1 - x^k). (End)
%F A000009 a(n) = A001227(n) + A238005(n) + A238006(n). - _R. J. Mathar_, Sep 08 2021
%F A000009 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
%F A000009 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]
%F A000009 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
%e A000009 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 + ...
%e A000009 G.f. = q + q^25 + q^49 + 2*q^73 + 2*q^97 + 3*q^121 + 4*q^145 + 5*q^169 + ...
%e A000009 The partitions of n into distinct parts (see A118457) for small n are:
%e A000009 1: 1
%e A000009 2: 2
%e A000009 3: 3, 21
%e A000009 4: 4, 31
%e A000009 5: 5, 41, 32
%e A000009 6: 6, 51, 42, 321
%e A000009 7: 7, 61, 52, 43, 421
%e A000009 8: 8, 71, 62, 53, 521, 431
%e A000009 ...
%e A000009 From _Reinhard Zumkeller_, Jun 13 2009: (Start)
%e A000009 a(8)=6, A140207(8)=#{5+2+1,4+3+1}=2, A003056(8)=3, A051162(8)=5;
%e A000009 a(9)=8, A140207(9)=#{6+2+1,5+3+1,4+3+2}=3, A003056(9)=3, A051162(9)=6;
%e A000009 a(10)=10, A140207(10)=#{4+3+2+1}=1, A003056(10)=4, A051162(10)=4. (End)
%p A000009 N := 100; t1 := series(mul(1+x^k,k=1..N),x,N); A000009 := proc(n) coeff(t1,x,n); end;
%p A000009 spec := [ P, {P=PowerSet(N), N=Sequence(Z,card>=1)} ]: [ seq(combstruct[count](spec, size=n), n=0..58) ];
%p A000009 spec := [ P, {P=PowerSet(N), N=Sequence(Z,card>=1)} ]: combstruct[allstructs](spec, size=10); # to get the actual partitions for n=10
%p A000009 A000009 := proc(n)
%p A000009 local x,m;
%p A000009 product(1+x^m,m=1..n+1) ;
%p A000009 expand(%) ;
%p A000009 coeff(%,x,n) ;
%p A000009 end proc: # _R. J. Mathar_, Jun 18 2016
%p A000009 lim := 99; # Enlarge if more terms are needed.
%p A000009 simplify(expand(QDifferenceEquations:-QPochhammer(-1, x, lim)/2, x)):
%p A000009 seq(coeff(%, x, n), n=0..55); # _Peter Luschny_, Nov 17 2016
%p A000009 # Alternative:
%p A000009 a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*add(
%p A000009 `if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
%p A000009 end:
%p A000009 seq(a(n), n=0..55); # _Alois P. Heinz_, Jun 24 2025
%t A000009 PartitionsQ[Range[0, 60]] (* _Harvey Dale_, Jul 27 2009 *)
%t A000009 a[ n_] := SeriesCoefficient[ Product[ 1 + x^k, {k, n}], {x, 0, n}]; (* _Michael Somos_, Jul 06 2011 *)
%t A000009 a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^k, {k, 1, n, 2}], {x, 0, n}]; (* _Michael Somos_, Jul 06 2011 *)
%t A000009 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 *)
%t A000009 a[ n_] := SeriesCoefficient[ 1 / QPochhammer[ x, x^2], {x, 0, n}]; (* _Michael Somos_, May 24 2013 *)
%t A000009 a[ n_] := SeriesCoefficient[ Series[ QHypergeometricPFQ[ {q}, {q x}, q, - q x], {q, 0, n}] /. x -> 1, {q, 0, n}]; (* _Michael Somos_, Mar 04 2014 *)
%t A000009 a[ n_] := SeriesCoefficient[ QHypergeometricPFQ[{}, {}, q, -1] / 2, {q, 0, n}]; (* _Michael Somos_, Mar 04 2014 *)
%t A000009 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 *)
%t A000009 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 *)
%o A000009 (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 */
%o A000009 (PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^2 + A) / eta(x + A), n))};
%o A000009 (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 */
%o A000009 (PARI) lista(nn) = {q='q+O('q^nn); Vec(eta(q^2)/eta(q))} \\ _Altug Alkan_, Mar 20 2018
%o A000009 (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
%o A000009 (Haskell)
%o A000009 import Data.MemoCombinators (memo2, integral)
%o A000009 a000009 n = a000009_list !! n
%o A000009 a000009_list = map (pM 1) [0..] where
%o A000009 pM = memo2 integral integral p
%o A000009 p _ 0 = 1
%o A000009 p k m | m < k = 0
%o A000009 | otherwise = pM (k + 1) (m - k) + pM (k + 1) m
%o A000009 -- _Reinhard Zumkeller_, Sep 09 2015, Nov 05 2013
%o A000009 (Maxima) num_distinct_partitions(60,list); /* _Emanuele Munarini_, Feb 24 2014 */
%o A000009 (Maxima)
%o A000009 h(n):=if oddp(n)=true then 1 else 0;
%o A000009 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);
%o A000009 makelist(S(n,1),n,0,27); /* _Vladimir Kruchinin_, Sep 07 2014 */
%o A000009 (SageMath) # uses[EulerTransform from A166861]
%o A000009 a = BinaryRecurrenceSequence(0, 1)
%o A000009 b = EulerTransform(a)
%o A000009 print([b(n) for n in range(56)]) # _Peter Luschny_, Nov 11 2020
%o A000009 (Python) # uses A010815
%o A000009 from functools import lru_cache
%o A000009 from math import isqrt
%o A000009 @lru_cache(maxsize=None)
%o A000009 def A000009(n): return 1 if n == 0 else A010815(n)+2*sum((-1)**(k+1)*A000009(n-k**2) for k in range(1,isqrt(n)+1)) # _Chai Wah Wu_, Sep 08 2021
%o A000009 (Python)
%o A000009 import numpy as np
%o A000009 n = 1000
%o A000009 arr = np.zeros(n,dtype=object)
%o A000009 arr[0] = 1
%o A000009 for i in range(1,n):
%o A000009 arr[i:] += arr[:n-i]
%o A000009 print(arr) # _Yigit Oktar_, Jul 12 2025
%o A000009 (Julia) # uses A010815
%o A000009 using Memoize
%o A000009 @memoize function A000009(n)
%o A000009 n == 0 && return 1
%o A000009 s = sum((-1)^k*A000009(n - k^2) for k in 1:isqrt(n))
%o A000009 A010815(n) - 2*s
%o A000009 end # _Peter Luschny_, Sep 09 2021
%Y A000009 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.
%Y A000009 a(n) = Sum_{n=1..m} A097306(n, m), row sums of triangle of number of partitions of n into m odd parts.
%Y A000009 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).
%Y A000009 Cf. A167377 (complement).
%Y A000009 Cf. A067659 (odd number of parts), A067661 (even number of parts).
%Y A000009 Number of r-regular partitions for r = 2 through 12: A000009, A000726, A001935, A035959, A219601, A035985, A261775, A104502, A261776, A328545, A328546.
%K A000009 nonn,core,easy,nice
%O A000009 0,4
%A A000009 _N. J. A. Sloane_