cp's OEIS Frontend

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.

Showing 1-10 of 45 results. Next

A000045 Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1.

Original entry on oeis.org

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155
Offset: 0

Views

Author

N. J. A. Sloane, 1964

Keywords

Comments

D. E. Knuth writes: "Before Fibonacci wrote his work, the sequence F_{n} had already been discussed by Indian scholars, who had long been interested in rhythmic patterns that are formed from one-beat and two-beat notes. The number of such rhythms having n beats altogether is F_{n+1}; therefore both Gopāla (before 1135) and Hemachandra (c. 1150) mentioned the numbers 1, 2, 3, 5, 8, 13, 21, ... explicitly." (TAOCP Vol. 1, 2nd ed.) - Peter Luschny, Jan 11 2015
In keeping with historical accounts (see the references by P. Singh and S. Kak), the generalized Fibonacci sequence a, b, a + b, a + 2b, 2a + 3b, 3a + 5b, ... can also be described as the Gopala-Hemachandra numbers H(n) = H(n-1) + H(n-2), with F(n) = H(n) for a = b = 1, and Lucas sequence L(n) = H(n) for a = 2, b = 1. - Lekraj Beedassy, Jan 11 2015
Susantha Goonatilake writes: "[T]his sequence was well known in South Asia and used in the metrical sciences. Its development is attributed in part to Pingala (200 BC), later being associated with Virahanka (circa 700 AD), Gopala (circa 1135), and Hemachandra (circa 1150)—all of whom lived and worked prior to Fibonacci." (Toward a Global Science: Mining Civilizational Knowledge, p. 126) - Russ Cox, Sep 08 2021
Also sometimes called Hemachandra numbers.
Also sometimes called Lamé's sequence.
For a photograph of "Fibonacci"'s 1202 book, see the Leonardo of Pisa link below.
F(n+2) = number of binary sequences of length n that have no consecutive 0's.
F(n+2) = number of subsets of {1,2,...,n} that contain no consecutive integers.
F(n+1) = number of tilings of a 2 X n rectangle by 2 X 1 dominoes.
F(n+1) = number of matchings (i.e., Hosoya index) in a path graph on n vertices: F(5)=5 because the matchings of the path graph on the vertices A, B, C, D are the empty set, {AB}, {BC}, {CD} and {AB, CD}. - Emeric Deutsch, Jun 18 2001
F(n) = number of compositions of n+1 with no part equal to 1. [Cayley, Grimaldi]
Positive terms are the solutions to z = 2*x*y^4 + (x^2)*y^3 - 2*(x^3)*y^2 - y^5 - (x^4)*y + 2*y for x,y >= 0 (Ribenboim, page 193). When x=F(n), y=F(n + 1) and z > 0 then z=F(n + 1).
For Fibonacci search see Knuth, Vol. 3; Horowitz and Sahni; etc.
F(n) is the diagonal sum of the entries in Pascal's triangle at 45 degrees slope. - Amarnath Murthy, Dec 29 2001 (i.e., row sums of A030528, R. J. Mathar, Oct 28 2021)
F(n+1) is the number of perfect matchings in ladder graph L_n = P_2 X P_n. - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002
F(n+1) = number of (3412,132)-, (3412,213)- and (3412,321)-avoiding involutions in S_n.
This is also the Horadam sequence (0,1,1,1). - Ross La Haye, Aug 18 2003
An INVERT transform of A019590. INVERT([1,1,2,3,5,8,...]) gives A000129. INVERT([1,2,3,5,8,13,21,...]) gives A028859. - Antti Karttunen, Dec 12 2003
Number of meaningful differential operations of the k-th order on the space R^3. - Branko Malesevic, Mar 02 2004
F(n) = number of compositions of n-1 with no part greater than 2. Example: F(4) = 3 because we have 3 = 1+1+1 = 1+2 = 2+1.
F(n) = number of compositions of n into odd parts; e.g., F(6) counts 1+1+1+1+1+1, 1+1+1+3, 1+1+3+1, 1+3+1+1, 1+5, 3+1+1+1, 3+3, 5+1. - Clark Kimberling, Jun 22 2004
F(n) = number of binary words of length n beginning with 0 and having all runlengths odd; e.g., F(6) counts 010101, 010111, 010001, 011101, 011111, 000101, 000111, 000001. - Clark Kimberling, Jun 22 2004
The number of sequences (s(0),s(1),...,s(n)) such that 0 < s(i) < 5, |s(i)-s(i-1)|=1 and s(0)=1 is F(n+1); e.g., F(5+1) = 8 corresponds to 121212, 121232, 121234, 123212, 123232, 123234, 123432, 123434. - Clark Kimberling, Jun 22 2004 [corrected by Neven Juric, Jan 09 2009]
Likewise F(6+1) = 13 corresponds to these thirteen sequences with seven numbers: 1212121, 1212123, 1212321, 1212323, 1212343, 1232121, 1232123, 1232321, 1232323, 1232343, 1234321, 1234323, 1234343. - Neven Juric, Jan 09 2008
A relationship between F(n) and the Mandelbrot set is discussed in the link "Le nombre d'or dans l'ensemble de Mandelbrot" (in French). - Gerald McGarvey, Sep 19 2004
For n > 0, the continued fraction for F(2n-1)*phi = [F(2n); L(2n-1), L(2n-1), L(2n-1), ...] and the continued fraction for F(2n)*phi = [F(2n+1)-1; 1, L(2n)-2, 1, L(2n)-2, ...]. Also true: F(2n)*phi = [F(2n+1); -L(2n), L(2n), -L(2n), L(2n), ...] where L(i) is the i-th Lucas number (A000204). - Clark Kimberling, Nov 28 2004 [corrected by Hieronymus Fischer, Oct 20 2010]
For any nonzero number k, the continued fraction [4,4,...,4,k], which is n 4's and a single k, equals (F(3n) + k*F(3n+3))/(F(3n-3) + k*F(3n)). - Greg Dresden, Aug 07 2019
F(n+1) (for n >= 1) = number of permutations p of 1,2,3,...,n such that |k-p(k)| <= 1 for k=1,2,...,n. (For <= 2 and <= 3, see A002524 and A002526.) - Clark Kimberling, Nov 28 2004
The ratios F(n+1)/F(n) for n > 0 are the convergents to the simple continued fraction expansion of the golden section. - Jonathan Sondow, Dec 19 2004
Lengths of successive words (starting with a) under the substitution: {a -> ab, b -> a}. - Jeroen F.J. Laros, Jan 22 2005
The Fibonacci sequence, like any additive sequence, naturally tends to be geometric with common ratio not a rational power of 10; consequently, for a sufficiently large number of terms, Benford's law of first significant digit (i.e., first digit 1 <= d <= 9 occurring with probability log_10(d+1) - log_10(d)) holds. - Lekraj Beedassy, Apr 29 2005 (See Brown-Duncan, 1970. - N. J. A. Sloane, Feb 12 2017)
F(n+2) = Sum_{k=0..n} binomial(floor((n+k)/2),k), row sums of A046854. - Paul Barry, Mar 11 2003
Number of order ideals of the "zig-zag" poset. See vol. 1, ch. 3, prob. 23 of Stanley. - Mitch Harris, Dec 27 2005
F(n+1)/F(n) is also the Farey fraction sequence (see A097545 for explanation) for the golden ratio, which is the only number whose Farey fractions and continued fractions are the same. - Joshua Zucker, May 08 2006
a(n+2) is the number of paths through 2 plates of glass with n reflections (reflections occurring at plate/plate or plate/air interfaces). Cf. A006356-A006359. - Mitch Harris, Jul 06 2006
F(n+1) equals the number of downsets (i.e., decreasing subsets) of an n-element fence, i.e., an ordered set of height 1 on {1,2,...,n} with 1 > 2 < 3 > 4 < ... n and no other comparabilities. Alternatively, F(n+1) equals the number of subsets A of {1,2,...,n} with the property that, if an odd k is in A, then the adjacent elements of {1,2,...,n} belong to A, i.e., both k - 1 and k + 1 are in A (provided they are in {1,2,...,n}). - Brian Davey, Aug 25 2006
Number of Kekulé structures in polyphenanthrenes. See the paper by Lukovits and Janezic for details. - Parthasarathy Nambi, Aug 22 2006
Inverse: With phi = (sqrt(5) + 1)/2, round(log_phi(sqrt((sqrt(5) a(n) + sqrt(5 a(n)^2 - 4))(sqrt(5) a(n) + sqrt(5 a(n)^2 + 4)))/2)) = n for n >= 3, obtained by rounding the arithmetic mean of the inverses given in A001519 and A001906. - David W. Cantrell (DWCantrell(AT)sigmaxi.net), Feb 19 2007
A result of Jacobi from 1848 states that every symmetric matrix over a p.i.d. is congruent to a triple-diagonal matrix. Consider the maximal number T(n) of summands in the determinant of an n X n triple-diagonal matrix. This is the same as the number of summands in such a determinant in which the main-, sub- and superdiagonal elements are all nonzero. By expanding on the first row we see that the sequence of T(n)'s is the Fibonacci sequence without the initial stammer on the 1's. - Larry Gerstein (gerstein(AT)math.ucsb.edu), Mar 30 2007
Suppose psi=log(phi). We get the representation F(n)=(2/sqrt(5))*sinh(n*psi) if n is even; F(n)=(2/sqrt(5))*cosh(n*psi) if n is odd. There is a similar representation for Lucas numbers (A000032). Many Fibonacci formulas now easily follow from appropriate sinh and cosh formulas. For example: the de Moivre theorem (cosh(x)+sinh(x))^m = cosh(mx)+sinh(mx) produces L(n)^2 + 5F(n)^2 = 2L(2n) and L(n)F(n) = F(2n) (setting x=n*psi and m=2). - Hieronymus Fischer, Apr 18 2007
Inverse: floor(log_phi(sqrt(5)*F(n)) + 1/2) = n, for n > 1. Also for n > 0, floor((1/2)*log_phi(5*F(n)*F(n+1))) = n. Extension valid for integer n, except n=0,-1: floor((1/2)*sign(F(n)*F(n+1))*log_phi|5*F(n)*F(n+1)|) = n (where sign(x) = sign of x). - Hieronymus Fischer, May 02 2007
F(n+2) = the number of Khalimsky-continuous functions with a two-point codomain. - Shiva Samieinia (shiva(AT)math.su.se), Oct 04 2007
This is a_1(n) in the Doroslovacki reference.
Let phi = A001622 then phi^n = (1/phi)*a(n) + a(n+1). - Gary W. Adamson, Dec 15 2007
The sequence of first differences, F(n+1)-F(n), is essentially the same sequence: 1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... - Colm Mulcahy, Mar 03 2008
Equals row sums of triangle A144152. - Gary W. Adamson, Sep 12 2008
Except for the initial term, the numerator of the convergents to the recursion x = 1/(x+1). - Cino Hilliard, Sep 15 2008
F(n) is the number of possible binary sequences of length n that obey the sequential construction rule: if last symbol is 0, add the complement (1); else add 0 or 1. Here 0,1 are metasymbols for any 2-valued symbol set. This rule has obvious similarities to JFJ Laros's rule, but is based on addition rather than substitution and creates a tree rather than a single sequence. - Ross Drewe, Oct 05 2008
F(n) = Product_{k=1..(n-1)/2} (1 + 4*cos^2 k*Pi/n), where terms = roots to the Fibonacci product polynomials, A152063. - Gary W. Adamson, Nov 22 2008
Fp == 5^((p-1)/2) mod p, p = prime [Schroeder, p. 90]. - Gary W. Adamson & Alexander R. Povolotsky, Feb 21 2009
A000032(n)^2 - 5*F(n)^2 = 4*(-1)^n. - Gary W. Adamson, Mar 11 2009
Output of Kasteleyn's formula for the number of perfect matchings of an m X n grid specializes to the Fibonacci sequence for m=2. - Sarah-Marie Belcastro, Jul 04 2009
(F(n),F(n+4)) satisfies the Diophantine equation: X^2 + Y^2 - 7XY = 9*(-1)^n. - Mohamed Bouhamida, Sep 06 2009
(F(n),F(n+2)) satisfies the Diophantine equation: X^2 + Y^2 - 3XY = (-1)^n. - Mohamed Bouhamida, Sep 08 2009
a(n+2) = A083662(A131577(n)). - Reinhard Zumkeller, Sep 26 2009
Difference between number of closed walks of length n+1 from a node on a pentagon and number of walks of length n+1 between two adjacent nodes on a pentagon. - Henry Bottomley, Feb 10 2010
F(n+1) = number of Motzkin paths of length n having exactly one weak ascent. A Motzkin path of length n is a lattice path from (0,0) to (n,0) consisting of U=(1,1), D=(1,-1) and H=(1,0) steps and never going below the x-axis. A weak ascent in a Motzkin path is a maximal sequence of consecutive U and H steps. Example: a(5)=5 because we have (HHHH), (HHU)D, (HUH)D, (UHH)D, and (UU)DD (the unique weak ascent is shown between parentheses; see A114690). - Emeric Deutsch, Mar 11 2010
(F(n-1) + F(n+1))^2 - 5*F(n-2)*F(n+2) = 9*(-1)^n. - Mohamed Bouhamida, Mar 31 2010
From the Pinter and Ziegler reference's abstract: authors "show that essentially the Fibonacci sequence is the unique binary recurrence which contains infinitely many three-term arithmetic progressions. A criterion for general linear recurrences having infinitely many three-term arithmetic progressions is also given." - Jonathan Vos Post, May 22 2010
F(n+1) = number of paths of length n starting at initial node on the path graph P_4. - Johannes W. Meijer, May 27 2010
F(k) = number of cyclotomic polynomials in denominator of generating function for number of ways to place k nonattacking queens on an n X n board. - Vaclav Kotesovec, Jun 07 2010
As n->oo, (a(n)/a(n-1) - a(n-1)/a(n)) tends to 1.0. Example: a(12)/a(11) - a(11)/a(12) = 144/89 - 89/144 = 0.99992197.... - Gary W. Adamson, Jul 16 2010
From Hieronymus Fischer, Oct 20 2010: (Start)
Fibonacci numbers are those numbers m such that m*phi is closer to an integer than k*phi for all k, 1 <= k < m. More formally: a(0)=0, a(1)=1, a(2)=1, a(n+1) = minimal m > a(n) such that m*phi is closer to an integer than a(n)*phi.
For all numbers 1 <= k < F(n), the inequality |k*phi-round(k*phi)| > |F(n)*phi-round(F(n)*phi)| holds.
F(n)*phi - round(F(n)*phi) = -((-phi)^(-n)), for n > 1.
Fract(1/2 + F(n)*phi) = 1/2 -(-phi)^(-n), for n > 1.
Fract(F(n)*phi) = (1/2)*(1 + (-1)^n) - (-phi)^(-n), n > 1.
Inverse: n = -log_phi |1/2 - fract(1/2 + F(n)*phi)|.
(End)
F(A001177(n)*k) mod n = 0, for any integer k. - Gary Detlefs, Nov 27 2010
F(n+k)^2 - F(n)^2 = F(k)*F(2n+k), for even k. - Gary Detlefs, Dec 04 2010
F(n+k)^2 + F(n)^2 = F(k)*F(2n+k), for odd k. - Gary Detlefs, Dec 04 2010
F(n) = round(phi*F(n-1)) for n > 1. - Joseph P. Shoulak, Jan 13 2012
For n > 0: a(n) = length of n-th row in Wythoff array A003603. - Reinhard Zumkeller, Jan 26 2012
From Bridget Tenner, Feb 22 2012: (Start)
The number of free permutations of [n].
The number of permutations of [n] for which s_k in supp(w) implies s_{k+-1} not in supp(w).
The number of permutations of [n] in which every decomposition into length(w) reflections is actually composed of simple reflections. (End)
The sequence F(n+1)^(1/n) is increasing. The sequence F(n+2)^(1/n) is decreasing. - Thomas Ordowski, Apr 19 2012
Two conjectures: For n > 1, F(n+2)^2 mod F(n+1)^2 = F(n)*F(n+1) - (-1)^n. For n > 0, (F(2n) + F(2n+2))^2 = F(4n+3) + Sum_{k = 2..2n} F(2k). - Alex Ratushnyak, May 06 2012
From Ravi Kumar Davala, Jan 30 2014: (Start)
Proof of Ratushnyak's first conjecture: For n > 1, F(n+2)^2 - F(n)*F(n+1) + (-1)^n = 2*F(n+1)^2.
Consider: F(n+2)^2 - F(n)*F(n+1) - 2*F(n+1)^2
= F(n+2)^2 - F(n+1)^2 - F(n+1)^2 - F(n)*F(n+1)
= (F(n+2) + F(n+1))*(F(n+2) - F(n+1)) - F(n+1)*(F(n+1) + F(n))
= F(n+3)*F(n) - F(n+1)*F(n+2) = -(-1)^n.
Proof of second conjecture: L(n) stands for Lucas number sequence from A000032.
Consider the fact that
L(2n+1)^2 = L(4n+2) - 2
(F(2n) + F(2n+2))^2 = F(4n+1) + F(4n+3) - 2
(F(2n) + F(2n+2))^2 = (Sum_{k = 2..2n} F(2k)) + F(4n+3).
(End)
The relationship: INVERT transform of (1,1,0,0,0,...) = (1, 2, 3, 5, 8, ...), while the INVERT transform of (1,0,1,0,1,0,1,...) = (1, 1, 2, 3, 5, 8, ...) is equivalent to: The numbers of compositions using parts 1 and 2 is equivalent to the numbers of compositions using parts == 1 (mod 2) (i.e., the odd integers). Generally, the numbers of compositions using parts 1 and k is equivalent to the numbers of compositions of (n+1) using parts 1 mod k. Cf. A000930 for k = 3 and A003269 for k = 4. Example: for k = 2, n = 4 we have the compositions (22; 211, 121; 112; 1111) = 5; but using parts 1 and 3 we have for n = 5: (311, 131, 113, 11111, 5) = 5. - Gary W. Adamson, Jul 05 2012
The sequence F(n) is the binomial transformation of the alternating sequence (-1)^(n-1)*F(n), whereas the sequence F(n+1) is the binomial transformation of the alternating sequence (-1)^n*F(n-1). Both of these facts follow easily from the equalities a(n;1)=F(n+1) and b(n;1)=F(n) where a(n;d) and b(n;d) are so-called "delta-Fibonacci" numbers as defined in comments to A014445 (see also the papers of Witula et al.). - Roman Witula, Jul 24 2012
F(n) is the number of different (n-1)-digit binary numbers such that all substrings of length > 1 have at least one digit equal to 1. Example: for n = 5 there are 8 binary numbers with n - 1 = 4 digits (1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111), only the F(n) = 5 numbers 1010, 1011, 1101, 1110 and 1111 have the desired property. - Hieronymus Fischer, Nov 30 2012
For positive n, F(n+1) equals the determinant of the n X n tridiagonal matrix with 1's along the main diagonal, i's along the superdiagonal and along the subdiagonal where i = sqrt(-1). Example: Det([1,i,0,0; i,1,i,0; 0,i,1,i; 0,0,i,1]) = F(4+1) = 5. - Philippe Deléham, Feb 24 2013
For n >= 1, number of compositions of n where there is a drop between every second pair of parts, starting with the first and second part; see example. Also, a(n+1) is the number of compositions where there is a drop between every second pair of parts, starting with the second and third part; see example. - Joerg Arndt, May 21 2013 [see the Hopkins/Tangboonduangjit reference for a proof, see also the Checa reference for alternative proofs and statistics]
Central terms of triangles in A162741 and A208245, n > 0. - Reinhard Zumkeller, Jul 28 2013
For n >= 4, F(n-1) is the number of simple permutations in the geometric grid class given in A226433. - Jay Pantone, Sep 08 2013
a(n) are the pentagon (not pentagonal) numbers because the algebraic degree 2 number rho(5) = 2*cos(Pi/5) = phi (golden section), the length ratio diagonal/side in a pentagon, has minimal polynomial C(5,x) = x^2 - x - 1 (see A187360, n=5), hence rho(5)^n = a(n-1)*1 + a(n)*rho(5), n >= 0, in the power basis of the algebraic number field Q(rho(5)). One needs a(-1) = 1 here. See also the P. Steinbach reference under A049310. - Wolfdieter Lang, Oct 01 2013
A010056(a(n)) = 1. - Reinhard Zumkeller, Oct 10 2013
Define F(-n) to be F(n) for n odd and -F(n) for n even. Then for all n and k, F(n+2k)^2 - F(n)^2 = F(n+k)*( F(n+3k) - F(n-k) ). - Charlie Marion, Dec 20 2013
( F(n), F(n+2k) ) satisfies the Diophantine equation: X^2 + Y^2 - L(2k)*X*Y = F(4k)^2*(-1)^n. This generalizes Bouhamida's comments dated Sep 06 2009 and Sep 08 2009. - Charlie Marion, Jan 07 2014
For any prime p there is an infinite periodic subsequence within F(n) divisible by p, that begins at index n = 0 with value 0, and its first nonzero term at n = A001602(i), and period k = A001602(i). Also see A236479. - Richard R. Forberg, Jan 26 2014
Range of row n of the circular Pascal array of order 5. - Shaun V. Ault, May 30 2014 [orig. Kicey-Klimko 2011, and observations by Glen Whitehead; more general work found in Ault-Kicey 2014]
Nonnegative range of the quintic polynomial 2*y - y^5 + 2*x*y^4 + x^2*y^3 - 2*x^3*y^2 - x^4*y with x, y >= 0, see Jones 1975. - Charles R Greathouse IV, Jun 01 2014
The expression round(1/(F(k+1)/F(n) + F(k)/F(n+1))), for n > 0, yields a Fibonacci sequence with k-1 leading zeros (with rounding 0.5 to 0). - Richard R. Forberg, Aug 04 2014
Conjecture: For n > 0, F(n) is the number of all admissible residue classes for which specific finite subsequences of the Collatz 3n + 1 function consists of n+2 terms. This has been verified for 0 < n < 51. For details see Links. - Mike Winkler, Oct 03 2014
a(4)=3 and a(6)=8 are the only Fibonacci numbers that are of the form prime+1. - Emmanuel Vantieghem, Oct 02 2014
a(1)=1=a(2), a(3)=2 are the only Fibonacci numbers that are of the form prime-1. - Emmanuel Vantieghem, Jun 07 2015
Any consecutive pair (m, k) of the Fibonacci sequence a(n) illustrates a fair equivalence between m miles and k kilometers. For instance, 8 miles ~ 13 km; 13 miles ~ 21 km. - Lekraj Beedassy, Oct 06 2014
a(n+1) counts closed walks on K_2, containing one loop on the other vertex. Equivalently the (1,1)entry of A^(n+1) where the adjacency matrix of digraph is A=(0,1; 1,1). - _David Neil McGrath, Oct 29 2014
a(n-1) counts closed walks on the graph G(1-vertex;l-loop,2-loop). - David Neil McGrath, Nov 26 2014
From Tom Copeland, Nov 02 2014: (Start)
Let P(x) = x/(1+x) with comp. inverse Pinv(x) = x/(1-x) = -P[-x], and C(x) = [1-sqrt(1-4x)]/2, an o.g.f. for the shifted Catalan numbers A000108, with inverse Cinv(x) = x * (1-x).
Fin(x) = P[C(x)] = C(x)/[1 + C(x)] is an o.g.f. for the Fine numbers, A000957 with inverse Fin^(-1)(x) = Cinv[Pinv(x)] = Cinv[-P(-x)].
Mot(x) = C[P(x)] = C[-Pinv(-x)] gives an o.g.f. for shifted A005043, the Motzkin or Riordan numbers with comp. inverse Mot^(-1)(x) = Pinv[Cinv(x)] = (x - x^2) / (1 - x + x^2) (cf. A057078).
BTC(x) = C[Pinv(x)] gives A007317, a binomial transform of the Catalan numbers, with BTC^(-1)(x) = P[Cinv(x)].
Fib(x) = -Fin[Cinv(Cinv(-x))] = -P[Cinv(-x)] = x + 2 x^2 + 3 x^3 + 5 x^4 + ... = (x+x^2)/[1-x-x^2] is an o.g.f. for the shifted Fibonacci sequence A000045, so the comp. inverse is Fib^(-1)(x) = -C[Pinv(-x)] = -BTC(-x) and Fib(x) = -BTC^(-1)(-x).
Generalizing to P(x,t) = x /(1 + t*x) and Pinv(x,t) = x /(1 - t*x) = -P(-x,t) gives other relations to lattice paths, such as the o.g.f. for A091867, C[P[x,1-t]], and that for A104597, Pinv[Cinv(x),t+1].
(End)
F(n+1) equals the number of binary words of length n avoiding runs of zeros of odd lengths. - Milan Janjic, Jan 28 2015
From Russell Jay Hendel, Apr 12 2015: (Start)
We prove Conjecture 1 of Rashid listed in the Formula section.
We use the following notation: F(n)=A000045(n), the Fibonacci numbers, and L(n) = A000032(n), the Lucas numbers. The fundamental Fibonacci-Lucas recursion asserts that G(n) = G(n-1) + G(n-2), with "L" or "F" replacing "G".
We need the following prerequisites which we label (A), (B), (C), (D). The prerequisites are formulas in the Koshy book listed in the References section. (A) F(m-1) + F(m+1) = L(m) (Koshy, p. 97, #32), (B) L(2m) + 2*(-1)^m = L(m)^2 (Koshy p. 97, #41), (C) F(m+k)*F(m-k) = (-1)^n*F(k)^2 (Koshy, p. 113, #24, Tagiuri's identity), and (D) F(n)^2 + F(n+1)^2 = F(2n+1) (Koshy, p. 97, #30).
We must also prove (E), L(n+2)*F(n-1) = F(2n+1)+2*(-1)^n. To prove (E), first note that by (A), proof of (E) is equivalent to proving that F(n+1)*F(n-1) + F(n+3)*F(n-1) = F(2n+1) + 2*(-1)^n. But by (C) with k=1, we have F(n+1)*F(n-1) = F(n)^2 + (-1)^n. Applying (C) again with k=2 and m=n+1, we have F(n+3)*F(n-1) = F(n+1) + (-1)^n. Adding these two applications of (C) together and using (D) we have F(n+1)*F(n-1) + F(n+3)*F(n-1) = F(n)^2 + F(n+1)^2 + 2*(-1)^n = F(2n+1) + 2(-1)^n, completing the proof of (E).
We now prove Conjecture 1. By (A) and the Fibonacci-Lucas recursion, we have F(2n+1) + F(2n+2) + F(2n+3) + F(2n+4) = (F(2n+1) + F(2n+3)) + (F(2n+2) + F(2n+4)) = L(2n+2) +L(2n+3) = L(2n+4). But then by (B), with m=2n+4, we have sqrt(L(2n+4) + 2(-1)^n) = L(n+2). Finally by (E), we have L(n+2)*F(n-1) = F(2n+1) + 2*(-1)^n. Dividing both sides by F(n-1), we have (F(2n+1) + 2*(-1)^n)/F(n-1) = L(n+2) = sqrt(F(2n+1) + F(2n+2) + F(2n+3) + F(2n+4) + 2(-1)^n), as required.
(End)
In Fibonacci's Liber Abaci the rabbit problem appears in the translation of L. E. Sigler on pp. 404-405, and a remark [27] on p. 637. - Wolfdieter Lang, Apr 17 2015
a(n) counts partially ordered partitions of (n-1) into parts 1,2,3 where only the order of adjacent 1's and 2's are unimportant. (See example.) - David Neil McGrath, Jul 27 2015
F(n) divides F(n*k). Proved by Marjorie Bicknell and Verner E Hoggatt Jr. - Juhani Heino, Aug 24 2015
F(n) is the number of UDU-equivalence classes of ballot paths of length n. Two ballot paths of length n with steps U = (1,1), D = (1,-1) are UDU-equivalent whenever the positions of UDU are the same in both paths. - Kostas Manes, Aug 25 2015
Cassini's identity F(2n+1) * F(2n+3) = F(2n+2)^2 + 1 is the basis for a geometrical paradox (or dissection fallacy) in A262342. - Jonathan Sondow, Oct 23 2015
For n >= 4, F(n) is the number of up-down words on alphabet {1,2,3} of length n-2. - Ran Pan, Nov 23 2015
F(n+2) is the number of terms in p(n), where p(n)/q(n) is the n-th convergent of the formal infinite continued fraction [a(0),a(1),...]; e.g., p(3) = a(0)a(1)a(2)a(3) + a(0)a(1) + a(0)a(3) + a(2)a(3) + 1 has F(5) terms. Also, F(n+1) is the number of terms in q(n). - Clark Kimberling, Dec 23 2015
F(n+1) (for n >= 1) is the permanent of an n X n matrix M with M(i,j)=1 if |i-j| <= 1 and 0 otherwise. - Dmitry Efimov, Jan 08 2016
A trapezoid has three sides of lengths in order F(n), F(n+2), F(n). For increasing n a very close approximation to the maximum area will have the fourth side equal to 2*F(n+1). For a trapezoid with lengths of sides in order F(n+2), F(n), F(n+2), the fourth side will be F(n+3). - J. M. Bergot, Mar 17 2016
(1) Join two triangles with lengths of sides L(n), F(n+3), L(n+2) and F(n+2), L(n+1), L(n+2) (where L(n)=A000032(n)) along the common side of length L(n+2) to create an irregular quadrilateral. Its area is approximately 5*F(2*n-1) - (F(2*n-7) - F(2*n-13))/5. (2) Join two triangles with lengths of sides L(n), F(n+2), F(n+3) and L(n+1), F(n+1), F(n+3) along the common side F(n+3) to form an irregular quadrilateral. Its area is approximately 4*F(2*n-1) - 2*(F(2*n-7) + F(2*n-18)). - J. M. Bergot, Apr 06 2016
From Clark Kimberling, Jun 13 2016: (Start)
Let T* be the infinite tree with root 0 generated by these rules: if p is in T*, then p+1 is in T* and x*p is in T*.
Let g(n) be the set of nodes in the n-th generation, so that g(0) = {0}, g(1) = {1}, g(2) = {2, x}, g(3) = {3, 2x, x+1, x^2}, etc.
Let T(r) be the tree obtained by substituting r for x.
If a positive integer N is not a square and r = sqrt(N), then the number of (not necessarily distinct) integers in g(n) is A000045(n), for n >= 1. See A274142. (End)
Consider the partitions of n, with all summands initially listed in nonincreasing order. Freeze all the 1's in place and then allow all the other summands to change their order, without displacing any of the 1's. The resulting number of arrangements is a(n+1). - Gregory L. Simay, Jun 14 2016
Limit of the matrix power M^k shown in A163733, Sep 14 2016, as k->infinity results in a single column vector equal to the Fibonacci sequence. - Gary W. Adamson, Sep 19 2016
F(n) and Lucas numbers L(n), being related by the formulas F(n) = (F(n-1) + L(n-1))/2 and L(n) = 2 F(n+1) - F(n), are a typical pair of "autosequences" (see the link to OEIS Wiki). - Jean-François Alcover, Jun 10 2017
Also the number of independent vertex sets and vertex covers in the (n-2)-path graph. - Eric W. Weisstein, Sep 22 2017
Shifted numbers of {UD, DU, FD, DF}-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are P-equivalent iff the positions of pattern P are identical in these paths. - Sergey Kirgizov, Apr 08 2018
For n > 0, F(n) = the number of Markov equivalence classes with skeleton the path on n nodes. See Theorem 2.1 in the article by A. Radhakrishnan et al. below. - Liam Solus, Aug 23 2018
For n >= 2, also: number of terms in A032858 (every other base-3 digit is strictly smaller than its neighbors) with n-2 digits in base 3. - M. F. Hasler, Oct 05 2018
F(n+1) is the number of fixed points of the Foata transformation on S_n. - Kevin Long, Oct 17 2018
F(n+2) is the dimension of the Hecke algebra of type A_n with independent parameters (0,1,0,1,...) or (1,0,1,0,...). See Corollary 1.5 in the link "Hecke algebras with independent parameters". - Jia Huang, Jan 20 2019
The sequence is the second INVERT transform of (1, -1, 2, -3, 5, -8, 13, ...) and is the first sequence in an infinite set of successive INVERT transforms generated from (1, 0, 1, 0, 1, ...). Refer to the array shown in A073133. - Gary W. Adamson, Jul 16 2019
From Kai Wang, Dec 16 2019: (Start)
F(n*k)/F(k) = Sum_{i=0..n-1; j=0..n-1; i+2*j=n-1} (-1)^(j*(k-1))*L(k)^i*((i+j)!/(i!*j!)).
F((2*m+1)*k)/F(k) = Sum_{i=0..m-1} (-1)^(i*k)*L((2*m-2*i)*k) + (-1)^(m*k).
F(2*m*k)/F(k) = Sum_{i=0..m-1} (-1)^(i*k)*L((2*m-2*i-1)*k).
F(m+s)*F(n+r) - F(m+r)*F(n+s) = (-1)^(n+s)*F(m-n)*F(r-s).
F(m+r)*F(n+s) + F(m+s)*F(n+r) = (2*L(m+n+r+s) - (-1)^(n+s)*L(m-n)*L(r-s))/5.
L(m+r)*L(n+s) - 5*F(m+s)*F(n+r) = (-1)^(n+s)*L(m-n)*L(r-s).
L(m+r)*L(n+s) + 5*F(m+s)*F(n+r) = 2*L(m+n+r+s) + (-1)^(n+s)*5*F(m-n)*F(r-s).
L(m+r)*L(n+s) - L(m+s)*L(n+r) = (-1)^(n+s)*5*F(m-n)*F(r-s). (End)
F(n+1) is the number of permutations in S_n whose principal order ideals in the weak order are Boolean lattices. - Bridget Tenner, Jan 16 2020
F(n+1) is the number of permutations w in S_n that form Boolean intervals [s, w] in the weak order for every simple reflection s in the support of w. - Bridget Tenner, Jan 16 2020
F(n+1) is the number of subsets of {1,2,.,.,n} in which all differences between successive elements of subsets are odd. For example, for n = 6, F(7) = 13 and the 13 subsets are {6}, {1,6}, {3,6}, {5,6}, {2,3,6}, {2,5,6}, {4,5,6}, {1,2,3,6}, {1,2,5,6}, {1,4,5,6}, {3,4,5,6}, {2,3,4,5,6}, {1,2,3,4,5,6}. For even differences between elements see Comment in A016116. - Enrique Navarrete, Jul 01 2020
F(n) is the number of subsets of {1,2,...,n} in which the smallest element of the subset equals the size of the subset (this type of subset is sometimes called extraordinary). For example, F(6) = 8 and the subsets are {1}, {2,3}, {2,4}, {2,5}, {3,4,5}, {2,6}, {3,4,6}, {3,5,6}. It is easy to see that these subsets follow the Fibonacci recursion F(n) = F(n-1) + F(n-2) since we get F(n) such subsets by keeping all F(n-1) subsets from the previous stage (in the example, the F(5)=5 subsets that don't include 6), and by adding one to all elements and appending an additional element n to each subset in F(n-2) subsets (in the example, by applying this to the F(4)=3 subsets {1}, {2,3}, {2,4} we obtain {2,6}, {3,4,6}, {3,5,6}). - Enrique Navarrete, Sep 28 2020
Named "série de Fibonacci" by Lucas (1877) after the Italian mathematician Fibonacci (Leonardo Bonacci, c. 1170 - c. 1240/50). In 1876 he named the sequence "série de Lamé" after the French mathematician Gabriel Lamé (1795 - 1870). - Amiram Eldar, Apr 16 2021
F(n) is the number of edge coverings of the path with n edges. - M. Farrokhi D. G., Sep 30 2021
LCM(F(m), F(n)) is a Fibonacci number if and only if either F(m) divides F(n) or F(n) divides F(m). - M. Farrokhi D. G., Sep 30 2021
Every nonunit positive rational number has at most one representation as the quotient of two Fibonacci numbers. - M. Farrokhi D. G., Sep 30 2021
The infinite sum F(n)/10^(n-1) for all natural numbers n is equal to 100/89. More generally, the sum of F(n)/(k^(n-1)) for all natural numbers n is equal to k^2/(k^2-k-1). Jonatan Djurachkovitch, Dec 31 2023
For n >= 1, number of compositions (c(1),c(2),...,c(k)) of n where c(1), c(3), c(5), ... are 1. To obtain such compositions K(n) of length n increase all parts c(2) by one in all of K(n-1) and prepend two parts 1 in all of K(n-2). - Joerg Arndt, Jan 05 2024
Cohn (1964) proved that a(12) = 12^2 is the only square in the sequence greater than a(1) = 1. - M. F. Hasler, Dec 18 2024
Product_{i=n-2..n+2} F(i) = F(n)^5 - F(n). For example, (F(4)F(5)F(6)F(7)F(8))=(3 * 5 * 8 * 13 * 21) = 8^5 - 8. - Jules Beauchamp, Apr 28 2025
F(n) is even iff n is a multiple of 3. - Stefano Spezia, Jul 06 2025

Examples

			For x = 0,1,2,3,4, x=1/(x+1) = 1, 1/2, 2/3, 3/5, 5/8. These fractions have numerators 1,1,2,3,5, which are the 2nd to 6th terms of the sequence. - _Cino Hilliard_, Sep 15 2008
From _Joerg Arndt_, May 21 2013: (Start)
There are a(7)=13 compositions of 7 where there is a drop between every second pair of parts, starting with the first and second part:
01:  [ 2 1 2 1 1 ]
02:  [ 2 1 3 1 ]
03:  [ 2 1 4 ]
04:  [ 3 1 2 1 ]
05:  [ 3 1 3 ]
06:  [ 3 2 2 ]
07:  [ 4 1 2 ]
08:  [ 4 2 1 ]
09:  [ 4 3 ]
10:  [ 5 1 1 ]
11:  [ 5 2 ]
12:  [ 6 1 ]
13:  [ 7 ]
There are abs(a(6+1))=13 compositions of 6 where there is no rise between every second pair of parts, starting with the second and third part:
01:  [ 1 2 1 2 ]
02:  [ 1 3 1 1 ]
03:  [ 1 3 2 ]
04:  [ 1 4 1 ]
05:  [ 1 5 ]
06:  [ 2 2 1 1 ]
07:  [ 2 3 1 ]
08:  [ 2 4 ]
09:  [ 3 2 1 ]
10:  [ 3 3 ]
11:  [ 4 2 ]
12:  [ 5 1 ]
13:  [ 6 ]
(End)
Partially ordered partitions of (n-1) into parts 1,2,3 where only the order of the adjacent 1's and 2's are unimportant. E.g., a(8)=21. These are (331),(313),(133),(322),(232),(223),(3211),(2311),(1321),(2131),(1132),(2113),(31111),(13111),(11311),(11131),(11113),(2221),(22111),(211111),(1111111). - _David Neil McGrath_, Jul 25 2015
Consider the partitions of 7 with summands initially listed in nonincreasing order. Keep the 1's frozen in position (indicated by "[]") and then allow the other summands to otherwise vary their order: 7; 6,[1]; 5,2; 2,5; 4,3; 3,4; 5,[1,1], 4,2,[1]; 2,4,[1]; 3,3,[1]; 3,3,2; 3,2,3; 2,3,3; 4,[1,1,1]; 3,2,[1,1]; 2,3,[1,1]; 2,2,2,[1]; 3,[1,1,1,1]; 2,2,[1,1,1]; 2,[1,1,1,1,1]; [1,1,1,1,1,1,1]. There are 21 = a(7+1) arrangements in all. - _Gregory L. Simay_, Jun 14 2016

References

  • Mohammad K. Azarian, The Generating Function for the Fibonacci Sequence, Missouri Journal of Mathematical Sciences, Vol. 2, No. 2, Spring 1990, pp. 78-79. Zentralblatt MATH, Zbl 1097.11516.
  • 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.
  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 70.
  • R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 84.
  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 4.
  • Marjorie Bicknell and Verner E Hoggatt, Fibonacci's Problem Book, Fibonacci Association, San Jose, Calif., 1974.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, pages 24 (Ex. 18), 489, 541.
  • A. Cayley, Theorems in Trigonometry and on Partitions, Messenger of Mathematics, 5 (1876), pp. 164, 188 = Mathematical Papers Vol. 10, n. 634, p. 16.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 84, 111-124, 202-203.
  • B. A. Davey and H. A. Priestley, Introduction to Lattices and Order (2nd edition), CUP, 2002. (See Exercise 1.15.)
  • B. Davis, 'The law of first digits' in 'Science Today' (subsequently renamed '2001') March 1980 p. 55, Times of India, Mumbai.
  • S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 1.2.
  • R. P. Grimaldi, Compositions without the summand 1, Proceedings Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001). Congr. Numer. 152 (2001), 33-43.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §8.5 The Fibonacci and Related Sequences, pp. 286-288.
  • H. Halberstam and K. F. Roth, Sequences, Oxford, 1966; see Appendix.
  • S. Happersett, "Mathematical meditations", Journal of Mathematics and the Arts, 1 (2007), 29 - 33.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954; see esp. p. 148.
  • V. E. Hoggatt, Jr., Fibonacci and Lucas Numbers. Houghton, Boston, MA, 1969.
  • E. Horowitz and S. Sahni, Fundamentals of Data Structures, Computer Science Press, 1976; p. 338.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 63.
  • C. Kicey and K. Klimko, Some geometry of Pascal's triangle, Pi Mu Epsilon Journal, 13(4):229-245 (2011).
  • D. E. Knuth, The Art of Computer Programming. Addison-Wesley, Reading, MA, Vol. 1, p. 78; Vol. 3, Section 6.2.1.
  • Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.
  • Leonardo of Pisa [Leonardo Pisano], Liber Abaci [The Book of Calculation], 1202.
  • D. Litchfield, D. Goldenheim and C. H. Dietrich, Euclid, Fibonacci and Sketchpad, Math. Teacher, 90 (1997).
  • Lukovits et al., Nanotubes: Number of Kekulé structures and aromaticity, J. Chem. Inf. Comput. Sci, (2003), vol. 43, 609-614. See eq. 2 on page 610.
  • I. Lukovits and D. Janezic, "Enumeration of conjugated circuits in nanotubes", J. Chem. Inf. Comput. Sci., vol. 44, 410-414 (2004). See Table 1, second column.
  • B. Malesevic: Some combinatorial aspects of differential operation composition on the space R^n, Univ. Beograd, Publ. Elektrotehn. Fak., Ser. Mat. 9 (1998), 29-33.
  • G. Mantel, Resten van wederkeerige Reeksen, Nieuw Archief v. Wiskunde, 2nd series, I (1894), 172-184.
  • C. N. Menhinick, The Fibonacci Resonance and other new Golden Ratio discoveries, Onperson, (2015), pages 200-206.
  • S. Mneimneh, Fibonacci in The Curriculum: Not Just a Bad Recurrence, in Proceeding SIGCSE '15 Proceedings of the 46th ACM Technical Symposium on Computer Science Education, Pages 253-258.
  • Hilary I. Okagbue, Muminu O. Adamu, Sheila A. Bishop, Abiodun A. Opanuga, Digit and Iterative Digit Sum of Fibonacci numbers, their identities and powers, International Journal of Applied Engineering Research ISSN 0973-4562 Volume 11, Number 6 (2016) pp 4623-4627.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 49.
  • Clifford A. Pickover, The Math Book, From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics, Sterling Publ., NY, 2009, page 274.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 55-58, 255-260.
  • Alfred S. Posamentier and I. Lehmann, The Fabulous Fibonacci Numbers, Prometheus Books, Amherst, NY 2007.
  • Paulo Ribenboim, The New Book of Prime Number Records, Springer, 1996.
  • Paulo Ribenboim, My Numbers, My Friends: Popular Lectures on Number Theory, Springer-Verlag, NY, 2000, p. 3.
  • Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See pp. 45, 59.
  • J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, Princeton, NJ, 1978.
  • A. M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.
  • J. Roberts, Lure of the Integers, Math. Assoc. America, 1992, p. 288.
  • Manfred R. Schroeder, "Number Theory in Science and Communication", 5th ed., Springer-Verlag, 2009
  • L. E. Sigler, Fibonacci's Liber Abaci, Springer, 2003, pp. 404-405 and [26] on p. 627.
  • Simson, [No first name given], An explanation of an obscure passage in Albert Girard's Commentary ..., Phil. Trans. Royal Soc., 10 (1753), 430-433.
  • Parmanand Singh, The so-called fibonacci numbers in ancient and medieval India, Historia Mathematica, vol. 12 (1985), 229-244.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 26-30.
  • S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.
  • N. N. Vorob'ev, Chisla fibonachchi [Russian], Moscow, 1951. English translation, Fibonacci Numbers, Blaisdell, New York and London, 1961.
  • N. N. Vorobiev, Fibonacci Numbers, Birkhauser (Basel; Boston) 2002.
  • D. Wells, The Penguin Dictionary of Curious and Interesting Numbers, pp. 61-67, Penguin Books 1987.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 53.
  • R. Witula, D. Slota, delta-Fibonacci Numbers, Appl. Anal. Discrete Math., 3 (2009), 310-329.

Links

Crossrefs

Cf. A001622 (phi), A039834 (signed Fibonacci numbers), A001519 (F(2n-1)), A001906 (F(2n)), A001690 (complement), A000213, A000288, A000322, A000383, A060455, A030186, A020695, A020701, A060280 (inv. Eul. Trans), A071679, A099731, A100492, A094216, A094638, A000108, A101399, A101400, A001611, A000071, A157725, A001911, A157726, A006327, A157727, A157728, A157729, A167616, A059929, A144152, A152063, A114690, A003893, A000032, A060441, A000930, A003269, A000957, A057078, A007317, A091867, A104597, A249548, A262342, A001060, A022095, A072649, A163733, A073133, A166861 (Euler Transform), A337009 (Multiset Transf.).
First row of arrays A103323, A172236, A234357. Second row of arrays A099390, A048887, and A092921 (k-generalized Fibonacci numbers).
Cf. also A001175 (Pisano periods), A001177 (Entry points), A001176 (number of zeros in a fundamental period).
Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.
Fibonacci-Cayley triangle: A327992.
Boustrophedon transforms: A000738, A000744.
Powers: A103323, A105317, A254719.
Numbers of prime factors: A022307 and A038575.
Cf. A061446 (primitive part of Fibonacci numbers), A000010 (comments on product formulas).
Number of digits of F(n): A020909 (base 2), A020911 (base 3), A020912 (base 4), A020913 (base 5), A060384 (base 10), A261585 (base 60).

Programs

  • Axiom
    [fibonacci(n) for n in 0..50]
  • GAP
    Fib:=[0,1];; for n in [3..10^3] do Fib[n]:=Fib[n-1]+Fib[n-2]; od; Fib; # Muniru A Asiru, Sep 03 2017
  • Haskell
    -- Based on code from http://www.haskell.org/haskellwiki/The_Fibonacci_sequence
-- which also has other versions.
fib :: Int -> Integer
fib n = fibs !! n
    where
        fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
{- Example of use: map fib [0..38] Gerald McGarvey, Sep 29 2009 -}
  • Julia
    function fib(n)
   F = BigInt[1 1; 1 0]
   Fn = F^n
   Fn[2, 1]
end
println([fib(n) for n in 0:38]) # Peter Luschny, Feb 23 2017
  • Julia
    # faster
function fibrec(n::Int)
    n == 0 && return (BigInt(0), BigInt(1))
    a, b = fibrec(div(n, 2))
    c = a * (b * 2 - a)
    d = a * a + b * b
    iseven(n) ? (c, d) : (d, c + d)
end
fibonacci(n::Int) = fibrec(n)[1]
println([fibonacci(n) for n in 0:40]) # Peter Luschny, Apr 03 2022
  • Magma
    [Fibonacci(n): n in [0..38]];
  • Maple
    A000045 := proc(n) combinat[fibonacci](n); end;
ZL:=[S, {a = Atom, b = Atom, S = Prod(X,Sequence(Prod(X,b))), X = Sequence(b,card >= 1)}, unlabelled]: seq(combstruct[count](ZL, size=n), n=0..38); # Zerinvary Lajos, Apr 04 2008
spec := [B, {B=Sequence(Set(Z, card>1))}, unlabeled ]: seq(combstruct[count](spec, size=n), n=1..39); # Zerinvary Lajos, Apr 04 2008
# The following Maple command isFib(n) yields true or false depending on whether n is a Fibonacci number or not.
with(combinat): isFib := proc(n) local a: a := proc(n) local j: for j while fibonacci(j) <= n do fibonacci(j) end do: fibonacci(j-1) end proc: evalb(a(n) = n) end proc: # Emeric Deutsch, Nov 11 2014
  • Mathematica
    Table[Fibonacci[k], {k, 0, 50}] (* Mohammad K. Azarian, Jul 11 2015 *)
Table[2^n Sqrt @ Product[(Cos[Pi k/(n + 1)]^2 + 1/4), {k, n}] // FullSimplify, {n, 15}]; (* Kasteleyn's formula specialized, Sarah-Marie Belcastro, Jul 04 2009 *)
LinearRecurrence[{1, 1}, {0, 1}, 40] (* Harvey P. Dale, Aug 03 2014 *)
Fibonacci[Range[0, 20]] (* Eric W. Weisstein, Sep 22 2017 *)
CoefficientList[Series[-(x/(-1 + x + x^2)), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 22 2017 *)
  • Maxima
    makelist(fib(n),n,0,100); /* Martin Ettl, Oct 21 2012 */
  • PARI
    a(n) = fibonacci(n)
  • PARI
    a(n) = imag(quadgen(5)^n)
  • PARI
    a(n)=my(phi=quadgen(5));(phi^n-(-1/phi)^n)/(2*phi-1) \\ Charles R Greathouse IV, Jun 17 2012
  • PARI
    is_A000045=A010056 \\ Characteristic function: see there. - M. F. Hasler, Feb 21 2025
  • Python
    # From Jaap Spies, Jan 05 2007, updated by Peter Luschny, Feb 21 2023:
from itertools import islice
def fib_gen():
    x, y = 0, 1
    while True:
        yield x
        x, y = y, x + y
fib_list = lambda n: list(islice(fib_gen(), n))
  • Python
    is_A000045 = A010056 # See there: Characteristic function. Used e.g. in A377092.
A000045 = lambda n: (4<M. F. Hasler, improving old code from 2023, Feb 20 2025
  • Python
    [(i:=-1)+(j:=1)] + [(j:=i+j)+(i:=j-i) for  in range(100)] # _Jwalin Bhatt, Apr 03 2025
  • Sage
    # Demonstration program from Jaap Spies:
a = sloane.A000045; # choose sequence
print(a)            # This returns the name of the sequence.
print(a(38))        # This returns the 38th term of the sequence.
print(a.list(39))   # This returns a list of the first 39 terms.
  • Sage
    a = BinaryRecurrenceSequence(1,1); print([a(n) for n in range(20)])
# Closed form integer formula with F(1) = 0 from Paul Hankin (see link).
F = lambda n: (4<<(n-1)*(n+2))//((4<<2*(n-1))-(2<<(n-1))-1)&((2<<(n-1))-1)
print([F(n) for n in range(20)]) # Peter Luschny, Aug 28 2016
  • Sage
    print(list(fibonacci_sequence(0, 40))) # Bruno Berselli, Jun 26 2014
  • Scala
    def fibonacci(n: BigInt): BigInt = {
  val zero = BigInt(0)
  def fibTail(n: BigInt, a: BigInt, b: BigInt): BigInt = n match {
    case `zero` => a
    case _ => fibTail(n - 1, b, a + b)
  }
  fibTail(n, 0, 1)
} // Based on "Case 3: Tail Recursion" from Carrasquel (2016) link
(0 to 49).map(fibonacci()) // _Alonso del Arte, Apr 13 2019

Formula

G.f.: x / (1 - x - x^2).
G.f.: Sum_{n>=0} x^n * Product_{k=1..n} (k + x)/(1 + k*x). - Paul D. Hanna, Oct 26 2013
F(n) = ((1+sqrt(5))^n - (1-sqrt(5))^n)/(2^n*sqrt(5)).
Alternatively, F(n) = ((1/2+sqrt(5)/2)^n - (1/2-sqrt(5)/2)^n)/sqrt(5).
F(n) = F(n-1) + F(n-2) = -(-1)^n F(-n).
F(n) = round(phi^n/sqrt(5)).
F(n+1) = Sum_{j=0..floor(n/2)} binomial(n-j, j).
A strong divisibility sequence, that is, gcd(a(n), a(m)) = a(gcd(n, m)) for all positive integers n and m. - Michael Somos, Jan 03 2017
E.g.f.: (2/sqrt(5))*exp(x/2)*sinh(sqrt(5)*x/2). - Len Smiley, Nov 30 2001
[0 1; 1 1]^n [0 1] = [F(n); F(n+1)]
x | F(n) ==> x | F(kn).
A sufficient condition for F(m) to be divisible by a prime p is (p - 1) divides m, if p == 1 or 4 (mod 5); (p + 1) divides m, if p == 2 or 3 (mod 5); or 5 divides m, if p = 5. (This is essentially Theorem 180 in Hardy and Wright.) - Fred W. Helenius (fredh(AT)ix.netcom.com), Jun 29 2001
a(n)=F(n) has the property: F(n)*F(m) + F(n+1)*F(m+1) = F(n+m+1). - Miklos Kristof, Nov 13 2003
From Kurmang. Aziz. Rashid, Feb 21 2004: (Start)
Conjecture 1: for n >= 2, sqrt(F(2n+1) + F(2n+2) + F(2n+3) + F(2n+4) + 2*(-1)^n) = (F(2n+1) + 2*(-1)^n)/F(n-1). [For a proof see Comments section.]
Conjecture 2: for n >= 0, (F(n+2)*F(n+3)) - (F(n+1)*F(n+4)) + (-1)^n = 0.
[Two more conjectures removed by Peter Luschny, Nov 17 2017]
Theorem 1: for n >= 0, (F(n+3)^ 2 - F(n+1)^ 2)/F(n+2) = (F(n+3)+ F(n+1)).
Theorem 2: for n >= 0, F(n+10) = 11*F(n+5) + F(n).
Theorem 3: for n >= 6, F(n) = 4*F(n-3) + F(n-6). (End)
Conjecture 2 of Rashid is actually a special case of the general law F(n)*F(m) + F(n+1)*F(m+1) = F(n+m+1) (take n <- n+1 and m <- -(n+4) in this law). - Harmel Nestra (harmel.nestra(AT)ut.ee), Apr 22 2005
Conjecture 2 of Rashid Kurmang simplified: F(n)*F(n+3) = F(n+1)*F(n+2)-(-1)^n. Follows from d'Ocagne's identity: m=n+2. - Alex Ratushnyak, May 06 2012
Conjecture: for all c such that 2-phi <= c < 2*(2-phi) we have F(n) = floor(phi*a(n-1)+c) for n > 2. - Gerald McGarvey, Jul 21 2004
For x > phi, Sum_{n>=0} F(n)/x^n = x/(x^2 - x - 1). - Gerald McGarvey, Oct 27 2004
F(n+1) = exponent of the n-th term in the series f(x, 1) determined by the equation f(x, y) = xy + f(xy, x). - Jonathan Sondow, Dec 19 2004
a(n-1) = Sum_{k=0..n} (-1)^k*binomial(n-ceiling(k/2), floor(k/2)). - Benoit Cloitre, May 05 2005
a(n) = Sum_{k=0..n} abs(A108299(n, k)). - Reinhard Zumkeller, Jun 01 2005
a(n) = A001222(A000304(n)).
F(n+1) = Sum_{k=0..n} binomial((n+k)/2, (n-k)/2)(1+(-1)^(n-k))/2. - Paul Barry, Aug 28 2005
Fibonacci(n) = Product_{j=1..ceiling(n/2)-1} (1 + 4(cos(j*Pi/n))^2). [Bicknell and Hoggatt, pp. 47-48.] - Emeric Deutsch, Oct 15 2006
F(n) = 2^-(n-1)*Sum_{k=0..floor((n-1)/2)} binomial(n,2*k+1)*5^k. - Hieronymus Fischer, Feb 07 2006
a(n) = (b(n+1) + b(n-1))/n where {b(n)} is the sequence A001629. - Sergio Falcon, Nov 22 2006
F(n*m) = Sum_{k = 0..m} binomial(m,k)*F(n-1)^k*F(n)^(m-k)*F(m-k). The generating function of F(n*m) (n fixed, m = 0,1,2,...) is G(x) = F(n)*x / ((1 - F(n-1)*x)^2 - F(n)*x*(1 - F(n-1)*x) - (F(n)*x)^2). E.g., F(15) = 610 = F(5*3) = binomial(3,0)* F(4)^0*F(5)^3*F(3) + binomial(3,1)* F(4)^1*F(5)^2*F(2) + binomial(3,2)* F(4)^2*F(5)^1*F(1) + binomial(3,3)* F(4)^3*F(5)^0*F(0) = 1*1*125*2 + 3*3*25*1 + 3*9*5*1 + 1*27*1*0 = 250 + 225 + 135 + 0 = 610. - Miklos Kristof, Feb 12 2007
From Miklos Kristof, Mar 19 2007: (Start)
Let L(n) = A000032(n) = Lucas numbers. Then:
For a >= b and odd b, F(a+b) + F(a-b) = L(a)*F(b).
For a >= b and even b, F(a+b) + F(a-b) = F(a)*L(b).
For a >= b and odd b, F(a+b) - F(a-b) = F(a)*L(b).
For a >= b and even b, F(a+b) - F(a-b) = L(a)*F(b).
F(n+m) + (-1)^m*F(n-m) = F(n)*L(m);
F(n+m) - (-1)^m*F(n-m) = L(n)*F(m);
F(n+m+k) + (-1)^k*F(n+m-k) + (-1)^m*(F(n-m+k) + (-1)^k*F(n-m-k)) = F(n)*L(m)*L(k);
F(n+m+k) - (-1)^k*F(n+m-k) + (-1)^m*(F(n-m+k) - (-1)^k*F(n-m-k)) = L(n)*L(m)*F(k);
F(n+m+k) + (-1)^k*F(n+m-k) - (-1)^m*(F(n-m+k) + (-1)^k*F(n-m-k)) = L(n)*F(m)*L(k);
F(n+m+k) - (-1)^k*F(n+m-k) - (-1)^m*(F(n-m+k) - (-1)^k*F(n-m-k)) = 5*F(n)*F(m)*F(k). (End)
A corollary to Kristof 2007 is 2*F(a+b) = F(a)*L(b) + L(a)*F(b). - Graeme McRae, Apr 24 2014
For n > m, the sum of the 2m consecutive Fibonacci numbers F(n-m-1) thru F(n+m-2) is F(n)*L(m) if m is odd, and L(n)*F(m) if m is even (see the McRae link). - Graeme McRae, Apr 24 2014.
F(n) = b(n) + (p-1)*Sum_{k=2..n-1} floor(b(k)/p)*F(n-k+1) where b(k) is the digital sum analog of the Fibonacci recurrence, defined by b(k) = ds_p(b(k-1)) + ds_p(b(k-2)), b(0)=0, b(1)=1, ds_p=digital sum base p. Example for base p=10: F(n) = A010077(n) + 9*Sum_{k=2..n-1} A059995(A010077(k))*F(n-k+1). - Hieronymus Fischer, Jul 01 2007
F(n) = b(n)+p*Sum_{k=2..n-1} floor(b(k)/p)*F(n-k+1) where b(k) is the digital product analog of the Fonacci recurrence, defined by b(k) = dp_p(b(k-1)) + dp_p(b(k-2)), b(0)=0, b(1)=1, dp_p=digital product base p. Example for base p=10: F(n) = A074867(n) + 10*Sum_{k=2..n-1} A059995(A074867(k))*F(n-k+1). - Hieronymus Fischer, Jul 01 2007
a(n) = denominator of continued fraction [1,1,1,...] (with n ones); e.g., 2/3 = continued fraction [1,1,1]; where barover[1] = [1,1,1,...] = 0.6180339.... - Gary W. Adamson, Nov 29 2007
F(n + 3) = 2F(n + 2) - F(n), F(n + 4) = 3F(n + 2) - F(n), F(n + 8) = 7F(n + 4) - F(n), F(n + 12) = 18F(n + 6) - F(n). - Paul Curtz, Feb 01 2008
a(2^n) = Product_{i=0..n-2} B(i) where B(i) is A001566. Example 3*7*47 = F(16). - Kenneth J Ramsey, Apr 23 2008
a(n+1) = Sum_{k=0..n} A109466(n,k)*(-1)^(n-k). -Philippe Deléham, Oct 26 2008
a(n) = Sum_{l_1=0..n+1} Sum_{l_2=0..n}...Sum_{l_i=0..n-i}... Sum_{l_n=0..1} delta(l_1,l_2,...,l_i,...,l_n), where delta(l_1,l_2,...,l_i,...,l_n) = 0 if any l_i + l_(i+1) >= 2 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
a(n+1) = 2^n sqrt(Product_{k=1..n} cos(k Pi/(n+1))^2+1/4) (Kasteleyn's formula specialized). - Sarah-Marie Belcastro, Jul 04 2009
a(n+1) = Sum_{k=floor(n/2) mod 5} C(n,k) - Sum_{k=floor((n+5)/2) mod 5} C(n,k) = A173125(n) - A173126(n) = |A054877(n)-A052964(n-1)|. - Henry Bottomley, Feb 10 2010
If p[i] = modp(i,2) and if A is Hessenberg matrix of order n defined by: A[i,j] = p[j-i+1], (i <= j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n >= 1, a(n)=det A. - Milan Janjic, May 02 2010
Limit_{k->oo} F(k+n)/F(k) = (L(n) + F(n)*sqrt(5))/2 with the Lucas numbers L(n) = A000032(n). - Johannes W. Meijer, May 27 2010
For n >= 1, F(n) = round(log_2(2^(phi*F(n-1)) + 2^(phi*F(n-2)))), where phi is the golden ratio. - Vladimir Shevelev, Jun 24 2010, Jun 27 2010
For n >= 1, a(n+1) = ceiling(phi*a(n)), if n is even and a(n+1) = floor(phi*a(n)), if n is odd (phi = golden ratio). - Vladimir Shevelev, Jul 01 2010
a(n) = 2*a(n-2) + a(n-3), n > 2. - Gary Detlefs, Sep 08 2010
a(2^n) = Product_{i=0..n-1} A000032(2^i). - Vladimir Shevelev, Nov 28 2010
a(n)^2 - a(n-1)^2 = a(n+1)*a(n-2), see A121646.
a(n) = sqrt((-1)^k*(a(n+k)^2 - a(k)*a(2n+k))), for any k. - Gary Detlefs, Dec 03 2010
F(2*n) = F(n+2)^2 - F(n+1)^2 - 2*F(n)^2. - Richard R. Forberg, Jun 04 2011
From Artur Jasinski, Nov 17 2011: (Start)
(-1)^(n+1) = F(n)^2 + F(n)*F(1+n) - F(1+n)^2.
F(n) = F(n+2) - 1 + (F(n+1))^4 + 2*(F(n+1)^3*F(n+2)) - (F(n+1)*F(n+2))^2 - 2*F(n+1)(F(n+2))^3 + (F(n+2))^4 - F(n+1). (End)
F(n) = 1 + Sum_{x=1..n-2} F(x). - Joseph P. Shoulak, Feb 05 2012
F(n) = 4*F(n-2) - 2*F(n-3) - F(n-6). - Gary Detlefs, Apr 01 2012
F(n) = round(phi^(n+1)/(phi+2)). - Thomas Ordowski, Apr 20 2012
From Sergei N. Gladkovskii, Jun 03 2012: (Start)
G.f.: A(x) = x/(1-x-x^2) = G(0)/sqrt(5) where G(k) = 1 - ((-1)^k)*2^k/(a^k - b*x*a^k*2^k/(b*x*2^k - 2*((-1)^k)*c^k/G(k+1))) and a=3+sqrt(5), b=1+sqrt(5), c=3-sqrt(5); (continued fraction, 3rd kind, 3-step).
Let E(x) be the e.g.f., i.e.,
E(x) = 1*x + (1/2)*x^2 + (1/3)*x^3 + (1/8)*x^4 + (1/24)*x^5 + (1/90)*x^6 + (13/5040)*x^7 + ...; then
E(x) = G(0)/sqrt(5); G(k) = 1 - ((-1)^k)*2^k/(a^k - b*x*a^k*2^k/(b*x*2^k - 2*((-1)^k)*(k+1)*c^k/G(k+1))), where a=3+sqrt(5), b=1+sqrt(5), c=3-sqrt(5); (continued fraction, 3rd kind, 3-step).
(End)
From Hieronymus Fischer, Nov 30 2012: (Start)
F(n) = 1 + Sum_{j_1=1..n-2} 1 + Sum_{j_1=1..n-2} Sum_{j_2=1..j_1-2} 1 + Sum_{j_1=1..n-2} Sum_{j_2=1..j_1-2} Sum_{j_3=1..j_2-2} 1 + ... + Sum_{j_1=1..n-2} Sum_{j_2=1..j_1-2} Sum_{j_3=1..j_2-2} ... Sum_{j_k=1..j_(k-1)-2} 1, where k = floor((n-1)/2).
Example: F(6) = 1 + Sum_{j=1..4} 1 + Sum_{j=1..4} Sum_{k=1..(j-2)} 1 + 0 = 1 + (1 + 1 + 1 + 1) + (1 + (1 + 1)) = 8.
F(n) = Sum_{j=0..k} S(j+1,n-2j), where k = floor((n-1)/2) and the S(j,n) are the n-th j-simplex sums: S(1,n) = 1 is the 1-simplex sum, S(2,n) = Sum_{k=1..n} S(1,k) = 1+1+...+1 = n is the 2-simplex sum, S(3,n) = Sum_{k=1..n} S(2,k) = 1+2+3+...+n is the 3-simplex sum (= triangular numbers = A000217), S(4,n) = Sum_{k=1..n} S(3,k) = 1+3+6+...+n(n+1)/2 is the 4-simplex sum (= tetrahedral numbers = A000292) and so on.
Since S(j,n) = binomial(n-2+j,j-1), the formula above equals the well-known binomial formula, essentially. (End)
G.f.: A(x) = x / (1 - x / (1 - x / (1 + x))). - Michael Somos, Jan 04 2013
Sum_{n >= 1} (-1)^(n-1)/(a(n)*a(n+1)) = 1/phi (phi=golden ratio). - Vladimir Shevelev, Feb 22 2013
From Raul Prisacariu, Oct 29 2023: (Start)
For odd k, Sum_{n >= 1} a(k)^2*(-1)^(n-1)/(a(k*n)*a(k*n+k)) = phi^(-k).
For even k, Sum_{n >= 1} a(k)^2/(a(k*n)*a(k*n+k)) = phi^(-k). (End)
From Vladimir Shevelev, Feb 24 2013: (Start)
(1) Expression a(n+1) via a(n): a(n+1) = (a(n) + sqrt(5*(a(n))^2 + 4*(-1)^n))/2;
(2) Sum_{k=1..n} (-1)^(k-1)/(a(k)*a(k+1)) = a(n)/a(n+1);
(3) a(n)/a(n+1) = 1/phi + r(n), where |r(n)| < 1/(a(n+1)*a(n+2)). (End)
F(n+1) = F(n)/2 + sqrt((-1)^n + 5*F(n)^2/4), n >= 0. F(n+1) = U_n(i/2)/i^n, (U:= Chebyshev polynomial of the 2nd kind, i=sqrt(-1)). - Bill Gosper, Mar 04 2013
G.f.: -Q(0) where Q(k) = 1 - (1+x)/(1 - x/(x - 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Mar 06 2013
G.f.: x - 1 - 1/x + (1/x)/Q(0), where Q(k) = 1 - (k+1)*x/(1 - x/(x - (k+1)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, Apr 23 2013
G.f.: x*G(0), where G(k) = 1 + x*(1+x)/(1 - x*(1+x)/(x*(1+x) + 1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jul 08 2013
G.f.: x^2 - 1 + 2*x^2/(W(0)-2), where W(k) = 1 + 1/(1 - x*(k + x)/( x*(k+1 + x) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013
G.f.: Q(0) - 1, where Q(k) = 1 + x^2 + (k+2)*x - x*(k+1 + x)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Oct 06 2013
Let b(n) = b(n-1) + b(n-2), with b(0) = 0, b(1) = phi. Then, for n >= 2, F(n) = floor(b(n-1)) if n is even, F(n) = ceiling(b(n-1)), if n is odd, with convergence. - Richard R. Forberg, Jan 19 2014
a(n) = Sum_{t1*g(1)+t2*g(2)+...+tn*g(n)=n} multinomial(t1+t2+...+tn,t1,t2,...,tn), where g(k)=2*k-1. - Mircea Merca, Feb 27 2014
F(n) = round(sqrt(F(n-1)^2 + F(n)^2 + F(n+1)^2)/2), for n > 0. This rule appears to apply to any sequence of the form a(n) = a(n-1) + a(n-2), for any two values of a(0) and a(1), if n is sufficiently large. - Richard R. Forberg, Jul 27 2014
F(n) = round(2/(1/F(n) + 1/F(n+1) + 1/F(n+2))), for n > 0. This rule also appears to apply to any sequence of the form a(n) = a(n-1) + a(n-2), for any two values of a(0) and a(1), if n is sufficiently large. - Richard R. Forberg, Aug 03 2014
F(n) = round(1/(Sum_{j>=n+2} 1/F(j))). - Richard R. Forberg, Aug 14 2014
a(n) = hypergeometric([-n/2+1/2, -n/2+1], [-n+1], -4) for n >= 2. - Peter Luschny, Sep 19 2014
Limit_{n -> oo} (log F(n+1)/log F(n))^n = e. - Thomas Ordowski, Oct 06 2014
F(n) = (L(n+1)^2 - L(n-1)^2)/(5*L(n)), where L(n) is A000032(n), with a similar inverse relationship. - Richard R. Forberg, Nov 17 2014
Consider the graph G[1-vertex;1-loop,2-loop] in comment above. Construct the power matrix array T(n,j) = [A^*j]*[S^*(j-1)] where A=(1,1,0,...) and S=(0,1,0,...)(A063524). [* is convolution operation] Define S^*0=I with I=(1,0,...). Then T(n,j) counts n-walks containing (j) loops and a(n-1) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Nov 21 2014
Define F(-n) to be F(n) for n odd and -F(n) for n even. Then for all n and k, F(n) = F(k)*F(n-k+3) - F(k-1)*F(n-k+2) - F(k-2)*F(n-k) + (-1)^k*F(n-2k+2). - Charlie Marion, Dec 04 2014
F(n+k)^2 - L(k)*F(n)*F(n+k) + (-1)^k*F(n)^2 = (-1)^n*F(k)^2, if L(k) = A000032(k). - Alexander Samokrutov, Jul 20 2015
F(2*n) = F(n+1)^2 - F(n-1)^2, similar to Koshy (D) and Forberg 2011, but different. - Hermann Stamm-Wilbrandt, Aug 12 2015
F(n+1) = ceiling( (1/phi)*Sum_{k=0..n} F(k) ). - Tom Edgar, Sep 10 2015
a(n) = (L(n-3) + L(n+3))/10 where L(n)=A000032(n). - J. M. Bergot, Nov 25 2015
From Bob Selcoe, Mar 27 2016: (Start)
F(n) = (F(2n+k+1) - F(n+1)*F(n+k+1))/F(n+k), k >= 0.
Thus when k=0: F(n) = sqrt(F(2n+1) - F(n+1)^2).
F(n) = (F(3n) - F(n+1)^3 + F(n-1)^3)^(1/3).
F(n+2k) = binomial transform of any subsequence starting with F(n). Example F(6)=8: 1*8 = F(6)=8; 1*8 + 1*13 = F(8)=21; 1*8 + 2*13 + 1*21 = F(10)=55; 1*8 + 3*13 + 3*21 + 1*34 = F(12)=144, etc. This formula applies to Fibonacci-type sequences with any two seed values for a(0) and a(1) (e.g., Lucas sequence A000032: a(0)=2, a(1)=1).
(End)
F(n) = L(k)*F(n-k) + (-1)^(k+1)*F(n-2k) for all k >= 0, where L(k) = A000032(k). - Anton Zakharov, Aug 02 2016
From Ilya Gutkovskiy, Aug 03 2016: (Start)
a(n) = F_n(1), where F_n(x) are the Fibonacci polynomials.
Inverse binomial transform of A001906.
Number of zeros in substitution system {0 -> 11, 1 -> 1010} at step n from initial string "1" (1 -> 1010 -> 101011101011 -> ...) multiplied by 1/A000079(n). (End)
For n >= 2, a(n) = 2^(n^2+n) - (4^n-2^n-1)*floor(2^(n^2+n)/(4^n-2^n-1)) - 2^n*floor(2^(n^2) - (2^n-1-1/2^n)*floor(2^(n^2+n)/(4^n-2^n-1))). - Benoit Cloitre, Apr 17 2017
f(n+1) = Sum_{j=0..floor(n/2)} Sum_{k=0..j} binomial(n-2j,k)*binomial(j,k). - Tony Foster III, Sep 04 2017
F(n) = Sum_{k=0..floor((n-1)/2)} ( (n-k-1)! / ((n-2k-1)! * k!) ). - Zhandos Mambetaliyev, Nov 08 2017
For x even, F(n) = (F(n+x) + F(n-x))/L(x). For x odd, F(n) = (F(n+x) - F(n-x))/L(x) where n >= x in both cases. Therefore F(n) = F(2*n)/L(n) for n >= 0. - David James Sycamore, May 04 2018
From Isaac Saffold, Jul 19 2018: (Start)
Let [a/p] denote the Legendre symbol. Then, for an odd prime p:
F(p+n) == [5/p]*F([5/p]+n) (mod p), if [5/p] = 1 or -1.
F(p+n) == 3*F(n) (mod p), if [5/p] = 0 (i.e., p = 5).
This is true for negative-indexed terms as well, if this sequence is extended by the negafibonacci numbers (i.e., F(-n) = A039834(n)). (End)
a(n) = A094718(4, n). a(n) = A101220(0, j, n).
a(n) = A090888(0, n+1) = A118654(0, n+1) = A118654(1, n-1) = A109754(0, n) = A109754(1, n-1), for n > 0.
a(n) = (L(n-3) + L(n-2) + L(n-1) + L(n))/5 with L(n)=A000032(n). - Art Baker, Jan 04 2019
F(n) = F(k-1)*F(abs(n-k-2)) + F(k-1)*F(n-k-1) + F(k)*F(abs(n-k-2)) + 2*F(k)*F(n-k-1), for n > k > 0. - Joseph M. Shunia, Aug 12 2019
F(n) = F(n-k+2)*F(k-1) + F(n-k+1)*F(k-2) for all k such that 2 <= k <= n. - Michael Tulskikh, Oct 09 2019
F(n)^2 - F(n+k)*F(n-k) = (-1)^(n+k) * F(k)^2 for 2 <= k <= n [Catalan's identity]. - Hermann Stamm-Wilbrandt, May 07 2021
Sum_{n>=1} 1/a(n) = A079586 is the reciprocal Fibonacci constant. - Gennady Eremin, Aug 06 2021
a(n) = Product_{d|n} b(d) = Product_{k=1..n} b(gcd(n,k))^(1/phi(n/gcd(n,k))) = Product_{k=1..n} b(n/gcd(n,k))^(1/phi(n/gcd(n,k))) where b(n) = A061446(n) = primitive part of a(n), phi(n) = A000010(n). - Richard L. Ollerton, Nov 08 2021
a(n) = 2*i^(1-n)*sin(n*arccos(i/2))/sqrt(5), i=sqrt(-1). - Bill Gosper, May 05 2022
a(n) = i^(n-1)*sin(n*c)/sin(c) = i^(n-1)*sin(c*n)*csc(c), where c = Pi/2 + i*arccsch(2). - Peter Luschny, May 23 2022
F(2n) = Sum_{k=1..n} (k/5)*binomial(2n, n+k), where (k/5) is the Legendre or Jacobi Symbol; F(2n+1)= Sum_{k=1..n} (-(k+2)/5)*binomial(2n+1, n+k), where (-(k+2)/5) is the Legendre or Jacobi Symbol. For example, F(10) = 1*binomial(10,6) - 1*binomial(10,7) - 1*binomial(10,8) + 1*binomial(10,9) + 0*binomial(10,10), F(11) = 1*binomial(11,6) - 1*binomial(11,7) + 0*binomial(11,8) - 1*binomial(11,9) + 1*binomial(11,10) + 1*binomial(11,11). - Yike Li, Aug 21 2022
For n > 0, 1/F(n) = Sum_{k>=1} F(n*k)/(F(n+2)^(k+1)). - Diego Rattaggi, Oct 26 2022
From Andrea Pinos, Dec 02 2022: (Start)
For n == 0 (mod 4): F(n) = F((n+2)/2)*( F(n/2) + F((n/2)-2) ) + 1;
For n == 1 (mod 4): F(n) = F((n-1)/2)*( F((n-1)/2) + F(2+(n-1)/2) ) + 1;
For n == 2 (mod 4): F(n) = F((n-2)/2)*( F(n/2) + F((n/2)+2) ) + 1;
For n == 3 (mod 4): F(n) = F((n-1)/2)*( F((n-1)/2) + F(2+(n-1)/2) ) - 1. (End)
F(n) = Sum_{i=0..n-1} F(i)^2 / F(n-1). - Jules Beauchamp, May 03 2025

A000041 a(n) is the number of partitions of n (the partition numbers).

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

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 sequence of positive integers p = p_1 ... p_k is a descending partition of the positive integer n if p_1 + ... + p_k = n and p_1 >= ... >= p_k. If formally needed p_j = 0 is appended to p for j > k. Let P_n denote the set of these partition for some n >= 1. Then a(n) = 1 + Sum_{p in P_n} floor((p_1-1)/(p_2+1)). (Cf. A000065, where the formula reduces to the sum.) Proof in Kelleher and O'Sullivan (2009). For example a(6) = 1 + 0 + 0 + 0 + 0 + 1 + 0 + 0 + 1 + 1 + 2 + 5 = 11. - Peter Luschny, Oct 24 2010
Let n = Sum( k_(p_m) p_m ) = k_1 + 2k_2 + 5k_5 + 7k_7 + ..., where p_m is the m-th generalized pentagonal number (A001318). Then a(n) is the sum over all such pentagonal partitions of n of (-1)^(k_5+k_7 + k_22 + ...) ( k_1 + k_2 + k_5 + ...)! /( k_1! k_2! k_5! ...), where the exponent of (-1) is the sum of all the k's corresponding to even-indexed GPN's. - Jerome Malenfant, Feb 14 2011
From Jerome Malenfant, Feb 14 2011: (Start)
The matrix of a(n) values
a(0)
a(1) a(0)
a(2) a(1) a(0)
a(3) a(2) a(1) a(0)
....
a(n) a(n-1) a(n-2) ... a(0)
is the inverse of the matrix
1
-1 1
-1 -1 1
0 -1 -1 1
....
-d_n -d_(n-1) -d_(n-2) ... -d_1 1
where d_q = (-1)^(m+1) if q = m(3m-1)/2 = the m-th generalized pentagonal number (A001318), = 0 otherwise. (End)
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, ) to be a partition of n with exactly k parts, with s(j) parts t(j) identical to each other and distinct from all the other parts. Note that n >= k, j <= k, 0 <= s(j) <= k, s(1)t(1) + ... + s(j)t(j) = n and s(1) + ... + s(j) = k. Then there are up to a(k) segmented partitions of n with exactly k parts. - Gregory L. Simay, Nov 08 2015
(End)
From Gregory L. Simay, Nov 09 2015: (Start)
The polynomials for a(n, k, ) have degree j-1.
a(n, k, ) = 1 if n = 0 mod k, = 0 otherwise
a(rn, rk, ) = a(n, k, )
a(n odd, k, ) = 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 < n
a(n, k, ) = a(n - j(j-1)/2, k)
(End)
a(10^20) was computed using the NIST Arb package. It has 11140086260 digits and its head and tail sections are 18381765...88091448. See the Johansson 2015 link. - Stanislav Sykora, Feb 01 2016
Satisfies Benford's law [Anderson-Rolen-Stoehr, 2011]. - N. J. A. Sloane, Feb 08 2017
The partition function p(n) is log-concave for all n>25 [DeSalvo-Pak, 2014]. - Michel Marcus, Apr 30 2019
a(n) is also the dimension of the n-th cohomology of the infinite real Grassmannian with coefficients in Z/2. - Luuk Stehouwer, Jun 06 2021
Number of equivalence relations on n unlabeled nodes. - Lorenzo Sauras Altuzarra, Jun 13 2022
Equivalently, number of idempotent mappings f from a set X of n elements into itself (i.e., satisfying f o f = f) up to permutation (i.e., f~f' :<=> There is a permutation sigma in Sym(X) such that f' o sigma = sigma o f). - Philip Turecek, Apr 17 2023
Conjecture: Each integer n > 2 different from 6 can be written as a sum of finitely many numbers of the form a(k) + 2 (k > 0) with no summand dividing another. This has been verified for n <= 7140. - Zhi-Wei Sun, May 16 2023
a(n) is also the number of partitions of n*(n+3)/2 into n distinct parts. - David García Herrero, Aug 20 2024
a(n) is also the number of non-isomorphic sigma algebras on {1,...,n}. A000110(n) counts all sigma algebras on {1,...,n}. Every sigma algebra on a finite set X is exactly the collection of all unions of its atoms (its minimal nonempty members), and those atoms partition X. An isomorphism of sigma algebras must map atoms to atoms, so the isomorphism class of a sigma algebra is determined by the multiset of its atom-sizes, which is an integer partition of n. - Matthew Azar, Jul 18 2025

Examples

			a(5) = 7 because there are seven partitions of 5, namely: {1, 1, 1, 1, 1}, {2, 1, 1, 1}, {2, 2, 1}, {3, 1, 1}, {3, 2}, {4, 1}, {5}. - _Bob Selcoe_, Jul 08 2014
G.f. = 1 + x + 2*x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 11*x^6 + 15*x^7 + 22*x^8 + ...
G.f. = 1/q + q^23 + 2*q^47 + 3*q^71 + 5*q^95 + 7*q^119 + 11*q^143 + 15*q^167 + ...
From _Gregory L. Simay_, Nov 08 2015: (Start)
There are up to a(4)=5 segmented partitions of the partitions of n with exactly 4 parts. They are a(n,4, <4>), a(n,4,<3,1>), a(n,4,<2,2>), a(n,4,<2,1,1>), a(n,4,<1,1,1,1>).
The partition 8,8,8,8 is counted in a(32,4,<4>).
The partition 9,9,9,5 is counted in a(32,4,<3,1>).
The partition 11,11,5,5 is counted in a(32,4,<2,2>).
The partition 13,13,5,1 is counted in a(32,4,<2,1,1>).
The partition 14,9,6,3 is counted in a(32,4,<1,1,1,1>).
a(n odd,4,<2,2>) = 0.
a(12, 6, <2,2,2>) = a(6,3,<1,1,1>) = a(6-3,3) = a(3,3) = 1. The lone partition is 3,3,2,2,1,1.
(End)

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.
  • Florian Cajori, A History of Mathematical Notations, Dover edition (2012), par. 411.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 94-96.
  • 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, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, pp. 83-100, 113-131.
  • 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.
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 286-289, 297-298, 303.
  • Robert M. Young, "Excursions in Calculus", Mathematical Association of America, p. 367.

Links

Crossrefs

Cf. A000009, A000079, A000203, A001318, A008284, A026820, A065446, A078506, A113685, A132311, A000248, A000110.
Partial sums give A000070.
For successive differences see A002865, A053445, A072380, A081094, A081095.
Antidiagonal sums of triangle A092905. a(n) = A054225(n,0).
Boustrophedon transforms: A000733, A000751.
Cf. A167376 (complement), A061260 (multisets), A000700 (self-conjug), A330644 (not self-conj).

Programs

  • GAP
    List([1..10],n->Size(OrbitsDomain(SymmetricGroup(IsPermGroup,n),SymmetricGroup(IsPermGroup,n),\^))); # Attila Egri-Nagy, Aug 15 2014
  • 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
-- Reinhard Zumkeller, Nov 03 2015, Nov 04 2013
  • Julia
    # DedekindEta is defined in A000594
A000041List(len) = DedekindEta(len, -1)
A000041List(50) |> println # Peter Luschny, Mar 09 2018
  • Magma
    a:= func< n | NumberOfPartitions(n) >; [ a(n) : n in [0..10]];
  • Maple
    A000041 := n -> combinat:-numbpart(n): [seq(A000041(n), n=0..50)]; # Warning: Maple 10 and 11 give incorrect answers in some cases: A110375.
spec := [B, {B=Set(Set(Z,card>=1))}, unlabeled ];
[seq(combstruct[count](spec, size=n), n=0..50)];
with(combstruct):ZL0:=[S,{S=Set(Cycle(Z,card>0))}, unlabeled]: seq(count(ZL0,size=n),n=0..45); # Zerinvary Lajos, Sep 24 2007
G:={P=Set(Set(Atom,card>0))}: combstruct[gfsolve](G,labeled,x); seq(combstruct[count]([P,G,unlabeled],size=i),i=0..45); # Zerinvary Lajos, Dec 16 2007
# Using the function EULER from Transforms (see link at the bottom of the page).
1,op(EULER([seq(1,n=1..49)])); # Peter Luschny, Aug 19 2020
  • Mathematica
    Table[ PartitionsP[n], {n, 0, 45}]
a[ n_] := SeriesCoefficient[ q^(1/24) / DedekindEta[ Log[q] / (2 Pi I)], {q, 0, n}]; (* Michael Somos, Jul 11 2011 *)
a[ n_] := SeriesCoefficient[ 1 / Product[ 1 - x^k, {k, n}], {x, 0, n}]; (* Michael Somos, Jul 11 2011 *)
CoefficientList[1/QPochhammer[q] + O[q]^100, q] (* Jean-François Alcover, Nov 25 2015 *)
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 *)
  • Maxima
    num_partitions(60,list); /* Emanuele Munarini, Feb 24 2014 */
  • MuPAD
    combinat::partitions::count(i) $i=0..54 // Zerinvary Lajos, Apr 16 2007
  • PARI
    {a(n) = if( n<0, 0, polcoeff( 1 / eta(x + x * O(x^n)), n))};
  • PARI
    /* The Hardy-Ramanujan-Rademacher exact formula in PARI is as follows (this is no longer necessary since it is now built in to the numbpart command): */
Psi(n, q) = local(a, b, c); a=sqrt(2/3)*Pi/q; b=n-1/24; c=sqrt(b); (sqrt(q)/(2*sqrt(2)*b*Pi))*(a*cosh(a*c)-(sinh(a*c)/c))
L(n, q) = if(q==1,1,sum(h=1,q-1,if(gcd(h,q)>1,0,cos((g(h,q)-2*h*n)*Pi/q))))
g(h, q) = if(q<3,0,sum(k=1,q-1,k*(frac(h*k/q)-1/2)))
part(n) = round(sum(q=1,max(5,0.5*sqrt(n)),L(n,q)*Psi(n,q)))
/* Ralf Stephan, Nov 30 2002, fixed by Vaclav Kotesovec, Apr 09 2018 */
  • PARI
    {a(n) = numbpart(n)};
  • PARI
    {a(n) = if( n<0, 0, polcoeff( sum( k=1, sqrtint(n), x^k^2 / prod( i=1, k, 1 - x^i, 1 + x * O(x^n))^2, 1), n))};
  • PARI
    f(n)= my(v,i,k,s,t);v=vector(n,k,0);v[n]=2;t=0;while(v[1]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
  • Perl
    use ntheory ":all"; my @p = map { partitions($) } 0..100; say "[@p]"; # _Dana Jacobsen, Sep 06 2015
  • Python
    from sympy.functions.combinatorial.numbers import partition
print([partition(i) for i in range(101)]) # Joan Ludevid, May 25 2025
  • Racket
    #lang racket
; SUM(k,-inf,+inf) (-1)^k p(n-k(3k-1)/2)
; For k outside the range (1-(sqrt(1-24n))/6 to (1+sqrt(1-24n))/6) argument n-k(3k-1)/2 < 0.
; Therefore the loops below are finite. The hash avoids repeated identical computations.
(define (p n) ; Nr of partitions of n.
(hash-ref h n
  (λ ()
   (define r
    (+
     (let loop ((k 1) (n (sub1 n)) (s 0))
      (if (< n 0) s
       (loop (add1 k) (- n (* 3 k) 1) (if (odd? k) (+ s (p n)) (- s (p n))))))
     (let loop ((k -1) (n (- n 2)) (s 0))
      (if (< n 0) s
       (loop (sub1 k) (+ n (* 3 k) -2) (if (odd? k) (+ s (p n)) (- s (p n))))))))
   (hash-set! h n r)
   r)))
(define h (make-hash '((0 . 1))))
; (for ((k (in-range 0 50))) (printf "~s, " (p k))) runs in a moment.
; Jos Koot, Jun 01 2016
  • Sage
    [number_of_partitions(n) for n in range(46)]  # Zerinvary Lajos, May 24 2009
  • Sage
    @CachedFunction
def A000041(n):
    if n == 0: return 1
    S = 0; J = n-1; k = 2
    while 0 <= J:
        T = A000041(J)
        S = S+T if is_odd(k//2) else S-T
        J -= k if is_odd(k) else k//2
        k += 1
    return S
[A000041(n) for n in range(50)]  # Peter Luschny, Oct 13 2012
  • Sage
    # uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(1, 0)
b = EulerTransform(a)
print([b(n) for n in range(50)]) # Peter Luschny, Nov 11 2020

Formula

G.f.: Product_{k>0} 1/(1-x^k) = Sum_{k>= 0} x^k Product_{i = 1..k} 1/(1-x^i) = 1 + Sum_{k>0} x^(k^2)/(Product_{i = 1..k} (1-x^i))^2.
G.f.: 1 + Sum_{n>=1} x^n/(Product_{k>=n} 1-x^k). - Joerg Arndt, Jan 29 2011
a(n) - a(n-1) - a(n-2) + a(n-5) + a(n-7) - a(n-12) - a(n-15) + ... = 0, where the sum is over n-k and k is a generalized pentagonal number (A001318) <= n and the sign of the k-th term is (-1)^([(k+1)/2]). See A001318 for a good way to remember this!
a(n) = (1/n) * Sum_{k=0..n-1} sigma(n-k)*a(k), where sigma(k) is the sum of divisors of k (A000203).
a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3)) as n -> infinity (Hardy and Ramanujan). See A050811.
a(n) = a(0)*b(n) + a(1)*b(n-2) + a(2)*b(n-4) + ... where b = A000009.
From Jon E. Schoenfield, Aug 17 2014: (Start)
It appears that the above approximation from Hardy and Ramanujan can be refined as
a(n) ~ 1/(4*n*sqrt(3)) * e^(Pi * sqrt(2n/3 + c0 + c1/n^(1/2) + c2/n + c3/n^(3/2) + c4/n^2 + ...)), where the coefficients c0 through c4 are approximately
c0 = -0.230420145062453320665537
c1 = -0.0178416569128570889793
c2 = 0.0051329911273
c3 = -0.0011129404
c4 = 0.0009573,
as n -> infinity. (End)
From Vaclav Kotesovec, May 29 2016 (c4 added Nov 07 2016): (Start)
c0 = -0.230420145062453320665536704197233... = -1/36 - 2/Pi^2
c1 = -0.017841656912857088979502135349949... = 1/(6*sqrt(6)*Pi) - sqrt(3/2)/Pi^3
c2 = 0.005132991127342167594576391633559... = 1/(2*Pi^4)
c3 = -0.001112940489559760908236602843497... = 3*sqrt(3/2)/(4*Pi^5) - 5/(16*sqrt(6)*Pi^3)
c4 = 0.000957343284806972958968694349196... = 1/(576*Pi^2) - 1/(24*Pi^4) + 93/(80*Pi^6)
a(n) ~ exp(Pi*sqrt(2*n/3))/(4*sqrt(3)*n) * (1 - (sqrt(3/2)/Pi + Pi/(24*sqrt(6)))/sqrt(n) + (1/16 + Pi^2/6912)/n).
a(n) ~ exp(Pi*sqrt(2*n/3) - (sqrt(3/2)/Pi + Pi/(24*sqrt(6)))/sqrt(n) + (1/24 - 3/(4*Pi^2))/n) / (4*sqrt(3)*n).
(End)
a(n) < exp( (2/3)^(1/2) Pi sqrt(n) ) (Ayoub, p. 197).
G.f.: Product_{m>=1} (1+x^m)^A001511(m). - Vladeta Jovovic, Mar 26 2004
a(n) = Sum_{i=0..n-1} P(i, n-i), where P(x, y) is the number of partitions of x into at most y parts and P(0, y)=1. - Jon Perry, Jun 16 2003
G.f.: Product_{i>=1} Product_{j>=0} (1+x^((2i-1)*2^j))^(j+1). - Jon Perry, Jun 06 2004
G.f. e^(Sum_{k>0} (x^k/(1-x^k)/k)). - Franklin T. Adams-Watters, Feb 08 2006
a(n) = A114099(9*n). - Reinhard Zumkeller, Feb 15 2006
Euler transform of all 1's sequence (A000012). Weighout transform of A001511. - Franklin T. Adams-Watters, Mar 15 2006
a(n) = A027187(n) + A027193(n) = A000701(n) + A046682(n). - Reinhard Zumkeller, Apr 22 2006
A026820(a(n),n) = A134737(n) for n > 0. - Reinhard Zumkeller, Nov 07 2007
Convolved with A152537 gives A000079, powers of 2. - Gary W. Adamson, Dec 06 2008
a(n) = A026820(n, n); a(n) = A108949(n) + A045931(n) + A108950(n) = A130780(n) + A171966(n) - A045931(n) = A045931(n) + A171967(n). - Reinhard Zumkeller, Jan 21 2010
a(n) = Tr(n)/(24*n-1) = A183011(n)/A183010(n), n>=1. See the Bruinier-Ono paper in the Links. - Omar E. Pol, Jan 23 2011
From Jerome Malenfant, Feb 14 2011: (Start)
a(n) = determinant of the n X n Toeplitz matrix:
1 -1
1 1 -1
0 1 1 -1
0 0 1 1 -1
-1 0 0 1 1 -1
. . .
d_n d_(n-1) d_(n-2)...1
where d_q = (-1)^(m+1) if q = m(3m-1)/2 = p_m, the m-th generalized pentagonal number (A001318), otherwise d_q = 0. Note that the 1's run along the diagonal and the -1's are on the superdiagonal. The (n-1) row (not written) would end with ... 1 -1. (End)
Empirical: let F*(x) = Sum_{n=0..infinity} p(n)*exp(-Pi*x*(n+1)), then F*(2/5) = 1/sqrt(5) to a precision of 13 digits.
F*(4/5) = 1/2+3/2/sqrt(5)-sqrt(1/2*(1+3/sqrt(5))) to a precision of 28 digits. These are the only values found for a/b when a/b is from F60, Farey fractions up to 60. The number for F*(4/5) is one of the real roots of 25*x^4 - 50*x^3 - 10*x^2 - 10*x + 1. Note here the exponent (n+1) compared to the standard notation with n starting at 0. - Simon Plouffe, Feb 23 2011
The constant (2^(7/8)*GAMMA(3/4))/(exp(Pi/6)*Pi^(1/4)) = 1.0000034873... when expanded in base exp(4*Pi) will give the first 52 terms of a(n), n>0, the precision needed is 300 decimal digits. - Simon Plouffe, Mar 02 2011
a(n) = A035363(2n). - Omar E. Pol, Nov 20 2009
G.f.: A(x)=1+x/(G(0)-x); G(k) = 1 + x - x^(k+1) - x*(1-x^(k+1))/G(k+1); (continued fraction Euler's kind, 1-step ). - Sergei N. Gladkovskii, Jan 25 2012
Convolution of A010815 with A000712. - Gary W. Adamson, Jul 20 2012
G.f.: 1 + x*(1 - G(0))/(1-x) where G(k) = 1 - 1/(1-x^(k+1))/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 22 2013
G.f.: Q(0) where Q(k) = 1 + x^(4*k+1)/( (x^(2*k+1)-1)^2 - x^(4*k+3)*(x^(2*k+1)-1)^2/( x^(4*k+3) + (x^(2*k+2)-1)^2/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 16 2013
a(n) = 24*spt(n) + 12*N_2(n) - Tr(n) = 24*A092269(n) + 12*A220908(n) - A183011(n), n >= 1. - Omar E. Pol, Feb 17 2013
G.f.: 1/(x; x){inf} where (a; q)_k is the q-Pochhammer symbol. - _Vladimir Reshetnikov, Apr 24 2013
a(n) = A066186(n)/n, n >= 1. - Omar E. Pol, Aug 16 2013
From Peter Bala, Dec 23 2013: (Start)
a(n-1) = Sum_{parts k in all partitions of n} mu(k), where mu(k) is the arithmetical Möbius function (see A008683).
Let P(2,n) denote the set of partitions of n into parts k >= 2. Then a(n-2) = -Sum_{parts k in all partitions in P(2,n)} mu(k).
n*( a(n) - a(n-1) ) = Sum_{parts k in all partitions in P(2,n)} k (see A138880).
Let P(3,n) denote the set of partitions of n into parts k >= 3. Then
a(n-3) = (1/2)*Sum_{parts k in all partitions in P(3,n)} phi(k), where phi(k) is the Euler totient function (see A000010). Using this result and Mertens's theorem on the average order of the phi function, we can find an approximate 3-term recurrence for the partition function: a(n) ~ a(n-1) + a(n-2) + (Pi^2/(3*n) - 1)*a(n-3). For example, substituting the values a(47) = 124754, a(48) = 147273 and a(49) = 173525 into the recurrence gives the approximation a(50) ~ 204252.48... compared with the true value a(50) = 204226. (End)
a(n) = Sum_{k=1..n+1} (-1)^(n+1-k)*A000203(k)*A002040(n+1-k). - Mircea Merca, Feb 27 2014
a(n) = A240690(n) + A240690(n+1), n >= 1. - Omar E. Pol, Mar 16 2015
From Gary W. Adamson, Jun 22 2015: (Start)
A production matrix for the sequence with offset 1 is M, an infinite n x n matrix of the following form:
a, 1, 0, 0, 0, 0, ...
b, 0, 1, 0, 0, 0, ...
c, 0, 0, 1, 0, 0, ...
d, 0, 0, 0, 1, 0, ...
.
.
... such that (a, b, c, d, ...) is the signed version of A080995 with offset 1: (1,1,0,0,-1,0,-1,...)
and a(n) is the upper left term of M^n.
This operation is equivalent to the g.f. (1 + x + 2x^2 + 3x^3 + 5x^4 + ...) = 1/(1 - x - x^2 + x^5 + x^7 - x^12 - x^15 + x^22 + ...). (End)
G.f.: x^(1/24)/eta(log(x)/(2 Pi i)). - Thomas Baruchel, Jan 09 2016, after Michael Somos (after Richard Dedekind).
a(n) = Sum_{k=-inf..+inf} (-1)^k a(n-k(3k-1)/2) with a(0)=1 and a(negative)=0. The sum can be restricted to the (finite) range from k = (1-sqrt(1-24n))/6 to (1+sqrt(1-24n))/6, since all terms outside this range are zero. - Jos Koot, Jun 01 2016
G.f.: (conjecture) (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) is A000009: (1, 1, 1, 2, 2, 3, 4, ...). - Gary W. Adamson, Sep 18 2016; Doron Zeilberger observed today that "This follows immediately from Euler's formula 1/(1-z) = (1+z)*(1+z^2)*(1+z^4)*(1+z^8)*..." Gary W. Adamson, Sep 20 2016
a(n) ~ 2*Pi * BesselI(3/2, sqrt(24*n-1)*Pi/6) / (24*n-1)^(3/4). - Vaclav Kotesovec, Jan 11 2017
G.f.: Product_{k>=1} (1 + x^k)/(1 - x^(2*k)). - Ilya Gutkovskiy, Jan 23 2018
a(n) = p(1, n) where p(k, n) = p(k+1, n) + p(k, n-k) if k < n, 1 if k = n, and 0 if k > n. p(k, n) is the number of partitions of n into parts >= k. - Lorraine Lee, Jan 28 2020
Sum_{n>=1} 1/a(n) = A078506. - Amiram Eldar, Nov 01 2020
Sum_{n>=0} a(n)/2^n = A065446. - Amiram Eldar, Jan 19 2021
From Simon Plouffe, Mar 12 2021: (Start)
Sum_{n>=0} a(n)/exp(Pi*n) = 2^(3/8)*Gamma(3/4)/(Pi^(1/4)*exp(Pi/24)).
Sum_{n>=0} a(n)/exp(2*Pi*n) = 2^(1/2)*Gamma(3/4)/(Pi^(1/4)*exp(Pi/12)).
[corrected by Vaclav Kotesovec, May 12 2023] (End)
[These are the reciprocals of phi(exp(-Pi)) (A259148) and phi(exp(-2*Pi)) (A259149), where phi(q) is the Euler modular function. See B. C. Berndt (RLN, Vol. V, p. 326), and formulas (13) and (14) in I. Mező, 2013. - Peter Luschny, Mar 13 2021]
a(n) = A000009(n) + A035363(n) + A006477(n). - R. J. Mathar, Feb 01 2022
a(n) = A008284(2*n,n) is also the number of partitions of 2n into n parts. - Ryan Brooks, Jun 11 2022
a(n) = A000700(n) + A330644(n). - R. J. Mathar, Jun 15 2022
a(n) ~ exp(Pi*sqrt(2*n/3)) / (4*n*sqrt(3)) * (1 + Sum_{r>=1} w(r)/n^(r/2)), where w(r) = 1/(-4*sqrt(6))^r * Sum_{k=0..(r+1)/2} binomial(r+1,k) * (r+1-k) / (r+1-2*k)! * (Pi/6)^(r-2*k) [Cormac O'Sullivan, 2023, pp. 2-3]. - Vaclav Kotesovec, Mar 15 2023

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

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.

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Partitions into distinct parts are sometimes called "strict partitions".
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 A047993. - 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
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]
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

Examples

			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)

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, Ramanujan: twelve lectures on subjects suggested by his life and work, Cambridge, University Press, 1940, p. 86.
  • 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).
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 288-290.

Links

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

Programs

  • 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
  • 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
  • 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
  • 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
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
lim := 99; # Enlarge if more terms are needed.
simplify(expand(QDifferenceEquations:-QPochhammer(-1, x, lim)/2, x)):
seq(coeff(%, x, n), n=0..55); # Peter Luschny, Nov 17 2016
# Alternative:
a:= proc(n) option remember; `if`(n=0, 1, add(a(n-j)*add(
     `if`(d::odd, d, 0), d=numtheory[divisors](j)), j=1..n)/n)
    end:
seq(a(n), n=0..55);  # Alois P. Heinz, Jun 24 2025
  • 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 *)
  • 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 nVladimir Kruchinin, Sep 07 2014 */
  • 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
  • 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
  • Python
    import numpy as np
n = 1000
arr = np.zeros(n,dtype=object)
arr[0] = 1
for i in range(1,n):
    arr[i:] += arr[:n-i]
print(arr) # Yigit Oktar, Jul 12 2025
  • 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

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

A010054 a(n) = 1 if n is a triangular number, otherwise 0.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This is essentially the q-expansion of the Jacobi theta function theta_2(q). (In theta_2 one has to ignore the initial factor of 2*q^(1/4) and then replace q by q^(1/2). See also A005369.) - N. J. A. Sloane, Aug 03 2014
Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).
Ramanujan's theta function f(a, b) = Sum_{n=-inf..inf} a^(n*(n+1)/2) * b^(n*(n-1)/2).
This sequence is the concatenation of the base-b digits in the sequence b^n, for any base b >= 2. - Davis Herring (herring(AT)lanl.gov), Nov 16 2004
Number of partitions of n into distinct parts such that the greatest part equals the number of all parts, see also A047993; a(n)=A117195(n,0) for n > 0; a(n) = 1-A117195(n,1) for n > 1. - Reinhard Zumkeller, Mar 03 2006
Triangle T(n,k), 0 <= k <= n, read by rows, given by A000007 DELTA A000004 where DELTA is the operator defined in A084938. - Philippe Deléham, Jan 03 2009
Convolved with A000041 = A022567, the convolution square of A000009. - Gary W. Adamson, Jun 11 2009
A008441(n) = Sum_{k=0..n} a(k)*a(n-k). - Reinhard Zumkeller, Nov 03 2009
Polcoeff inverse with alternate signs = A006950: (1, 1, 1, 2, 3, 4, 5, 7, ...). - Gary W. Adamson, Mar 15 2010
This sequence is related to Ramanujan's two-variable theta functions because this sequence is also the characteristic function of generalized hexagonal numbers. - Omar E. Pol, Jun 08 2012
Number 3 of the 14 primitive eta-products which are holomorphic modular forms of weight 1/2 listed by D. Zagier on page 30 of "The 1-2-3 of Modular Forms". - Michael Somos, May 04 2016
Number of partitions of n into consecutive parts that contain 1 as a part, n >= 1. - Omar E. Pol, Nov 27 2020
The constant whose decimal expansion is this sequence is irrational (Mahler, 1981). The constant whose expansion in any base b >= 2 is this sequence is irrational (Bundschuh, 1984). - Amiram Eldar, Mar 23 2025

Examples

			G.f. = 1 + x + x^3 + x^6 + x^10 + x^15 + x^21 + x^28 + x^36 + x^45 + x^55 + x^66 + ...
G.f. for B(q) = q * A(q^8): q + q^9 + q^25 + q^49 + q^81 + q^121 + q^169 + q^225 + q^289 + q^361 + ...
From _Philippe Deléham_, Jan 04 2008: (Start)
As a triangle this begins:
  1;
  1, 0;
  1, 0, 0;
  1, 0, 0, 0;
  1, 0, 0, 0, 0;
  1, 0, 0, 0, 0, 0;
  ...  (End)

References

  • J. H. Conway and N. J. A. Sloane, Sphere Packings, Lattices and Groups, Springer-Verlag, 1999, p. 103.
  • Michael D. Hirschhorn, The Power of q, Springer, 2017. See Psi, page 9.
  • Jules Tannery and Jules Molk, Eléments de la Théorie des Fonctions Elliptiques, Vol. 2, Gauthier-Villars, Paris, 1902; Chelsea, NY, 1972, see p. 27.
  • Edmund T. Whittaker and George N. Watson, A Course of Modern Analysis, Cambridge Univ. Press, 4th ed., 1963, p. 464.

Links

Crossrefs

Cf. A000217, A002448, A005369, A023531, A035214, A022567, A052343, A006950, A106459, A127648.
Number of ways of writing n as a sum of k triangular numbers, for k=1,...: A010054, A008441, A008443, A008438, A008439, A008440, A226252, A007331, A226253, A226254, A226255, A014787, A014809.
Cf. A106507 (reciprocal series).

Programs

  • Clojure
    (def A010054 (mapcat #(cons 1 (replicate % 0)) (range))) ; Tony Zorman, Apr 03 2023
  • Haskell
    a010054 = a010052 . (+ 1) . (* 8)
a010054_list = concatMap (\x -> 1 : replicate x 0) [0..]
-- Reinhard Zumkeller, Feb 12 2012, Oct 22 2011, Apr 02 2011
  • Magma
    Basis( ModularForms( Gamma0(16), 1/2), 362) [2] ; /* Michael Somos, Jun 10 2014 */
  • Maple
    A010054 := proc(n)
    if issqr(1+8*n) then
        1;
    else
        0;
    end if;
end proc:
seq(A010054(n),n=0..80) ; # R. J. Mathar, Feb 22 2021
  • Mathematica
    a[ n_] := SquaresR[ 1, 8 n + 1] / 2; (* Michael Somos, Nov 15 2011 *)
a[ n_] := If[ n < 0, 0, SeriesCoefficient[ (Series[ EllipticTheta[ 3, Log[y] / (2 I), x^2], {x, 0, n + Floor @ Sqrt[n]}] // Normal // TrigToExp) /. {y -> x}, {x, 0, n}]]; (* Michael Somos, Nov 15 2011 *)
Table[If[IntegerQ[(Sqrt[8n+1]-1)/2],1,0],{n,0,110}] (* Harvey P. Dale, Oct 29 2012 *)
a[ n_] := SeriesCoefficient[ EllipticTheta[ 2, 0, q^(1/2)] / (2 q^(1/8)), {q, 0, n}]; (* Michael Somos, Jul 01 2014 *)
Module[{tr=Accumulate[Range[20]]},If[MemberQ[tr,#],1,0]&/@Range[Max[tr]]] (* Harvey P. Dale, Mar 13 2023 *)
  • PARI
    {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^2 + A)^2 / eta(x + A), n))}; /* Michael Somos, Mar 14 2011 */
  • PARI
    {a(n) = issquare( 8*n + 1)}; /* Michael Somos, Apr 27 2000 */
  • PARI
    a(n) = ispolygonal(n, 3); \\ Michel Marcus, Jan 22 2015
  • Python
    from sympy import integer_nthroot
def A010054(n): return int(integer_nthroot((n<<3)+1,2)[1]) # Chai Wah Wu, Nov 15 2022
  • Sage
    # uses[EulerTransform from A166861]
b = BinaryRecurrenceSequence(-1, 0)
a = EulerTransform(b)
print([a(n) for n in range(88)]) # Peter Luschny, Nov 17 2022

Formula

Expansion of f(x, x^3) in powers of x where f(, ) is Ramanujan's general theta function.
Expansion of q^(-1) * (phi(q) - phi(q^4)) / 2 in powers of q^8. - Michael Somos, Jul 01 2014
Expansion of q^(-1/8) * eta(q^2)^2 / eta(q) in powers of q. - Michael Somos, Apr 13 2005
Euler transform of period 2 sequence [ 1, -1, ...]. - Michael Somos, Mar 24 2003
Given g.f. A(x), then B(q) = q * A(q^8) satisfies 0 = f(B(q), B(q^2), B(q^3), B(q^6)) where f(u1, u2, u3, u6) = u1*u6^3 + u2*u3^3 - u1*u2^2*u6. - Michael Somos, Apr 13 2005
a(n) = b(8*n + 1) where b()=A098108() is multiplicative with b(2^e) = 0^e, b(p^e) = (1 + (-1)^e) / 2 if p > 2. - Michael Somos, Jun 06 2005
a(n) = A005369(2*n). - Michael Somos, Apr 29 2003
G.f.: theta_2(sqrt(q)) / (2 * q^(1/8)).
G.f.: 1 / (1 - x / (1 + x / (1 + x^1 / (1 - x / (1 + x / (1 + x^2 / (1 - x / (1 + x / (1 + x^3 / ...))))))))). - Michael Somos, May 11 2012
G.f.: Product_{k>0} (1-x^(2*k))/(1-x^(2*k-1)). - Vladeta Jovovic, May 02 2002
a(0)=1; for n>0, a(n) = A002024(n+1)-A002024(n). - Benoit Cloitre, Jan 05 2004
G.f.: Sum_{j>=0} Product_{k=0..j} x^j. - Jon Perry, Mar 30 2004
a(n) = floor((1-cos(Pi*sqrt(8*n+1)))/2). - Carl R. White, Mar 18 2006
a(n) = round(sqrt(2n+1)) - round(sqrt(2n)). - Hieronymus Fischer, Aug 06 2007
a(n) = ceiling(2*sqrt(2n+1)) - floor(2*sqrt(2n)) - 1. - Hieronymus Fischer, Aug 06 2007
a(n) = f(n,0) with f(x,y) = if x > 0 then f(x-y,y+1), otherwise 0^(-x). - Reinhard Zumkeller, Sep 27 2008
a(n) = A035214(n) - 1.
From Mikael Aaltonen, Jan 22 2015: (Start)
Since the characteristic function of s-gonal numbers is given by floor(sqrt(2n/(s-2) + ((s-4)/(2s-4))^2) + (s-4)/(2s-4)) - floor(sqrt(2(n-1)/(s-2) + ((s-4)/(2s-4))^2) + (s-4)/(2s-4)), by setting s = 3 we get the following: For n > 0, a(n) = floor(sqrt(2*n+1/4)-1/2) - floor(sqrt(2*(n-1)+1/4)-1/2).
(End)
a(n) = (-1)^n * A106459(n). - Michael Somos, May 04 2016
G.f. is a period 1 Fourier series which satisfies f(-1 / (16 t)) = 2^(-1/2) (t/i)^(1/2) g(t) where q = exp(2 Pi i t) and g() is the g.f. for A002448. - Michael Somos, May 05 2016
G.f.: Sum_{n >= 0} x^(n*(n+1)/2) = Product_{n >= 1} (1 - x^n)*(1 + x^n)^2 = Product_{n >= 1} (1 - x^(2*n))*(1 + x^n) = Product_{n >= 1} (1 - x^(2*n))/(1 - x^(2*n-1)). From the sum and product representations of theta_2(0, sqrt(q))/(2*q^(1/8)) function. The last product, given by Vladeta Jovovic above, is obtained from the second to last one by an Euler identity, proved via f(x) := Product_{n >= 1} (1 - x^(2*n-1))*Product_{n >= 1} (1 + x^n) = f(x^2), by moving the odd-indexed factors of the second product to the first product. This leads to f(x) = f(0) = 1. - Wolfdieter Lang, Jul 05 2016
a(0) = 1, a(n) = (1/n)*Sum_{k=1..n} A002129(k)*a(n-k) for n > 0. - Seiichi Manyama, Apr 08 2017
G.f.: Sum_{n >= 0} x^n * Product_{k >= n+1} (1 - x^(2*k)) = 1/(1 - x) * Sum_{n >= 0} x^(3*n) * Product_{k >= n+1} (1 - x^(2*k)) = 1/((1 - x)*(1 - x^3)) * Sum_{n >= 0} x^(5*n) * Product_{k >= n+1} (1 - x^(2*k)) = .... - Peter Bala, Jun 24 2025

Extensions

Additional comments from Michael Somos, Apr 27 2000

A000219 Number of plane partitions (or planar partitions) of n.

Original entry on oeis.org

1, 1, 3, 6, 13, 24, 48, 86, 160, 282, 500, 859, 1479, 2485, 4167, 6879, 11297, 18334, 29601, 47330, 75278, 118794, 186475, 290783, 451194, 696033, 1068745, 1632658, 2483234, 3759612, 5668963, 8512309, 12733429, 18974973, 28175955, 41691046, 61484961, 90379784, 132441995, 193487501, 281846923
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Two-dimensional partitions of n in which no row or column is longer than the one before it (compare A001970). E.g., a(4) = 13:
4.31.3.22.2.211.21..2.1111.111.11.11.1 but not 2
.....1....2.....1...1......1...11.1..1........ 11
....................1.............1..1
.....................................1
In the above, one also must require that rows & columns are nondecreasing, e.g., [1,1; 2] is also forbidden (which implies that row and column lengths are nondecreasing, if empty cells are identified with cells filled with 0's). - M. F. Hasler, Sep 22 2018
Can also be regarded as number of "safe pilings" of cubes in the corner of a room: the height should not increase away from the corner. - Wouter Meeussen
Also number of partitions of n objects of 2 colors, each part containing at least one black object; see example. - Christian G. Bower, Jan 08 2004
Number of partitions of n into 1 type of part 1, 2 types of part 2, ..., k types of part k. E.g., n=3 gives 111, 12, 12', 3, 3', 3''. - Jon Perry, May 27 2004
The bijection between the partitions in the two preceding comments goes by identifying a part with k black objects with a part of type k. - David Scambler and Joerg Arndt, May 01 2013
Can also be regarded as the number of Jordan canonical forms for an n X n matrix. (I.e., a 5 X 5 matrix has 24 distinct Jordan canonical forms, dependent on the algebraic and geometric multiplicity of each eigenvalue.) - Aaron Gable (agable(AT)hmc.edu), May 26 2009
(1/n) * convolution product of n terms * A001157 (sum of squares of divisors of n): (1, 5, 10, 21, 26, 50, 50, 85, ...) = a(n). As shown by [Bressoud, p. 12]: 1/6 * [1*24 + 5*13 + 10*6 + 21*3 + 26*1 + 50*1] = 288/6 = 48. - Gary W. Adamson, Jun 13 2009
Convolved with the aerated version (1, 0, 1, 0, 3, 0, 6, 0, 13, ...) = A026007: (1, 1, 2, 5, 8, 16, 28, 49, 83, ...). - Gary W. Adamson, Jun 13 2009
Starting with offset 1 = row sums of triangle A162453. - Gary W. Adamson, Jul 03 2009
Unfortunately, Wright's formula is also incomplete in the paper by G. Almkvist: "Asymptotic formulas and generalized Dedekind sums", p. 344, (the denominator should have sqrt(3*Pi) not sqrt(Pi)). This error was already corrected in the paper by Steven Finch: "Integer Partitions". - Vaclav Kotesovec, Aug 17 2015
Also the number of non-isomorphic weight-n chains of multisets whose dual is also a chain of multisets. The dual of a multiset partition has, for each vertex, one block consisting of the indices (or positions) of the blocks containing that vertex, counted with multiplicity. The weight of a multiset partition is the sum of sizes of its parts. - Gus Wiseman, Sep 25 2018

Examples

			A planar partition of 13:
  4 3 1 1
  2 1
  1
a(5) = (1/5!)*(sigma_2(1)^5+10*sigma_2(2)*sigma_2(1)^3+20*sigma_2(3)*sigma_2(1)^2+ 15*sigma_2(1)*sigma_2(2)^2+30*sigma_2(4)*sigma_2(1)+20*sigma_2(2)*sigma_2(3)+24*sigma_2(5)) = 24. - _Vladeta Jovovic_, Jan 10 2003
From _David Scambler_ and _Joerg Arndt_, May 01 2013: (Start)
There are a(4) = 13 partitions of 4 objects of 2 colors ('b' and 'w'), each part containing at least one black object:
1 black part:
  [ bwww ]
2 black parts:
  [ bbww ]
  [ bww, b ]
  [ bw, bw ]
3 black parts:
  [ bbbw ]
  [ bbw, b ]
  [ bb, bw ]
(but not: [bw, bb ] )
  [ bw, b, b ]
4 black parts:
  [ bbbb ]
  [ bbb, b ]
  [ bb, bb ]
  [ bb, b, b ]
  [ b, b, b, b ]
(End)
From _Geoffrey Critzer_, Nov 29 2014: (Start)
The corresponding partitions of the integer 4 are:
  4'''
  4''
  3'' + 1
  2' + 2'
  4'
  3' + 1
  2 + 2'
  2' + 1 + 1
  4
  3 + 1
  2 + 2
  2 + 1 + 1
  1 + 1 + 1 + 1.
(End)
From _Gus Wiseman_, Sep 25 2018: (Start)
Non-isomorphic representatives of the a(4) = 13 chains of multisets whose dual is also a chain of multisets:
  {{1,1,1,1}}
  {{1,1,2,2}}
  {{1,2,2,2}}
  {{1,2,3,3}}
  {{1,2,3,4}}
  {{1},{1,1,1}}
  {{2},{1,2,2}}
  {{3},{1,2,3}}
  {{1,1},{1,1}}
  {{1,2},{1,2}}
  {{1},{1},{1,1}}
  {{2},{2},{1,2}}
  {{1},{1},{1},{1}}
(End)
G.f. = 1 + x + 3*x^2 + 6*x^3 + 13*x^4 + 24*x^5 + 48*x^6 + 86*x^7 + 160*x^8 + ...

References

  • G. Almkvist, The differences of the number of plane partitions, Manuscript, circa 1991.
  • G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976, p. 241.
  • D. M. Bressoud, Proofs and Confirmations, Camb. Univ. Press, 1999; pp(n) on p. 10.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 575.
  • L. Carlitz, Generating functions and partition problems, pp. 144-169 of A. L. Whiteman, ed., Theory of Numbers, Proc. Sympos. Pure Math., 8 (1965). Amer. Math. Soc., see p. 145, eq. (1.6).
  • I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, Wiley, N.Y., 1983, (5.4.5).
  • P. A. MacMahon, Memoir on the theory of partitions of numbers - Part VI, Phil. Trans. Royal Soc., 211 (1912), 345-373.
  • P. A. MacMahon, Combinatory Analysis. Cambridge Univ. Press, London and New York, Vol. 1, 1915 and Vol. 2, 1916; see vol. 2, p 332.
  • P. A. MacMahon, The connexion between the sum of the squares of the divisors and the number of partitions of a given number, Messenger Math., 54 (1924), 113-116. Collected Papers, MIT Press, 1978, Vol. I, pp. 1364-1367. See Table II. - N. J. A. Sloane, May 21 2014
  • 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

Crossrefs

Cf. A000784, A000785, A000786, A005380, A005987, A048141, A048142, A089300.
Cf. A023871-A023878, A026007, A001157, A162453, A285216.
Differences: A191659, A191660, A191661.
Row sums of A089353 and A091438 and A091298.
Column k=1 of A144048. - Alois P. Heinz, Nov 02 2012
Sequences "number of r-line partitions": A000041 (r=1), A000990 (r=2), A000991 (r=3), A002799 (r=4), A001452 (r=5), A225196 (r=6), A225197 (r=7), A225198 (r=8), A225199 (r=9).
Cf. A249386, A249387.
Cf. A161870, A255610, A255611, A255612, A255613, A255614, A193427.

Programs

  • Julia
    using Nemo, Memoize
@memoize function a(n)
    if n == 0 return 1 end
    s = sum(a(n - j) * divisor_sigma(j, 2) for j in 1:n)
    return div(s, n)
end
[a(n) for n in 0:20] # Peter Luschny, May 03 2020
  • Maple
    series(mul((1-x^k)^(-k),k=1..64),x,63);
# second Maple program:
a:= proc(n) option remember; `if`(n=0, 1, add(
      a(n-j)*numtheory[sigma][2](j), j=1..n)/n)
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Aug 17 2015
  • Mathematica
    CoefficientList[Series[Product[(1 - x^k)^-k, {k, 64}], {x, 0, 64}], x]
Zeta[3]^(7/36)/2^(11/36)/Sqrt[3 Pi]/Glaisher E^(3 Zeta[3]^(1/3) (n/2)^(2/3) + 1/12)/n^(25/36) (* asymptotic formula after Wright; Vaclav Kotesovec, Jun 23 2014 *)
a[0] = 1; a[n_] := a[n] = Sum[a[n - j] DivisorSigma[2, j], {j, n}]/n; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Sep 21 2015, after Alois P. Heinz *)
CoefficientList[Series[Exp[Sum[DivisorSigma[2, n] x^n/n, {n, 50}]], {x, 0, 50}], x] (* Eric W. Weisstein, Feb 01 2018 *)
  • PARI
    {a(n) = if( n<0, 0, polcoeff( exp( sum( k=1, n, x^k / (1 - x^k)^2 / k, x * O(x^n))), n))}; /* Michael Somos, Jan 29 2005 */
  • PARI
    {a(n) = if( n<0, 0, polcoeff( prod( k=1, n, (1 - x^k + x * O(x^n))^-k), n))}; /* Michael Somos, Jan 29 2005 */
  • PARI
    my(N=66, x='x+O('x^N)); Vec( prod(n=1,N, (1-x^n)^-n) ) \\ Joerg Arndt, Mar 25 2014
  • PARI
    A000219(n)=#PlanePartitions(n) \\ See A091298 for PlanePartitions(). For illustrative use: much slower than the above. - M. F. Hasler, Sep 24 2018
  • Python
    from sympy import cacheit
from sympy.ntheory import divisor_sigma
@cacheit
def A000219(n):
    if n <= 1:
        return 1
    return sum(A000219(n - k) * divisor_sigma(k, 2) for k in range(1, n + 1)) // n
print([A000219(n) for n in range(20)])
# R. J. Mathar, Oct 18 2009
  • SageMath
    # uses[EulerTransform from A166861]
b = EulerTransform(lambda n: n)
print([b(n) for n in range(37)]) # Peter Luschny, Nov 11 2020

Formula

G.f.: Product_{k >= 1} 1/(1 - x^k)^k. - MacMahon, 1912.
Euler transform of sequence [1, 2, 3, ...].
a(n) ~ (c_2 / n^(25/36)) * exp( c_1 * n^(2/3) ), where c_1 = A249387 = 2.00945... and c_2 = A249386 = 0.23151... - Wright, 1931. Corrected Jun 01 2010 by Rod Canfield - see Mutafchiev and Kamenov. The exact value of c_2 is e^(2c)*2^(-11/36)*zeta(3)^(7/36)*(3*Pi)^(-1/2), where c = Integral_{y=0..inf} (y*log(y)/(e^(2*Pi*y)-1))dy = (1/2)*zeta'(-1).
The exact value of c_1 is 3*2^(-2/3)*Zeta(3)^(1/3) = 2.0094456608770137530649... - Vaclav Kotesovec, Sep 14 2014
a(n) = (1/n) * Sum_{k=1..n} a(n-k)*sigma_2(k), n > 0, a(0)=1, where sigma_2(n) = A001157(n) = sum of squares of divisors of n. - Vladeta Jovovic, Jan 20 2002
G.f.: exp(Sum_{n>0} sigma_2(n)*x^n/n). a(n) = Sum_{pi} Product_{i=1..n} binomial(k(i)+i-1, k(i)) where pi runs through all nonnegative solutions of k(1)+2*k(2)+..+n*k(n)=n. - Vladeta Jovovic, Jan 10 2003
From Vaclav Kotesovec, Nov 07 2016: (Start)
More precise asymptotics: a(n) ~ Zeta(3)^(7/36) * exp(3 * Zeta(3)^(1/3) * (n/2)^(2/3) + 1/12) / (A * sqrt(3*Pi) * 2^(11/36) * n^(25/36))
* (1 + c1/n^(2/3) + c2/n^(4/3) + c3/n^2), where
c1 = -0.23994424421250649114273759... = -277/(864*(2*Zeta(3))^(1/3)) - Zeta(3)^(2/3)/(1440*2^(1/3))
c2 = -0.02576771365117401620018082... = 353*Zeta(3)^(1/3)/(248832*2^(2/3)) - 17*Zeta(3)^(4/3)/(3225600*2^(2/3)) - 71575/(1492992*(2*Zeta(3))^(2/3))
c3 = -0.00533195302658826100834286... = -629557/859963392 - 42944125/(7739670528*Zeta(3)) + 14977*Zeta(3)/1114767360 - 22567*Zeta(3)^2/250822656000
and A = A074962 is the Glaisher-Kinkelin constant.
(End)

Extensions

Corrected by N. J. A. Sloane, Jul 29 2006
Minor edits by Vaclav Kotesovec, Oct 27 2014

A001970 Functional determinants; partitions of partitions; Euler transform applied twice to all 1's sequence.

Original entry on oeis.org

1, 1, 3, 6, 14, 27, 58, 111, 223, 424, 817, 1527, 2870, 5279, 9710, 17622, 31877, 57100, 101887, 180406, 318106, 557453, 972796, 1688797, 2920123, 5026410, 8619551, 14722230, 25057499, 42494975, 71832114, 121024876, 203286806, 340435588, 568496753, 946695386
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) = number of partitions of n, when for each k there are p(k) different copies of part k. E.g., let the parts be 1, 2a, 2b, 3a, 3b, 3c, 4a, 4b, 4c, 4d, 4e, ... Then the a(4) = 14 partitions of 4 are: 4 = 4a = 4b = ... = 4e = 3a+1 = 3b+1 = 3c+1 = 2a+2a = 2a+2b = 2b+2b = 2a+1 = 2b+1 = 1+1+1+1.
Equivalently (Cayley), a(n) = number of 2-dimensional partitions of n. E.g., for n = 4 we have:
4 31 3 22 2 211 21 2 2 1111 111 11 11 1
1 2 1 11 1 1 11 1 1
1 1 1
1
Also total number of different species of singularity for conjugate functions with n letters (Sylvester).
According to [Belmans], this sequence gives "[t]he number of Segre symbols for the intersection of two quadrics in a fixed dimension". - Eric M. Schmidt, Sep 02 2017
From Gus Wiseman, Jul 30 2022: (Start)
Also the number of non-isomorphic multiset partitions of weight n with all constant blocks. The strict case is A089259. For example, non-isomorphic representatives of the a(1) = 1 through a(3) = 6 multiset partitions are:
{{1}} {{1,1}} {{1,1,1}}
{{1},{1}} {{1},{1,1}}
{{1},{2}} {{1},{2,2}}
{{1},{1},{1}}
{{1},{2},{2}}
{{1},{2},{3}}
A000688 counts factorizations into prime powers.
A007716 counts non-isomorphic multiset partitions by weight.
A279784 counts twice-partitions of type PPR, factorizations A295935.
Constant partitions are ranked by prime-powers: A000961, A023894, A054685, A246655, A355743.
(End)

Examples

			G.f. = 1 + x + 3*x^2 + 6*x^3 + 15*x^4 + 28*x^5 + 66*x^6 + 122*x^7 + ...
a(3) = 6 because we have (111) = (111) = (11)(1) = (1)(1)(1), (12) = (12) = (1)(2), (3) = (3).
The a(4)=14 multiset partitions whose total sum of parts is 4 are:
((4)),
((13)), ((1)(3)),
((22)), ((2)(2)),
((112)), ((1)(12)), ((2)(11)), ((1)(1)(2)),
((1111)), ((1)(111)), ((11)(11)), ((1)(1)(11)), ((1)(1)(1)(1)). - _Gus Wiseman_, Dec 19 2016

References

  • A. Cayley, Recherches sur les matrices dont les termes sont des fonctions linéaires d'une seule indéterminée, J. Reine angew. Math., 50 (1855), 313-317; Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 2, p. 219.
  • V. A. Liskovets, Counting rooted initially connected directed graphs. Vesci Akad. Nauk. BSSR, ser. fiz.-mat., No 5, 23-32 (1969), MR44 #3927.
  • 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).
  • J. J. Sylvester, An Enumeration of the Contacts of Lines and Surfaces of the Second Order, Phil. Mag. 1 (1851), 119-140. Reprinted in Collected Papers, Vol. 1. See p. 239, where one finds a(n)-2, but with errors.
  • J. J. Sylvester, Note on the 'Enumeration of the Contacts of Lines and Surfaces of the Second Order', Phil. Mag., Vol. VII (1854), pp. 331-334. Reprinted in Collected Papers, Vol. 2, pp. 30-33.

Links

Crossrefs

Related to A001383 via generating function.
The multiplicative version (factorizations) is A050336.
The ordered version (sequences of partitions) is A055887.
Row-sums of A061260.
Main diagonal of A055885.
We have A271619(n) <= a(n) <= A063834(n).
Column k=3 of A290353.
The strict case is A316980.
Cf. A000041, A061259, A006171, A061255, A061256, A061257, A089292, A000219.
Cf. A089300.
Cf. A001055, A072233, A112798, A275024.

Programs

  • Haskell
    Following Vladeta Jovovic:
a001970 n = a001970_list !! (n-1)
a001970_list = 1 : f 1 [1] where
   f x ys = y : f (x + 1) (y : ys) where
            y = sum (zipWith (*) ys a061259_list) `div` x
-- Reinhard Zumkeller, Oct 31 2015
  • Maple
    with(combstruct); SetSetSetU := [T, {T=Set(S), S=Set(U,card >= 1), U=Set(Z,card >=1)},unlabeled];
# second Maple program:
with(numtheory): with(combinat):
a:= proc(n) option remember; `if`(n=0, 1, add(add(d*
      numbpart(d), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..35);  # Alois P. Heinz, Dec 19 2016
  • Mathematica
    m = 32; f[x_] = Product[1/(1-x^k)^PartitionsP[k], {k, 1, m}]; CoefficientList[ Series[f[x], {x, 0, m-1}], x] (* Jean-François Alcover, Jul 19 2011, after g.f. *)
  • PARI
    {a(n) = if( n<0, 0, polcoeff( 1 / prod(k=1, n, 1 - numbpart(k) * x^k + x * O(x^n)), n))}; /* Michael Somos, Dec 20 2016 */
  • Python
    from sympy.core.cache import cacheit
from sympy import npartitions, divisors
@cacheit
def a(n): return 1 if n == 0 else sum([sum([d*npartitions(d) for d in divisors(j)])*a(n - j) for j in range(1, n + 1)]) / n
[a(n) for n in range(51)]  # Indranil Ghosh, Aug 19 2017, after Maple code
# (Sage) # uses[EulerTransform from A166861]
b = BinaryRecurrenceSequence(0, 1, 1)
a = EulerTransform(EulerTransform(b))
print([a(n) for n in range(36)]) # Peter Luschny, Nov 17 2022

Formula

G.f.: Product_{k >= 1} 1/(1-x^k)^p(k), where p(k) = number of partitions of k = A000041. [Cayley]
a(n) = (1/n)*Sum_{k = 1..n} a(n-k)*b(k), n > 1, a(0) = 1, b(k) = Sum_{d|k} d*numbpart(d), where numbpart(d) = number of partitions of d, cf. A061259. - Vladeta Jovovic, Apr 21 2001
Logarithmic derivative yields A061259 (equivalent to above formula from Vladeta Jovovic). - Paul D. Hanna, Sep 05 2012
a(n) = Sum_{k=1..A000041(n)} A001055(A215366(n,k)) = number of factorizations of Heinz numbers of integer partitions of n. - Gus Wiseman, Dec 19 2016
a(n) = |{m>=1 : n = Sum_{k=1..A001222(m)} A056239(A112798(m,k)+1)}| = number of normalized twice-prime-factored multiset partitions (see A275024) whose total sum of parts is n. - Gus Wiseman, Dec 19 2016

Extensions

Additional comments from Valery A. Liskovets
Sylvester references from Barry Cipra, Oct 07 2003

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

Original entry on oeis.org

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
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The over-partition function.
Ramanujan theta functions: f(q) (see A121373), phi(q) (A000122), psi(q) (A010054), chi(q) (A000700).
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
Convolution of A000041 and A000009. - Vladeta Jovovic, Nov 26 2002
Equals A022567 convolved with A035363. - Gary W. Adamson, Jun 09 2009
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
Equals A182818 convolved with A010815. - Gary W. Adamson, Jul 20 2012
Partial sums of A211971. - Omar E. Pol, Jan 09 2014
Also 1 together with the row sums of A235790. - Omar E. Pol, Jan 19 2014
Antidiagonal sums of A284592. - Peter Bala, Mar 30 2017
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

Examples

			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

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

Crossrefs

Cf. A022567, A035363, A002448, A106507, A156616, A261386, A265835, A014968, A284592, A303662.
See A004402 for a version with signs.
Column k=2 of A321884.
Cf. A002513.

Programs

  • Julia
    # JacobiTheta4 is defined in A002448.
A015128List(len) = JacobiTheta4(len, -1)
A015128List(40) |> println # Peter Luschny, Mar 12 2018
  • 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):
seq(a(n), n=0..40);  # Alois P. Heinz, Feb 10 2014
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 *)
QP = QPochhammer; s = QP[q^2]/QP[q]^2 + O[q]^40; CoefficientList[s + O[q]^100, q] (* Jean-François Alcover, Nov 25 2015, after Michael Somos *)
Table[Sum[PartitionsP[n-k]*PartitionsQ[k], {k, 0, n}], {n, 0, 50}] (* Vaclav Kotesovec, Nov 28 2015 *)
(QPochhammer[-x, x]/QPochhammer[x, x] + O[x]^50)[[3]] (* Vladimir Reshetnikov, Nov 12 2016 *)
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 *)
  • 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
  • SageMath
    # uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(0, 1, 1, 2)
b = EulerTransform(a)
print([b(n) for n in range(40)]) # Peter Luschny, Nov 11 2020

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
A004402(n) = (-1)^n * a(n). - Michael Somos, Mar 17 2003
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
Convolution inverse of A002448. - 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.: Product_{i>=1} (1 + x^i)^A001511(2i) (see A000041). - Jon Perry, Jun 06 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) = 2*A014968(n), n >= 1. - Omar E. Pol, Jan 19 2014
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
For n >= 1, a(n) = Sum_{k>=1} 2^k * A116608(n,k). - Gregory L. Simay, Jun 01 2019
Sum_{n>=1} 1/a(n) = A303662. - Amiram Eldar, Nov 15 2020
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

Extensions

Minor edits by Vaclav Kotesovec, Sep 13 2014

A000712 Generating function = Product_{m>=1} 1/(1 - x^m)^2; a(n) = number of partitions of n into parts of 2 kinds.

Original entry on oeis.org

1, 2, 5, 10, 20, 36, 65, 110, 185, 300, 481, 752, 1165, 1770, 2665, 3956, 5822, 8470, 12230, 17490, 24842, 35002, 49010, 68150, 94235, 129512, 177087, 240840, 326015, 439190, 589128, 786814, 1046705, 1386930, 1831065, 2408658, 3157789, 4126070, 5374390
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n >= 1, a(n) is also the number of conjugacy classes in the automorphism group of the n-dimensional hypercube. This automorphism group is the wreath product of the cyclic group C_2 and the symmetric group S_n, its order is in sequence A000165. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Nov 04 2001
Also, number of noncongruent matrices in GL_n(Z): each Jordan block can only have +1 or -1 on the diagonal. - Michele Dondi (blazar(AT)lcm.mi.infn.it), Jun 15 2004
a(n) = Sum (k(1)+1)*(k(2)+1)*...*(k(n)+1), where the sum is taken over all (k(1),k(2),...,k(n)) such that k(1)+2*k(2)+...+n*k(n) = n, k(i)>=0, i=1..n, cf. A104510, A077285. - Vladeta Jovovic, Apr 21 2005
Convolution of partition numbers (A000041) with itself. - Graeme McRae, Jun 07 2006
Number of one-to-one partial endofunctions on n unlabeled points. Connected components are either cycles or "lines", hence two for each size. - Franklin T. Adams-Watters, Dec 28 2006
Equals A000716: (1, 3, 9, 22, 561, 108, ...) convolved with A010815. A000716 = the number of partitions of n into parts of 3 kinds = the Euler transform of [3,3,3,...]. - Gary W. Adamson, Oct 26 2008
Paraphrasing the g.f.: 1 + 2x + 5x^2 + ... = s(x) * s(x^2) * s(x^3) * s(x^4) * ...; where s(x) = 1 + 2x + 3x^2 + 4x^3 + ... is (up to a factor x) the g.f. of A000027. - Gary W. Adamson, Apr 01 2010
Also equals number of partitions of 2n in which the odd parts appear as many times in even as in odd positions. - Wouter Meeussen, Apr 17 2013
Also number of ordered pairs (R,S) with R a partition of r, S a partition of s, and r+s=n; see example. This corresponds to the formula a(n) = sum(r+s==n, p(r)*p(s) ) = Sum_{k=0..n} p(k)*p(n-k). - Joerg Arndt, Apr 29 2013
Also the number of all multi-graphs with exactly n-edges and with vertex degrees 1 or 2. - Ebrahim Ghorbani, Dec 02 2013
If one decomposes k-permutations into cycles and so-called paths, the number of different type of decompositions equals to a(k); see the paper by Chen, Ghorbani, and Wong. - Ebrahim Ghorbani, Dec 02 2013
Let T(n,k) be the number of partitions of n having parts 1 through k of two kinds, with T(n,0) = A000041(n), the number of partitions of n. Then a(n) = T(n,0) + T(n-1,1) + T(n-2,2) + T(n-3,3) + ... - Gregory L. Simay, May 18 2019
Also the number of orbits of projections in the partition monoid P_n under conjugation by permutations. - James East, Jul 21 2020

Examples

			Assume there are integers of two kinds: k and k'; then a(3) = 10 since 3 has the following partitions into parts of two kinds: 111, 111', 11'1', 1'1'1', 12, 1'2, 12', 1'2', 3, and 3'. - _W. Edwin Clark_, Jun 24 2011
There are a(4)=20 partitions of 4 into 2 sorts of parts. Here p:s stands for "part p of sort s":
01:  [ 1:0  1:0  1:0  1:0  ]
02:  [ 1:0  1:0  1:0  1:1  ]
03:  [ 1:0  1:0  1:1  1:1  ]
04:  [ 1:0  1:1  1:1  1:1  ]
05:  [ 1:1  1:1  1:1  1:1  ]
06:  [ 2:0  1:0  1:0  ]
07:  [ 2:0  1:0  1:1  ]
08:  [ 2:0  1:1  1:1  ]
09:  [ 2:0  2:0  ]
10:  [ 2:0  2:1  ]
11:  [ 2:1  1:0  1:0  ]
12:  [ 2:1  1:0  1:1  ]
13:  [ 2:1  1:1  1:1  ]
14:  [ 2:1  2:1  ]
15:  [ 3:0  1:0  ]
16:  [ 3:0  1:1  ]
17:  [ 3:1  1:0  ]
18:  [ 3:1  1:1  ]
19:  [ 4:0  ]
20:  [ 4:1  ]
- _Joerg Arndt_, Apr 28 2013
The a(4)=20 ordered pairs (R,S) of partitions for n=4 are
  ([4], [])
  ([3, 1], [])
  ([2, 2], [])
  ([2, 1, 1], [])
  ([1, 1, 1, 1], [])
  ([3], [1])
  ([2, 1], [1])
  ([1, 1, 1], [1])
  ([2], [2])
  ([2], [1, 1])
  ([1, 1], [2])
  ([1, 1], [1, 1])
  ([1], [3])
  ([1], [2, 1])
  ([1], [1, 1, 1])
  ([], [4])
  ([], [3, 1])
  ([], [2, 2])
  ([], [2, 1, 1])
  ([], [1, 1, 1, 1])
This list was created with the Sage command
   for P in PartitionTuples(2,4) : print P;
- _Joerg Arndt_, Apr 29 2013
G.f. = 1 + 2*x + 5*x^2 + 10*x^3 + 20*x^4 + 36*x^5 + 65*x^6 + 110*x^7 + 185*x^8 + ...

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).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 1, 1999; see Proposition 2.5.2 on page 78.

Links

Crossrefs

Cf. A000165, A000041, A002107 (reciprocal of g.f.).
Cf. A002720.
Cf. A000716, A010815. - Gary W. Adamson, Oct 26 2008
Row sums of A175012. - Gary W. Adamson, Apr 03 2010
Column k=2 of A144064.
Cf. A008619, A000070, A000990, A285217, A304045.

Programs

  • Haskell
    a000712 = p a008619_list where
   p _          0 = 1
   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Nov 06 2012
  • Julia
    # DedekindEta is defined in A000594.
A000712List(len) = DedekindEta(len, -2)
A000712List(39) |> println # Peter Luschny, Mar 09 2018
  • Maple
    with(combinat): A000712:= n-> add(numbpart(k)*numbpart(n-k), k=0..n): seq(A000712(n), n=0..40); # Emeric Deutsch
  • Mathematica
    CoefficientList[ Series[ Product[1/(1 - x^n)^2, {n, 40}], {x, 0, 37}], x]; (* Robert G. Wilson v, Feb 03 2005 *)
Table[Count[Partitions[2*n], q_ /; Tr[(-1)^Mod[Flatten[Position[q, ?OddQ]], 2]] === 0], {n, 12}] (* _Wouter Meeussen, Apr 17 2013 *)
a[ n_] := SeriesCoefficient[ QPochhammer[ x]^-2, {x, 0, n}]; (* Michael Somos, Oct 12 2015 *)
Table[Length@IntegerPartitions[n, All, Range@n~Join~Range@n], {n, 0, 15}] (* Robert Price, Jun 15 2020 *)
  • PARI
    {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( 1 / eta(x + A)^2, n))}; /* Michael Somos, Nov 14 2002 */
  • PARI
    Vec(1/eta('x+O('x^66))^2) /* Joerg Arndt, Jun 25 2011 */
  • Python
    from sympy import npartitions
def A000712(n): return (sum(npartitions(k)*npartitions(n-k) for k in range(n+1>>1))<<1) + (0 if n&1 else npartitions(n>>1)**2) # Chai Wah Wu, Sep 25 2023
  • SageMath
    # uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(0, 1, 2, 2)
b = EulerTransform(a)
print([b(n) for n in range(40)]) # Peter Luschny, Nov 11 2020

Formula

a(n) = Sum_{k=0..n} p(k)*p(n-k), where p(n) = A000041(n).
Euler transform of period 1 sequence [ 2, 2, 2, ...]. - Michael Somos, Jul 22 2003
a(n) = A006330(n) + A001523(n). - Michael Somos, Jul 22 2003
a(0) = 1, a(n) = (1/n)*Sum_{k=0..n-1} 2*a(k)*sigma_1(n-k). - Joerg Arndt, Feb 05 2011
a(n) ~ (1/12)*3^(1/4)*n^(-5/4)*exp((2/3)*sqrt(3)*Pi*sqrt(n)). - Joe Keane (jgk(AT)jgk.org), Sep 13 2002
G.f.: Product_{i>=1} (1 + x^i)^(2*A001511(i)) (see A000041). - Jon Perry, Jun 06 2004
More precise asymptotics: a(n) ~ exp(2*Pi*sqrt(n/3)) / (4*3^(3/4)*n^(5/4)) * (1 - (Pi/(12*sqrt(3)) + 15*sqrt(3)/(16*Pi)) / sqrt(n) + (Pi^2/864 + 315/(512*Pi^2) + 35/192)/n). - Vaclav Kotesovec, Jan 22 2017
From Peter Bala, Jan 26 2016: (Start)
a(n) is odd iff n = 2*m and p(m) is odd.
a(n) = (2/n)*Sum_{k = 0..n} k*p(k)*p(n-k) for n >= 1.
Conjecture: : a(n) is divisible by 5 when n is congruent to 2, 3 or 4 modulo 5. (End)
Conjecture is proved in Hammond and Lewis. - Yen-chi R. Lin, Jun 24 2024
G.f.: exp(2*Sum_{k>=1} x^k/(k*(1 - x^k))). - Ilya Gutkovskiy, Feb 06 2018
With the convention that a(n) = 0 for n < 0 we have the recurrence a(n) = g(n) + Sum_{k >= 1} (-1)^(k+1)*(2*k + 1)*a(n - k*(k + 1)/2), where g(n) = (-1)^m if n = m*(3*m - 1)/2 is a generalized pentagonal number (A001318) else g(n) = 0. For example, n = 7 = -2*(3*(-2) - 1)/2 is a pentagonal number, g(7) = 1, and so a(7) = 1 + 3*a(6) - 5*a(4) + 7*a(1) = 1 + 195 - 100 + 14 = 110. - Peter Bala, Apr 06 2022
a(n) = p(n/2) + Sum_{k \in Z, k != 0} (-1)^{k-1} a(n-k^2), here p(n) = A000041(n) and p(x) = 0 when x is not an integer. - Yen-chi R. Lin, Jun 24 2024
Conjecture: a(25*n + 23) is divisible by 25 (checked for n < 400). - Peter Bala, Jan 13 2025

Extensions

More terms from Joe Keane (jgk(AT)jgk.org), Nov 17 2001
More terms from Michele Dondi (blazar(AT)lcm.mi.infn.it), Jun 15 2004
Definition rewritten by N. J. A. Sloane, Apr 02 2022

A034691 Euler transform of powers of 2 [1,2,4,8,16,...].

Original entry on oeis.org

1, 1, 3, 7, 18, 42, 104, 244, 585, 1373, 3233, 7533, 17547, 40591, 93711, 215379, 493735, 1127979, 2570519, 5841443, 13243599, 29953851, 67604035, 152258271, 342253980, 767895424, 1719854346, 3845443858
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This is the number of different hierarchical orderings that can be formed from n unlabeled elements: these are divided into groups and the elements in each group are then arranged in an "unlabeled preferential arrangement" or "composition" as in A000079. - Thomas Wieder and N. J. A. Sloane, Jun 10 2003
From Gus Wiseman, Mar 03 2016: (Start)
The original Sloane-Wieder definition, "To obtain a hierarchical ordering we partition the elements into unlabeled nonempty subsets and form a composition of each subset," [arXiv:math/0307064] has two possible meanings. The first possible meaning is that we should (1) choose a set partition pi of {1...n} and (2) for each block of pi choose a composition of the number of elements. In this case the correct number of such structures would evidently be counted by A004211 which differs from a(n) for n > 2.
The other possible meaning is that after we have done (1) and (2) above we (3) "forget" the choice of pi. We will have produced a collection M of multisets of compositions. The span of M (its set of distinct elements) is correctly counted by A034691 and it seems that non-isomorphic hierarchical orderings of unlabeled sets are nothing more than multisets of compositions. This discovery is due to Wieder. (End)
The asymptotic formula in the article by N. J. A. Sloane and Thomas Wieder, "The Number of Hierarchical Orderings" (Theorem 3) is incorrect (a multiplicative factor of 1.397... is missing, see my formula below). - Vaclav Kotesovec, Sep 08 2014
Number of partitions of n into 1 sort of 1, 2 sorts of 2's, 4 sorts of 3's, ..., 2^(k-1) sorts of k's, ... . - Joerg Arndt, Sep 09 2014
Also number of normal multiset partitions of weight n, where a multiset is normal if it spans an initial interval of positive integers. - Gus Wiseman, Mar 03 2016

Examples

			The normal multiset partitions for a(4) = 18: {{1111},{1222},{1122},{1112},{1233},{1223},{1123},{1234},{1,111},{1,122},{1,112},{1,123},{11,11},{11,12},{12,12},{1,1,11},{1,1,12},{1,1,1,1}}

Links

Crossrefs

Cf. A034899, A075729, A247003, A004211, A104500 (Euler transform), A290222 (Multiset transform).

Programs

  • Maple
    oo := 101: mul( 1/(1-x^j)^(2^(j-1)),j=1..oo): series(%,x,oo): t1 := seriestolist(%); A034691 := n-> t1[n+1];
with(combstruct); SetSeqSetU := [T, {T=Set(S), S=Sequence(U,card >= 1), U=Set(Z,card >=1)},unlabeled]; seq(count(SetSeqSetU,size=j),j=1..12);
# Alternative, uses EulerTransform from A358369:
a := EulerTransform(BinaryRecurrenceSequence(2, 0)):
seq(a(n), n = 0..27); # Peter Luschny, Nov 17 2022
  • Mathematica
    nn = 30; b = Table[2^n, {n, 0, nn}]; CoefficientList[Series[Product[1/(1 - x^m)^b[[m]], {m, nn}], {x, 0, nn}],  x] (* T. D. Noe, Nov 21 2011 *)
Table[SeriesCoefficient[E^(Sum[x^k/(1 - 2*x^k)/k, {k, 1, n}]), {x, 0, n}], {n, 0, 30}] (* Vaclav Kotesovec, Sep 08 2014 *)
allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
allnmsp[0]={};allnmsp[1]={{{1}}};allnmsp[n_Integer]:=allnmsp[n]=Join[allnmsp[n-1],List/@allnorm[n],Join@@Function[ptn,Append[ptn,#]&/@Select[allnorm[n-Length[Join@@ptn]],OrderedQ[{Last[ptn],#}]&]]/@allnmsp[n-1]];
Apply[SequenceForm,Select[allnmsp[4],Length[Join@@#]===4&],{2}] (* to construct the example *)
Table[Length[Complement[allnmsp[n],allnmsp[n-1]]],{n,1,8}] (* Gus Wiseman, Mar 03 2016 *)
  • PARI
    A034691(n,l=1+O('x^(n+1)))={polcoeff(1/prod(k=1,n,(l-'x^k)^2^(k-1)),n)} \\ Michael Somos, Nov 21 2011, edited by M. F. Hasler, Jul 24 2017
  • SageMath
    # uses[EulerTransform from A166861]
a = BinaryRecurrenceSequence(2, 0)
b = EulerTransform(a)
print([b(n) for n in range(30)]) # Peter Luschny, Nov 11 2020

Formula

G.f.: 1 / Product_{n>=1} (1-x^n)^(2^(n-1)).
Recurrence: a(n) = (1/n) * Sum_{m=1..n} a(n-m)*c(m) where c(m) = A083413(m).
a(n) ~ c * 2^n * exp(sqrt(2*n)) / (sqrt(2*Pi) * exp(1/4) * 2^(3/4) * n^(3/4)), where c = exp( Sum_{k>=2} 1/(k*(2^k-2)) ) = 1.3976490050836502... (see A247003). - Vaclav Kotesovec, Sep 08 2014

A000294 Expansion of g.f. Product_{k >= 1} (1 - x^k)^(-k*(k+1)/2).

Original entry on oeis.org

1, 1, 4, 10, 26, 59, 141, 310, 692, 1483, 3162, 6583, 13602, 27613, 55579, 110445, 217554, 424148, 820294, 1572647, 2992892, 5652954, 10605608, 19765082, 36609945, 67405569, 123412204, 224728451, 407119735, 733878402, 1316631730, 2351322765, 4180714647, 7401898452, 13051476707, 22922301583, 40105025130, 69909106888, 121427077241, 210179991927, 362583131144
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of partitions of n if there are k(k+1)/2 kinds of k (k=1,2,...). E.g., a(3)=10 because we have six kinds of 3, three kinds of 2+1 because there are three kinds of 2 and 1+1+1+1. - Emeric Deutsch, Mar 23 2005
Euler transform of the triangular numbers 1,3,6,10,...
Equals A028377: [1, 1, 3, 9, 19, 46, 100, ...] convolved with the aerated version of A000294: [1, 0, 1, 0, 4, 0, 10, 0, 26, 0, 59, ...]. - Gary W. Adamson, Jun 13 2009
The formula for p3(n) in the article by S. Finch (page 2) is incomplete, terms with n^(1/2) and n^(1/4) are also needed. These terms are in the article by Mustonen and Rajesh (page 2) and agree with my results, but in both articles the multiplicative constant is marked only as C, resp. c3(m). The following is a closed form of this constant: Pi^(1/24) * exp(1/24 - Zeta(3) / (8*Pi^2) + 75*Zeta(3)^3 / (2*Pi^8)) / (A^(1/2) * 2^(157/96) * 15^(13/96)) = A255939 = 0.213595160470..., where A = A074962 is the Glaisher-Kinkelin constant and Zeta(3) = A002117. - Vaclav Kotesovec, Mar 11 2015 [The new version of "Integer Partitions" by S. Finch contains the missing terms, see pages 2 and 5. - Vaclav Kotesovec, May 12 2015]
Number of solid partitions of corner-hook volume n (see arXiv:2009.00592 among links for definition). E.g., a(2) = 1 because there is only one solid partition [[[2]]] with cohook volume 2; a(3) = 4 because we have three solid partitions with two 1's (entry at (1,1,1) contributes 1, another entry at (2,1,1) or (1,2,1) or (1,1,2) contributes 2 to corner-hook volume) and one solid partition with single entry 3 (which contributes 3 to the corner-hook volume). Namely as 3D arrays [[[1],[1]]],[[[1]],[[1]]],[[[1]],[[1]]], [[[3]]]. - Alimzhan Amanov, Jul 13 2021

References

  • R. Chandra, Tables of solid partitions, Proceedings of the Indian National Science Academy, 26 (1960), 134-139.
  • V. S. Nanda, Tables of solid partitions, Proceedings of the Indian National Science Academy, 19 (1953), 313-314.
  • 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

Crossrefs

Cf. A000293, A007294, A007326, A255939, A028377.
Cf. also A000041, A000219, A000335, A000391, A000417, A000428, A255965.
Cf. also A278403 (log of o.g.f.).

Programs

  • 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-> n*(n+1)/2): seq(a(n), n=0..30);  # Alois P. Heinz, Sep 08 2008
  • Mathematica
    a[0] = 1; a[n_] := a[n] = 1/(2*n)*Sum[(DivisorSigma[2, k]+DivisorSigma[3, k])*a[n-k], {k, 1, n}]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Mar 05 2014, after Vladeta Jovovic *)
nmax=50; CoefficientList[Series[Product[1/(1-x^k)^(k*(k+1)/2),{k,1,nmax}],{x,0,nmax}],x] (* Vaclav Kotesovec, Mar 11 2015 *)
  • PARI
    a(n)=if(n<0, 0, polcoeff(exp(sum(k=1, n, x^k/(1-x^k)^3/k, x*O(x^n))), n)) \\ Joerg Arndt, Apr 16 2010
  • SageMath
    # uses[EulerTransform from A166861]
b = EulerTransform(lambda n: binomial(n+1, 2))
print([b(n) for n in range(37)]) # Peter Luschny, Nov 11 2020

Formula

a(n) = (1/(2*n))*Sum_{k=1..n} (sigma[2](k)+sigma[3](k))*a(n-k). - Vladeta Jovovic, Sep 17 2002
a(n) ~ Pi^(1/24) * exp(1/24 - Zeta(3) / (8*Pi^2) + 75*Zeta(3)^3 / (2*Pi^8) - 15^(5/4) * Zeta(3)^2 * n^(1/4) / (2^(7/4)*Pi^5) + 15^(1/2) * Zeta(3) * n^(1/2) / (2^(1/2)*Pi^2) + 2^(7/4) * Pi * n^(3/4) / (3*15^(1/4))) / (A^(1/2) * 2^(157/96) * 15^(13/96) * n^(61/96)), where A = A074962 = 1.2824271291... is the Glaisher-Kinkelin constant and Zeta(3) = A002117 = 1.202056903... . - Vaclav Kotesovec, Mar 11 2015
G.f.: exp(Sum_{k>=1} (sigma_2(k) + sigma_3(k))*x^k/(2*k)). - Ilya Gutkovskiy, Aug 21 2018

Extensions

More terms from Sascha Kurz, Aug 15 2002
Showing 1-10 of 45 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.