0,4

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.

Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).

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

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

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

Equals left border of triangle A091602 starting with offset 1. - Gary W. Adamson, Mar 13 2010

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 A000041. - Richard Locke Peterson, Aug 16 2018

Ewell (1973) gives a number of recurrences. - N. J. A. Sloane, Jan 14 2020

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

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).

Reinhard Zumkeller, Table of n, a(n) for n = 0..5000 (first 2000 terms from N. J. A. Sloane)

Joerg Arndt, Matters Computational (The Fxtbook), pp.348-350

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.

Francesca Aicardi, Matricial formulae for partitions, Functional Analysis and Other Mathematics, Vol. 3, No. 2 (2011), pp. 127-133; arXiv preprint, arXiv:0806.1273 [math.NT], 2008.

George E. Andrews, Euler's "De Partitio Numerorum", Bull. Amer. Math. Soc., 44 (No. 4, 2007), 561-573.

George E. Andrews, The Bhargava-Adiga Summation and Partitions, 2016. See page 4 equation (2.2)

Andreas B. G. Blobel, An Asymptotic Form of the Generating Function Prod_{k=1,oo} (1+x^k/k), arXiv:1904.07808 [math.CO], 2019.

Alexander Bors, Michael Giudici and Cheryl E. Praeger, Documentation for the GAP code file OrbOrd.txt, arXiv:1910.12570 [math.GR], 2019.

Henry Bottomley, Illustration for A000009, A000041, A047967

Andrés Eduardo Caicedo and Brittany Shelton, Of puzzles and partitions: Introducing Partiti, Mathematics Magazine, Vol. 91, No. 1 (2018), pp. 20-23; arXiv preprint, arXiv:1710.04495 [math.HO], 2017.

Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002.

Huantian Cao, AutoGF: An Automated System to Calculate Coefficients of Generating Functions, thesis, 2002 [Local copy, with permission]

H. B. C. Darling, Collected Papers of Ramanujan, Table for q(n); n=1 through 100

Alejandro Erickson and Mark Schurch, Monomer-dimer tatami tilings of square regions, Journal of Discrete Algorithms, Vol. 16 (2012), pp. 258-269; arXiv preprint, arXiv:1110.5103 [math.CO], 2011.

John A. Ewell, Partition recurrences, J. Comb. Theory A, Vol. 14, 125-127, 1973.

Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009; see page 48 and 499

Evangelos Georgiadis, Computing Partition Numbers q(n), Technical Report, February (2009).

Benjamin Hackl, 5 + 5 + 1 + 1 + 1 = 10 + 2 + 1, and why there is more to it than you think., YouTube video, 2022.

Cristiano Husu, The butterfly sequence: the second difference sequence of the numbers of integer partitions with distinct parts, Journal of Number Theory, Vol. 193 (2018), pp. 171-188; arXiv preprint, arXiv:1804.09883 [math.NT], 2018.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 108

Martin Klazar, What is an answer? - remarks, results and problems on PIO formulas in combinatorial enumeration, part I, arXiv:1808.08449 [math.CO], 2018.

Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], 2015-2016.

Vaclav Kotesovec, Getting wrong limit with Bessel, Mathematica Stack Exchange, Nov 09 2016.

Alain Lascoux, Sylvester's bijection between strict and odd partitions, Discrete Math., Vol. 277, No. 1-3 (2004), pp. 275-278.

Jeremy Lovejoy, The number of partitions into distinct parts modulo powers of 5, Bulletin of the London Mathematical Society, Vol. 35, No. 1 (2003), pp. 41-46; alternative link.

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.

Günter Meinardus, Über Partitionen mit Differenzenbedingungen, Mathematische Zeitschrift (1954/55), Volume 61, page 289-302

Mircea Merca, Combinatorial interpretations of a recent convolution for the number of divisors of a positive integer, Journal of Number Theory, Volume 160, March 2016, Pages 60-75, function q(n).

Mircea Merca, The Lambert series factorization theorem, The Ramanujan Journal, Vol. 44, No. 2 (2017), pp. 417-435; alternative link.

Donald J. Newman, A Problem Seminar, pp. 18;93;102-3 Prob. 93 Springer-Verlag NY 1982.

Hieu D. Nguyen and Douglas Taggart, Mining the OEIS: Ten Experimental Conjectures, 2013. Mentions this sequence.

Kimeu Arphaxad Ngwava, Nick Gill and Ian Short, Nilpotent covers of symmetric groups, arXiv:2005.13869 [math.GR], 2020.

Matthew Parker, The first 100K terms (7-Zip compressed file).

Marko Riedel, Proof of recurrence by V. Jovovic.

Ed Sandifer, How Euler Did It, Philip Naude's problem.

Michael Somos, Introduction to Ramanujan theta functions.

Eric Weisstein's World of Mathematics, Partition Function P, Partition Function Q, Partition Function bk, Euler Identity, Ramanujan Theta Functions, q-Pochhammer Symbol.

Wikipedia, Glaisher's Theorem.

Wolfram Research, Generating functions for q(n).

Mingjia Yang and Doron Zeilberger, Systematic Counting of Restricted Partitions, arXiv:1910.08989 [math.CO], 2019.

Michael P. Zaletel and Roger S. K. Mong, Exact matrix product states for quantum Hall wave functions, Physical Review B, Vol. 86, No. 24 (2012), 245305; arXiv preprint, arXiv:1208.4862 [cond-mat.str-el], 2012. - From N. J. A. Sloane, Dec 25 2012

Index entries for "core" sequences

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.

a(n) = Sum_{k=0..n-1} A117195(n,k) = A117192(n) + A117193(n) for n>0. - Reinhard Zumkeller, Mar 03 2006

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

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)

From Gary W. Adamson, Jun 13 2009: (Start)

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(A004526(n)) = A172033(n). - Reinhard Zumkeller, Jan 23 2010

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

a(n) = A054242(n,0) = A201377(n,0). - Reinhard Zumkeller, Dec 02 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) = A067661(n) + A067659(n). Wolfdieter Lang, Jan 18 2016

From Vaclav Kotesovec, May 29 2016: (Start)

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) = 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

a(n) ~ Pi*BesselI(1, Pi*sqrt((n+1/24)/3)) / sqrt(24*n+1). - Vaclav Kotesovec, Nov 08 2016

a(n) = A000041(n)-A047967(n). - R. J. Mathar, Nov 20 2017

Sum_{n>=1} 1/a(n) = A237515. - Amiram Eldar, Nov 15 2020

From Peter Bala, Jan 15 2021: (Start)

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)

From Peter Bala, Feb 02 2021: (Start)

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 McLaughlin et al., Section 1.3, Entry 7.)

Similarly, A(x) = Sum_{n >= 0} x^(n*(2*n+1))/Product_{k = 1..2*n+1} (1 - x^k). (End)

a(n) = A001227(n) + A238005(n) + A238006(n). - R. J. Mathar, Sep 08 2021

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

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

...

From Reinhard Zumkeller, Jun 13 2009: (Start)

a(8)=6, A140207(8)=#{5+2+1,4+3+1}=2, A003056(8)=3, A051162(8)=5;

a(9)=8, A140207(9)=#{6+2+1,5+3+1,4+3+2}=3, A003056(9)=3, A051162(9)=6;

a(10)=10, A140207(10)=#{4+3+2+1}=1, A003056(10)=4, A051162(10)=4. (End)

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

A000009 := proc(n)

    local x, m;

    product(1+x^m, m=1..n+1) ;

    expand(%) ;

    coeff(%, x, n) ;

end proc: # R. J. Mathar, Jun 18 2016

# Alternatively:

simplify(expand(QDifferenceEquations:-QPochhammer(-1, x, 99)/2, x)):

seq(coeff(%, x, n), n=0..55); # Peter Luschny, Nov 17 2016

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 *)

(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

-- Reinhard Zumkeller, Sep 09 2015, Nov 05 2013

(Maxima) num_distinct_partitions(60, list); /* Emanuele Munarini, Feb 24 2014 */

(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);

makelist(S(n, 1), n, 0, 27); /* Vladimir Kruchinin, Sep 07 2014 */

(SageMath) # uses[EulerTransform from A166861]

a = BinaryRecurrenceSequence(0, 1)

b = EulerTransform(a)

print([b(n) for n in range(56)]) # Peter Luschny, Nov 11 2020

(Python) # uses A010815

from functools import lru_cache

from math import isqrt

@lru_cache(maxsize=None)

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

(Julia) # uses A010815

using Memoize

@memoize function A000009(n)

    n == 0 && return 1

    s = sum((-1)^k*A000009(n - k^2) for k in 1:isqrt(n))

    A010815(n) - 2*s

end # Peter Luschny, Sep 09 2021

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).

Cf. A167377 (complement).

Cf. A067659 (odd number of parts), A067661 (even number of parts).

Number of r-regular partitions for r = 2 through 12: A000009, A000726, A001935, A035959, A219601, A035985, A261775, A104502, A261776, A328545, A328546.

Sequence in context: A034320 A058703 A347588 * A081360 A117409 A092833

Adjacent sequences:  A000006 A000007 A000008 * A000010 A000011 A000012

nonn,core,easy,nice

N. J. A. Sloane

approved