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 62 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

A000108 Catalan numbers: C(n) = binomial(2n,n)/(n+1) = (2n)!/(n!(n+1)!).

Original entry on oeis.org

1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790, 477638700, 1767263190, 6564120420, 24466267020, 91482563640, 343059613650, 1289904147324, 4861946401452, 18367353072152, 69533550916004, 263747951750360, 1002242216651368, 3814986502092304
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

These were formerly sometimes called Segner numbers.
A very large number of combinatorial interpretations are known - see references, esp. R. P. Stanley, "Catalan Numbers", Cambridge University Press, 2015. This is probably the longest entry in the OEIS, and rightly so.
The solution to Schröder's first problem: number of ways to insert n pairs of parentheses in a word of n+1 letters. E.g., for n=2 there are 2 ways: ((ab)c) or (a(bc)); for n=3 there are 5 ways: ((ab)(cd)), (((ab)c)d), ((a(bc))d), (a((bc)d)), (a(b(cd))).
Consider all the binomial(2n,n) paths on squared paper that (i) start at (0, 0), (ii) end at (2n, 0) and (iii) at each step, either make a (+1,+1) step or a (+1,-1) step. Then the number of such paths that never go below the x-axis (Dyck paths) is C(n). [Chung-Feller]
Number of noncrossing partitions of the n-set. For example, of the 15 set partitions of the 4-set, only [{13},{24}] is crossing, so there are a(4)=14 noncrossing partitions of 4 elements. - Joerg Arndt, Jul 11 2011
Noncrossing partitions are partitions of genus 0. - Robert Coquereaux, Feb 13 2024
a(n-1) is the number of ways of expressing an n-cycle (123...n) in the symmetric group S_n as a product of n-1 transpositions (u_1,v_1)*(u_2,v_2)*...*(u_{n-1},v_{n-1}) where u_iA000272. - Joerg Arndt and Greg Stevenson, Jul 11 2011
a(n) is the number of ordered rooted trees with n nodes, not including the root. See the Conway-Guy reference where these rooted ordered trees are called plane bushes. See also the Bergeron et al. reference, Example 4, p. 167. - Wolfdieter Lang, Aug 07 2007
As shown in the paper from Beineke and Pippert (1971), a(n-2)=D(n) is the number of labeled dissections of a disk, related to the number R(n)=A001761(n-2) of labeled planar 2-trees having n vertices and rooted at a given exterior edge, by the formula D(n)=R(n)/(n-2)!. - M. F. Hasler, Feb 22 2012
Shifts one place left when convolved with itself.
For n >= 1, a(n) is also the number of rooted bicolored unicellular maps of genus 0 on n edges. - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 15 2001
Number of ways of joining 2n points on a circle to form n nonintersecting chords. (If no such restriction imposed, then the number of ways of forming n chords is given by (2n-1)!! = (2n)!/(n!*2^n) = A001147(n).)
Arises in Schubert calculus - see Sottile reference.
Inverse Euler transform of sequence is A022553.
With interpolated zeros, the inverse binomial transform of the Motzkin numbers A001006. - Paul Barry, Jul 18 2003
The Hankel transforms of this sequence or of this sequence with the first term omitted give A000012 = 1, 1, 1, 1, 1, 1, ...; example: Det([1, 1, 2, 5; 1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132]) = 1 and Det([1, 2, 5, 14; 2, 5, 14, 42; 5, 14, 42, 132; 14, 42, 132, 429]) = 1. - Philippe Deléham, Mar 04 2004
a(n) equals the sum of squares of terms in row n of triangle A053121, which is formed from successive self-convolutions of the Catalan sequence. - Paul D. Hanna, Apr 23 2005
Also coefficients of the Mandelbrot polynomial M iterated an infinite number of times. Examples: M(0) = 0 = 0*c^0 = [0], M(1) = c = c^1 + 0*c^0 = [1 0], M(2) = c^2 + c = c^2 + c^1 + 0*c^0 = [1 1 0], M(3) = (c^2 + c)^2 + c = [0 1 1 2 1], ... ... M(5) = [0 1 1 2 5 14 26 44 69 94 114 116 94 60 28 8 1], ... - Donald D. Cross (cosinekitty(AT)hotmail.com), Feb 04 2005
The multiplicity with which a prime p divides C_n can be determined by first expressing n+1 in base p. For p=2, the multiplicity is the number of 1 digits minus 1. For p an odd prime, count all digits greater than (p+1)/2; also count digits equal to (p+1)/2 unless final; and count digits equal to (p-1)/2 if not final and the next digit is counted. For example, n=62, n+1 = 223_5, so C_62 is not divisible by 5. n=63, n+1 = 224_5, so 5^3 | C_63. - Franklin T. Adams-Watters, Feb 08 2006
Koshy and Salmassi give an elementary proof that the only prime Catalan numbers are a(2) = 2 and a(3) = 5. Is the only semiprime Catalan number a(4) = 14? - Jonathan Vos Post, Mar 06 2006
The answer is yes. Using the formula C_n = binomial(2n,n)/(n+1), it is immediately clear that C_n can have no prime factor greater than 2n. For n >= 7, C_n > (2n)^2, so it cannot be a semiprime. Given that the Catalan numbers grow exponentially, the above consideration implies that the number of prime divisors of C_n, counted with multiplicity, must grow without limit. The number of distinct prime divisors must also grow without limit, but this is more difficult. Any prime between n+1 and 2n (exclusive) must divide C_n. That the number of such primes grows without limit follows from the prime number theorem. - Franklin T. Adams-Watters, Apr 14 2006
The number of ways to place n indistinguishable balls in n numbered boxes B1,...,Bn such that at most a total of k balls are placed in boxes B1,...,Bk for k=1,...,n. For example, a(3)=5 since there are 5 ways to distribute 3 balls among 3 boxes such that (i) box 1 gets at most 1 ball and (ii) box 1 and box 2 together get at most 2 balls:(O)(O)(O), (O)()(OO), ()(OO)(O), ()(O)(OO), ()()(OOO). - Dennis P. Walsh, Dec 04 2006
a(n) is also the order of the semigroup of order-decreasing and order-preserving full transformations (of an n-element chain) - now known as the Catalan monoid. - Abdullahi Umar, Aug 25 2008
a(n) is the number of trivial representations in the direct product of 2n spinor (the smallest) representations of the group SU(2) (A(1)). - Rutger Boels (boels(AT)nbi.dk), Aug 26 2008
The invert transform appears to converge to the Catalan numbers when applied infinitely many times to any starting sequence. - Mats Granvik, Gary W. Adamson and Roger L. Bagula, Sep 09 2008, Sep 12 2008
Limit_{n->oo} a(n)/a(n-1) = 4. - Francesco Antoni (francesco_antoni(AT)yahoo.com), Nov 24 2008
Starting with offset 1 = row sums of triangle A154559. - Gary W. Adamson, Jan 11 2009
C(n) is the degree of the Grassmannian G(1,n+1): the set of lines in (n+1)-dimensional projective space, or the set of planes through the origin in (n+2)-dimensional affine space. The Grassmannian is considered a subset of N-dimensional projective space, N = binomial(n+2,2) - 1. If we choose 2n general (n-1)-planes in projective (n+1)-space, then there are C(n) lines that meet all of them. - Benji Fisher (benji(AT)FisherFam.org), Mar 05 2009
Starting with offset 1 = A068875: (1, 2, 4, 10, 18, 84, ...) convolved with Fine numbers, A000957: (1, 0, 1, 2, 6, 18, ...). a(6) = 132 = (1, 2, 4, 10, 28, 84) dot (18, 6, 2, 1, 0, 1) = (18 + 12 + 8 + 10 + 0 + 84) = 132. - Gary W. Adamson, May 01 2009
Convolved with A032443: (1, 3, 11, 42, 163, ...) = powers of 4, A000302: (1, 4, 16, ...). - Gary W. Adamson, May 15 2009
Sum_{k>=1} C(k-1)/2^(2k-1) = 1. The k-th term in the summation is the probability that a random walk on the integers (beginning at the origin) will arrive at positive one (for the first time) in exactly (2k-1) steps. - Geoffrey Critzer, Sep 12 2009
C(p+q)-C(p)*C(q) = Sum_{i=0..p-1, j=0..q-1} C(i)*C(j)*C(p+q-i-j-1). - Groux Roland, Nov 13 2009
Leonhard Euler used the formula C(n) = Product_{i=3..n} (4*i-10)/(i-1) in his 'Betrachtungen, auf wie vielerley Arten ein gegebenes polygonum durch Diagonallinien in triangula zerschnitten werden könne' and computes by recursion C(n+2) for n = 1..8. (Berlin, 4th September 1751, in a letter to Goldbach.) - Peter Luschny, Mar 13 2010
Let A179277 = A(x). Then C(x) is satisfied by A(x)/A(x^2). - Gary W. Adamson, Jul 07 2010
a(n) is also the number of quivers in the mutation class of type B_n or of type C_n. - Christian Stump, Nov 02 2010
From Matthew Vandermast, Nov 22 2010: (Start)
Consider a set of A000217(n) balls of n colors in which, for each integer k = 1 to n, exactly one color appears in the set a total of k times. (Each ball has exactly one color and is indistinguishable from other balls of the same color.) a(n+1) equals the number of ways to choose 0 or more balls of each color while satisfying the following conditions: 1. No two colors are chosen the same positive number of times. 2. For any two colors (c, d) that are chosen at least once, color c is chosen more times than color d iff color c appears more times in the original set than color d.
If the second requirement is lifted, the number of acceptable ways equals A000110(n+1). See related comments for A016098, A085082. (End)
Deutsch and Sagan prove the Catalan number C_n is odd if and only if n = 2^a - 1 for some nonnegative integer a. Lin proves for every odd Catalan number C_n, we have C_n == 1 (mod 4). - Jonathan Vos Post, Dec 09 2010
a(n) is the number of functions f:{1,2,...,n}->{1,2,...,n} such that f(1)=1 and for all n >= 1 f(n+1) <= f(n)+1. For a nice bijection between this set of functions and the set of length 2n Dyck words, see page 333 of the Fxtbook (see link below). - Geoffrey Critzer, Dec 16 2010
Postnikov (2005) defines "generalized Catalan numbers" associated with buildings (e.g., Catalan numbers of Type B, see A000984). - N. J. A. Sloane, Dec 10 2011
Number of permutations in S(n) for which length equals depth. - Bridget Tenner, Feb 22 2012
a(n) is also the number of standard Young tableau of shape (n,n). - Thotsaporn Thanatipanonda, Feb 25 2012
a(n) is the number of binary sequences of length 2n+1 in which the number of ones first exceed the number of zeros at entry 2n+1. See the example below in the example section. - Dennis P. Walsh, Apr 11 2012
Number of binary necklaces of length 2*n+1 containing n 1's (or, by symmetry, 0's). All these are Lyndon words and their representatives (as cyclic maxima) are the binary Dyck words. - Joerg Arndt, Nov 12 2012
Number of sequences consisting of n 'x' letters and n 'y' letters such that (counting from the left) the 'x' count >= 'y' count. For example, for n=3 we have xxxyyy, xxyxyy, xxyyxy, xyxxyy and xyxyxy. - Jon Perry, Nov 16 2012
a(n) is the number of Motzkin paths of length n-1 in which the (1,0)-steps come in 2 colors. Example: a(4)=14 because, denoting U=(1,1), H=(1,0), and D=(1,-1), we have 8 paths of shape HHH, 2 paths of shape UHD, 2 paths of shape UDH, and 2 paths of shape HUD. - José Luis Ramírez Ramírez, Jan 16 2013
If p is an odd prime, then (-1)^((p-1)/2)*a((p-1)/2) mod p = 2. - Gary Detlefs, Feb 20 2013
Conjecture: For any positive integer n, the polynomial Sum_{k=0..n} a(k)*x^k is irreducible over the field of rational numbers. - Zhi-Wei Sun, Mar 23 2013
a(n) is the size of the Jones monoid on 2n points (cf. A225798). - James Mitchell, Jul 28 2013
For 0 < p < 1, define f(p) = Sum_{n>=0} a(n)*(p*(1-p))^n, then f(p) = min{1/p, 1/(1-p)}, so f(p) reaches its maximum value 2 at p = 0.5, and p*f(p) is constant 1 for 0.5 <= p < 1. - Bob Selcoe, Nov 16 2013 [Corrected by Jianing Song, May 21 2021]
No a(n) has the form x^m with m > 1 and x > 1. - Zhi-Wei Sun, Dec 02 2013
From Alexander Adamchuk, Dec 27 2013: (Start)
Prime p divides a((p+1)/2) for p > 3. See A120303(n) = Largest prime factor of Catalan number.
Reciprocal Catalan Constant C = 1 + 4*sqrt(3)*Pi/27 = 1.80613.. = A121839.
Log(Phi) = (125*C - 55) / (24*sqrt(5)), where C = Sum_{k>=1} (-1)^(k+1)*1/a(k). See A002390 = Decimal expansion of natural logarithm of golden ratio.
3-d analog of the Catalan numbers: (3n)!/(n!(n+1)!(n+2)!) = A161581(n) = A006480(n) / ((n+1)^2*(n+2)), where A006480(n) = (3n)!/(n!)^3 De Bruijn's S(3,n). (End)
For a relation to the inviscid Burgers's, or Hopf, equation, see A001764. - Tom Copeland, Feb 15 2014
From Fung Lam, May 01 2014: (Start)
One class of generalized Catalan numbers can be defined by g.f. A(x) = (1-sqrt(1-q*4*x*(1-(q-1)*x)))/(2*q*x) with nonzero parameter q. Recurrence: (n+3)*a(n+2) -2*q*(2*n+3)*a(n+1) +4*q*(q-1)*n*a(n) = 0 with a(0)=1, a(1)=1.
Asymptotic approximation for q >= 1: a(n) ~ (2*q+2*sqrt(q))^n*sqrt(2*q*(1+sqrt(q))) /sqrt(4*q^2*Pi*n^3).
For q <= -1, the g.f. defines signed sequences with asymptotic approximation: a(n) ~ Re(sqrt(2*q*(1+sqrt(q)))*(2*q+2*sqrt(q))^n) / sqrt(q^2*Pi*n^3), where Re denotes the real part. Due to Stokes' phenomena, accuracy of the asymptotic approximation deteriorates at/near certain values of n.
Special cases are A000108 (q=1), A068764 to A068772 (q=2 to 10), A240880 (q=-3).
(End)
Number of sequences [s(0), s(1), ..., s(n)] with s(n)=0, Sum_{j=0..n} s(j) = n, and Sum_{j=0..k} s(j)-1 >= 0 for k < n-1 (and necessarily Sum_{j=0..n-1} s(j)-1 = 0). These are the branching sequences of the (ordered) trees with n non-root nodes, see example. - Joerg Arndt, Jun 30 2014
Number of stack-sortable permutations of [n], these are the 231-avoiding permutations; see the Bousquet-Mélou reference. - Joerg Arndt, Jul 01 2014
a(n) is the number of increasing strict binary trees with 2n-1 nodes that avoid 132. For more information about increasing strict binary trees with an associated permutation, see A245894. - Manda Riehl, Aug 07 2014
In a one-dimensional medium with elastic scattering (zig-zag walk), first recurrence after 2n+1 scattering events has the probability C(n)/2^(2n+1). - Joachim Wuttke, Sep 11 2014
The o.g.f. C(x) = (1 - sqrt(1-4x))/2, for the Catalan numbers, with comp. inverse Cinv(x) = x*(1-x) and the functions P(x) = x / (1 + t*x) and its inverse Pinv(x,t) = -P(-x,t) = x / (1 - t*x) form a group under composition that generates or interpolates among many classic arrays, such as the Motzkin (Riordan, A005043), Fibonacci (A000045), and Fine (A000957) numbers and polynomials (A030528), and enumerating arrays for Motzkin, Dyck, and Łukasiewicz lattice paths and different types of trees and non-crossing partitions (A091867, connected to sums of the refined Narayana numbers A134264). - Tom Copeland, Nov 04 2014
Conjecture: All the rational numbers Sum_{i=j..k} 1/a(i) with 0 < min{2,k} <= j <= k have pairwise distinct fractional parts. - Zhi-Wei Sun, Sep 24 2015
The Catalan number series A000108(n+3), offset n=0, gives Hankel transform revealing the square pyramidal numbers starting at 5, A000330(n+2), offset n=0 (empirical observation). - Tony Foster III, Sep 05 2016
Hankel transforms of the Catalan numbers with the first 2, 4, and 5 terms omitted give A001477, A006858, and A091962, respectively, without the first 2 terms in all cases. More generally, the Hankel transform of the Catalan numbers with the first k terms omitted is H_k(n) = Product_{j=1..k-1} Product_{i=1..j} (2*n+j+i)/(j+i) [see Cigler (2011), Eq. (1.14) and references therein]; together they form the array A078920/A123352/A368025. - Andrey Zabolotskiy, Oct 13 2016
Presumably this satisfies Benford's law, although the results in Hürlimann (2009) do not make this clear. See S. J. Miller, ed., 2015, p. 5. - N. J. A. Sloane, Feb 09 2017
Coefficients of the generating series associated to the Magmatic and Dendriform operadic algebras. Cf. p. 422 and 435 of the Loday et al. paper. - Tom Copeland, Jul 08 2018
Let M_n be the n X n matrix with M_n(i,j) = binomial(i+j-1,2j-2); then det(M_n) = a(n). - Tony Foster III, Aug 30 2018
Also the number of Catalan trees, or planted plane trees (Bona, 2015, p. 299, Theorem 4.6.3). - N. J. A. Sloane, Dec 25 2018
Number of coalescent histories for a caterpillar species tree and a matching caterpillar gene tree with n+1 leaves (Rosenberg 2007, Corollary 3.5). - Noah A Rosenberg, Jan 28 2019
Finding solutions of eps*x^2+x-1 = 0 for eps small, that is, writing x = Sum_{n>=0} x_{n}*eps^n and expanding, one finds x = 1 - eps + 2*eps^2 - 5*eps^3 + 14*eps^3 - 42*eps^4 + ... with x_{n} = (-1)^n*C(n). Further, letting x = 1/y and expanding y about 0 to find large roots, that is, y = Sum_{n>=1} y_{n}*eps^n, one finds y = 0 - eps + eps^2 - 2*eps^3 + 5*eps^3 - ... with y_{n} = (-1)^n*C(n-1). - Derek Orr, Mar 15 2019
Permutations of length n that produce a bipartite permutation graph of order n [see Knuth (1973), Busch (2006), Golumbic and Trenk (2004)]. - Elise Anderson, R. M. Argus, Caitlin Owens, Tessa Stevens, Jun 27 2019
For n > 0, a random selection of n + 1 objects (the minimum number ensuring one pair by the pigeonhole principle) from n distinct pairs of indistinguishable objects contains only one pair with probability 2^(n-1)/a(n) = b(n-1)/A098597(n), where b is the 0-offset sequence with the terms of A120777 repeated (1,1,4,4,8,8,64,64,128,128,...). E.g., randomly selecting 6 socks from 5 pairs that are black, blue, brown, green, and white, results in only one pair of the same color with probability 2^(5-1)/a(5) = 16/42 = 8/21 = b(4)/A098597(5). - Rick L. Shepherd, Sep 02 2019
See Haran & Tabachnikov link for a video discussing Conway-Coxeter friezes. The Conway-Coxeter friezes with n nontrivial rows are generated by the counts of triangles at each vertex in the triangulations of regular n-gons, of which there are a(n). - Charles R Greathouse IV, Sep 28 2019
For connections to knot theory and scattering amplitudes from Feynman diagrams, see Broadhurst and Kreimer, and Todorov. Eqn. 6.12 on p. 130 of Bessis et al. becomes, after scaling, -12g * r_0(-y/(12g)) = (1-sqrt(1-4y))/2, the o.g.f. (expressed as a Taylor series in Eqn. 7.22 in 12gx) given for the Catalan numbers in Copeland's (Sep 30 2011) formula below. (See also Mizera p. 34, Balduf pp. 79-80, Keitel and Bartosch.) - Tom Copeland, Nov 17 2019
Number of permutations in S_n whose principal order ideals in the weak order are modular lattices. - Bridget Tenner, Jan 16 2020
Number of permutations in S_n whose principal order ideals in the weak order are distributive lattices. - Bridget Tenner, Jan 16 2020
Legendre gives the following formula for computing the square root modulo 2^m:
sqrt(1 + 8*a) mod 2^m = (1 + 4*a*Sum_{i=0..m-4} C(i)*(-2*a)^i) mod 2^m
as cited by L. D. Dickson, History of the Theory of Numbers, Vol. 1, 207-208. - Peter Schorn, Feb 11 2020
a(n) is the number of length n permutations sorted to the identity by a consecutive-132-avoiding stack followed by a classical-21-avoiding stack. - Kai Zheng, Aug 28 2020
Number of non-crossing partitions of a 2*n-set with n blocks of size 2. Also number of non-crossing partitions of a 2*n-set with n+1 blocks of size at most 3, and without cyclical adjacencies. The two partitions can be mapped by rotated Kreweras bijection. - Yuchun Ji, Jan 18 2021
Named by Riordan (1968, and earlier in Mathematical Reviews, 1948 and 1964) after the French and Belgian mathematician Eugène Charles Catalan (1814-1894) (see Pak, 2014). - Amiram Eldar, Apr 15 2021
For n >= 1, a(n-1) is the number of interpretations of x^n is an algebra where power-associativity is not assumed. For example, for n = 4 there are a(3) = 5 interpretations: x(x(xx)), x((xx)x), (xx)(xx), (x(xx))x, ((xx)x)x. See the link "Non-associate powers and a functional equation" from I. M. H. Etherington and the page "Nonassociative Product" from Eric Weisstein's World of Mathematics for detailed information. See also A001190 for the case where multiplication is commutative. - Jianing Song, Apr 29 2022
Number of states in the transition diagram associated with the Laplacian system over the complete graph K_N, corresponding to ordered initial conditions x_1 < x_2 < ... < x_N. - Andrea Arlette España, Nov 06 2022
a(n) is the number of 132-avoiding stabilized-interval-free permutations of size n+1. - Juan B. Gil, Jun 22 2023
Number of rooted polyominoes composed of n triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {3,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024
a(n) is the number of extremely lucky Stirling permutations of order n; i.e., the number of Stirling permutations of order n that have exactly n lucky cars. (see Colmenarejo et al. reference) - Bridget Tenner, Apr 16 2024

Examples

			From _Joerg Arndt_ and Greg Stevenson, Jul 11 2011: (Start)
The following products of 3 transpositions lead to a 4-cycle in S_4:
(1,2)*(1,3)*(1,4);
(1,2)*(1,4)*(3,4);
(1,3)*(1,4)*(2,3);
(1,4)*(2,3)*(2,4);
(1,4)*(2,4)*(3,4). (End)
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 42*x^5 + 132*x^6 + 429*x^7 + ...
For n=3, a(3)=5 since there are exactly 5 binary sequences of length 7 in which the number of ones first exceed the number of zeros at entry 7, namely, 0001111, 0010111, 0011011, 0100111, and 0101011. - _Dennis P. Walsh_, Apr 11 2012
From _Joerg Arndt_, Jun 30 2014: (Start)
The a(4) = 14 branching sequences of the (ordered) trees with 4 non-root nodes are (dots denote zeros):
01:  [ 1 1 1 1 . ]
02:  [ 1 1 2 . . ]
03:  [ 1 2 . 1 . ]
04:  [ 1 2 1 . . ]
05:  [ 1 3 . . . ]
06:  [ 2 . 1 1 . ]
07:  [ 2 . 2 . . ]
08:  [ 2 1 . 1 . ]
09:  [ 2 1 1 . . ]
10:  [ 2 2 . . . ]
11:  [ 3 . . 1 . ]
12:  [ 3 . 1 . . ]
13:  [ 3 1 . . . ]
14:  [ 4 . . . . ]
(End)

References

  • The large number of references and links demonstrates the ubiquity of the Catalan numbers.
  • R. Alter, Some remarks and results on Catalan numbers, pp. 109-132 in Proceedings of the Louisiana Conference on Combinatorics, Graph Theory and Computer Science. Vol. 2, edited R. C. Mullin et al., 1971.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, many references.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 53.
  • J. H. Conway and R. K. Guy, The Book of Numbers, New York: Springer-Verlag, 1995, ch. 4, pp. 96-106.
  • S. J. Cyvin and I. Gutman, Kekulé structures in benzenoid hydrocarbons, Lecture Notes in Chemistry, No. 46, Springer, New York, 1988 (see pp. 183, 196, etc.).
  • Michael Dairyko, Samantha Tyner, Lara Pudwell, and Casey Wynn, Non-contiguous pattern avoidance in binary trees. Electron. J. Combin. 19 (2012), no. 3, Paper 22, 21 pp. MR2967227.
  • E. Deutsch, Dyck path enumeration, Discrete Math., 204, 167-202, 1999.
  • E. Deutsch and L. Shapiro, Seventeen Catalan identities, Bulletin of the Institute of Combinatorics and its Applications, 31, 31-38, 2001.
  • L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 1, 207-208.
  • Tomislav Doslic and Darko Veljan, Logarithmic behavior of some combinatorial sequences. Discrete Math. 308 (2008), no. 11, 2182-2212. MR2404544 (2009j:05019)
  • S. Dulucq and J.-G. Penaud, Cordes, arbres et permutations. Discrete Math. 117 (1993), no. 1-3, 89-105.
  • A. Errera, Analysis situs - Un problème d'énumération, Mémoires Acad. Bruxelles, Classe des sciences, Série 2, Vol. XI, Fasc. 6, No. 1421 (1931), 26 pp.
  • Ehrenfeucht, Andrzej; Haemer, Jeffrey; Haussler, David. Quasimonotonic sequences: theory, algorithms and applications. SIAM J. Algebraic Discrete Methods 8 (1987), no. 3, 410-429. MR0897739 (88h:06026)
  • I. M. H. Etherington, Non-associate powers and a functional equation. The Mathematical Gazette, 21 (1937): 36-39; addendum 21 (1937), 153.
  • I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
  • I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
  • K. Fan, Structure of a Hecke algebra quotient, J. Amer. Math. Soc., 10 (1997), 139-167.
  • Susanna Fishel, Myrto Kallipoliti and Eleni Tzanaki, Facets of the Generalized Cluster Complex and Regions in the Extended Catalan Arrangement of Type A, The electronic Journal of Combinatorics 20(4) (2013), #P7.
  • D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence, J. Comb Thy A 80 380-384 1997.
  • H. G. Forder, Some problems in combinatorics, Math. Gazette, vol. 45, 1961, 199-201.
  • Fürlinger, J.; Hofbauer, J., q-Catalan numbers. J. Combin. Theory Ser. A 40 (1985), no. 2, 248-264. MR0814413 (87e:05017)
  • M. Gardner, Time Travel and Other Mathematical Bewilderments, Chap. 20 pp. 253-266, W. H. Freeman NY 1988.
  • James Gleick, Faster, Vintage Books, NY, 2000 (see pp. 259-261).
  • M. C. Golumbic and A. N. Trenk, Tolerance graphs, Vol. 89, Cambridge University Press, 2004, pp. 32.
  • S Goodenough, C Lavault, Overview on Heisenberg—Weyl Algebra and Subsets of Riordan Subgroups, The Electronic Journal of Combinatorics, 22(4) (2015), #P4.16,
  • H. W. Gould, Research bibliography of two special number sequences, Mathematica Monongaliae, Vol. 12, 1971.
  • D. Gouyou-Beauchamps, Chemins sous-diagonaux et tableau de Young, pp. 112-125 of "Combinatoire Enumerative (Montreal 1985)", Lect. Notes Math. 1234, 1986.
  • M. Griffiths, The Backbone of Pascal's Triangle, United Kingdom Mathematics Trust (2008), 53-63 and 85-93.
  • J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 530.
  • N. S. S. Gu, N. Y. Li and T. Mansour, 2-Binary trees: bijections and related issues, Discr. Math., 308 (2008), 1209-1221.
  • R. K. Guy, Dissecting a polygon into triangles, Research Paper #9, Math. Dept., Univ. Calgary, 1967.
  • R. K. Guy and J. L. Selfridge, The nesting and roosting habits of the laddered parenthesis. Amer. Math. Monthly 80 (1973), 868-876.
  • Peter Hajnal and Gabor V. Nagy, A bijective proof of Shapiro's Catalan convolution, Elect. J. Combin., 21 (2014), #P2.42.
  • F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.23).
  • F. Harary, G. Prins, and W. T. Tutte, The number of plane trees. Indag. Math. 26, 319-327, 1964.
  • J. Harris, Algebraic Geometry: A First Course (GTM 133), Springer-Verlag, 1992, pages 245-247.
  • S. Heubach, N. Y. Li and T. Mansour, Staircase tilings and k-Catalan structures, Discrete Math., 308 (2008), 5954-5964.
  • Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
  • Higgins, Peter M. Combinatorial results for semigroups of order-preserving mappings. Math. Proc. Camb. Phil. Soc. (1993), 113: 281-296.
  • B. D. Hughes, Random Walks and Random Environments, Oxford 1995, vol. 1, p. 513, Eq. (7.282).
  • F. Hurtado, M. Noy, Ears of triangulations and Catalan numbers, Discrete Mathematics, Volume 149, Issues 1-3, Feb 22 1996, Pages 319-324.
  • M. Janjic, Determinants and Recurrence Sequences, Journal of Integer Sequences, 2012, Article 12.3.5.
  • R. H. Jeurissen, Raney and Catalan, Discrete Math., 308 (2008), 6298-6307.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 36.
  • Kim, Ki Hang; Rogers, Douglas G.; Roush, Fred W. Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013)
  • Klarner, D. A. A Correspondence Between Sets of Trees. Indag. Math. 31, 292-296, 1969.
  • M. Klazar, On numbers of Davenport-Schinzel sequences, Discr. Math., 185 (1998), 77-87.
  • D. E. Knuth, The Art of Computer Programming, 2nd Edition, Vol. 1, Addison-Wesley, 1973, pp. 238.
  • D. E. Knuth, The Art of Computer Programming, vol. 4A, Combinatorial Algorithms, Section 7.2.1.6 (p. 450).
  • Thomas Koshy and Mohammad Salmassi, "Parity and Primality of Catalan Numbers", College Mathematics Journal, Vol. 37, No. 1 (Jan 2006), pp. 52-53.
  • M. Kosters, A theory of hexaflexagons, Nieuw Archief Wisk., 17 (1999), 349-362.
  • E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.
  • C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., 14 (1922), 55-62, 122-138 and 143-146.
  • P. Lafar and C. T. Long, A combinatorial problem, Amer. Math. Mnthly, 69 (1962), 876-883.
  • Laradji, A. and Umar, A. On certain finite semigroups of order-decreasing transformations I, Semigroup Forum 69 (2004), 184-200.
  • P. J. Larcombe, On pre-Catalan Catalan numbers: Kotelnikow (1766), Mathematics Today, 35 (1999), p. 25.
  • P. J. Larcombe, On the history of the Catalan numbers: a first record in China, Mathematics Today, 35 (1999), p. 89.
  • P. J. Larcombe, The 18th century Chinese discovery of the Catalan numbers, Math. Spectrum, 32 (1999/2000), 5-7.
  • P. J. Larcombe and P. D. C. Wilson, On the trail of the Catalan sequence, Mathematics Today, 34 (1998), 114-117.
  • P. J. Larcombe and P. D. C. Wilson, On the generating function of the Catalan sequence: a historical perspective, Congress. Numer., 149 (2001), 97-108.
  • G. S. Lueker, Some techniques for solving recurrences, Computing Surveys, 12 (1980), 419-436.
  • J. J. Luo, Antu Ming, the first inventor of Catalan numbers in the world [in Chinese], Neimenggu Daxue Xuebao, 19 (1998), 239-245.
  • C. L. Mallows, R. J. Vanderbei, Which Young Tableaux Can Represent an Outer Sum?, Journal of Integer Sequences, Vol. 18, 2015, #15.9.1.
  • Toufik Mansour, Matthias Schork, and Mark Shattuck, Catalan numbers and pattern restricted set partitions. Discrete Math. 312(2012), no. 20, 2979-2991. MR2956089
  • Toufik Mansour and Simone Severini, Enumeration of (k,2)-noncrossing partitions, Discrete Math., 308 (2008), 4570-4577.
  • M. E. Mays and Jerzy Wojciechowski, A determinant property of Catalan numbers. Discrete Math. 211, No. 1-3, 125-133 (2000). Zbl 0945.05037
  • D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344.
  • A. Milicevic and N. Trinajstic, "Combinatorial Enumeration in Chemistry", Chem. Modell., Vol. 4, (2006), pp. 405-469.
  • Miller, Steven J., ed. Benford's Law: Theory and Applications. Princeton University Press, 2015.
  • David Molnar, "Wiggly Games and Burnside's Lemma", Chapter 8, The Mathematics of Various Entertaining Subjects: Volume 3 (2019), Jennifer Beineke & Jason Rosenhouse, eds. Princeton University Press, Princeton and Oxford, p. 102.
  • C. O. Oakley and R. J. Wisner, Flexagons, Amer. Math. Monthly, 64 (1957), 143-154.
  • A. Panholzer and H. Prodinger, Bijections for ternary trees and non-crossing trees, Discrete Math., 250 (2002), 181-195 (see Eq. 4).
  • Papoulis, Athanasios. "A new method of inversion of the Laplace transform."Quart. Appl. Math 14.405-414 (1957): 124.
  • S. G. Penrice, Stacks, bracketings and CG-arrangements, Math. Mag., 72 (1999), 321-324.
  • C. A. Pickover, Wonders of Numbers, Chap. 71, Oxford Univ. Press NY 2000.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
  • G. Pólya, On the number of certain lattice polygons. J. Combinatorial Theory 6 1969 102-105. MR0236031 (38 #4329)
  • C. Pomerance, Divisors of the middle binomial coefficient, Amer. Math. Monthly, 112 (2015), 636-644.
  • Jocelyn Quaintance and Harris Kwong, A combinatorial interpretation of the Catalan and Bell number difference tables, Integers, 13 (2013), #A29.
  • Ronald C. Read, "The Graph Theorists who Count -- and What They Count", in 'The Mathematical Gardner', in D. A. Klarner, Ed., pp. 331-334, Wadsworth CA 1989.
  • J. Riordan, Combinatorial Identities, Wiley, 1968, p. 101.
  • J. Riordan, The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comp., 29 (1975), 215-222.
  • T. Santiago Costa Oliveira, "Catalan traffic" and integrals on the Grassmannian of lines, Discr. Math., 308 (2007), 148-152.
  • A. Sapounakis, I. Tasoulas and P. Tsikouras, Counting strings in Dyck paths, Discrete Math., 307 (2007), 2909-2924.
  • E. Schröder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
  • Shapiro, Louis W. Catalan numbers and "total information" numbers. Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975), pp. 531-539. Congressus Numerantium, No. XIV, Utilitas Math., Winnipeg, Man., 1975. MR0398853 (53 #2704).
  • L. W. Shapiro, A short proof of an identity of Touchard's concerning Catalan numbers, J. Combin. Theory, A 20 (1976), 375-376.
  • L. W. Shapiro and C. J. Wang, Generating identities via 2 X 2 matrices, Congressus Numerantium, 205 (2010), 33-46.
  • L. W. Shapiro, W.-J. Woan and S. Getu, The Catalan numbers via the World Series, Math. Mag., 66 (1993), 20-22.
  • D. M. Silberger, Occurrences of the integer (2n-2)!/n!(n-1)!, Roczniki Polskiego Towarzystwa Math. 13 (1969): 91-96.
  • 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).
  • S. Snover and S. Troyer, Multidimensional Catalan numbers, Abstracts 848-05-94 and 848-05-95, 848th Meeting, Amer. Math. Soc., Worcester Mass., March 15-16, 1989.
  • R. P. Stanley, Enumerative Combinatorics, Wadsworth, Vol. 1, 1986, Vol. 2, 1999; see especially Chapter 6.
  • R. P. Stanley, Recent Progress in Algebraic Combinatorics, Bull. Amer. Math. Soc., 40 (2003), 55-68.
  • Richard P. Stanley, "Catalan Numbers", Cambridge University Press, 2015.
  • J. J. Sylvester, On reducible cyclodes, Coll. Math. Papers, Vol. 2, see especially page 670, where Catalan numbers appear.
  • Thiel, Marko. "A new cyclic sieving phenomenon for Catalan objects." Discrete Mathematics 340.3 (2017): 426-429.
  • I. Vun and P. Belcher, Catalan numbers, Mathematical Spectrum, 30 (1997/1998), 3-5.
  • D. Wells, Penguin Dictionary of Curious and Interesting Numbers, Entry 42 p 121, Penguin Books, 1987.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 41.
  • J. Wuttke, The zig-zag walk with scattering and absorption on the real half line and in a lattice model, J. Phys. A 47 (2014), 215203, 1-9.

Links

Crossrefs

Cf. A000142, A000245, A000344, A000588, A000957, A000984, A001392, A001453, A001791, A002057, A002420, A003046, A003517, A003518, A003519, A006480, A008276, A008549, A014137, A014138, A014140, A022553 (inv. Eul. trans.), A024492, A032357, A032443, A039599, A048990, A059288, A068875, A069640, A086117, A088327 (Eul. trans.), A094216, A094638, A094639, A098597, A099731, A119822, A120304, A124926, A129763, A137697, A154559, A161581, A167892, A167893, A179277, A211611, A275431 (multisets).
A row of A060854.
See A001003, A001190, A001699, A000081 for other ways to count parentheses.
Enumerates objects encoded by A014486.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A051168 (diagonal of the square array described).
Cf. A033552, A176137 (partitions into Catalan numbers).
Cf. A000753, A000736 (Boustrophedon transforms).
Cf. A120303 (largest prime factor of Catalan number).
Cf. A121839 (reciprocal Catalan constant), A268813.
Cf. A038003, A119861, A119908, A120274, A120275 (odd Catalan number).
Cf. A002390 (decimal expansion of natural logarithm of golden ratio).
Coefficients of square root of the g.f. are A001795/A046161.
For a(n) mod 6 see A259667.
For a(n) in base 2 see A264663.
Hankel transforms with first terms omitted: A001477, A006858, A091962, A078920, A123352, A368025.
Cf. A001147, A163960.
Cf. A332602 (conjectured production matrix).
Polyominoes: A001683(n+2) (oriented), A000207 (unoriented), A369314 (chiral), A208355(n-1) (achiral), A001764 {4,oo}.

Programs

  • GAP
    A000108:=List([0..30],n->Binomial(2*n,n)/(n+1)); # Muniru A Asiru, Feb 17 2018
  • Haskell
    import Data.List (genericIndex)
a000108 n = genericIndex a000108_list n
a000108_list = 1 : catalan [1] where
   catalan cs = c : catalan (c:cs) where
      c = sum $ zipWith (*) cs $ reverse cs
-- Reinhard Zumkeller, Nov 12 2011
a000108 = map last $ iterate (scanl1 (+) . (++ [0])) [1]
-- David Spies, Aug 23 2015
  • Magma
    C:= func< n | Binomial(2*n,n)/(n+1) >; [ C(n) : n in [0..60]];
  • Magma
    [Catalan(n): n in [0..40]]; // Vincenzo Librandi, Apr 02 2011
  • Maple
    A000108 := n->binomial(2*n,n)/(n+1);
G000108 := (1 - sqrt(1 - 4*x)) / (2*x);
spec := [ A, {A=Prod(Z,Sequence(A))}, unlabeled ]: [ seq(combstruct[count](spec, size=n+1), n=0..42) ];
with(combstruct): bin := {B=Union(Z,Prod(B,B))}: seq(count([B,bin,unlabeled],size=n+1), n=0..25); # Zerinvary Lajos, Dec 05 2007
gser := series(G000108, x=0, 42): seq(coeff(gser, x, n), n=0..41); # Zerinvary Lajos, May 21 2008
seq((2*n)!*coeff(series(hypergeom([],[2],x^2),x,2*n+2),x,2*n),n=0..30); # Peter Luschny, Jan 31 2015
A000108List := proc(m) local A, P, n; A := [1, 1]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), A[-1]]);
A := [op(A), P[-1]] od; A end: A000108List(31); # Peter Luschny, Mar 24 2022
  • Mathematica
    Table[(2 n)!/n!/(n + 1)!, {n, 0, 20}]
Table[4^n Gamma[n + 1/2]/(Sqrt[Pi] Gamma[n + 2]), {n, 0, 20}] (* Eric W. Weisstein, Oct 31 2024 *)
Table[Hypergeometric2F1[1 - n, -n, 2, 1], {n, 0, 20}] (* Richard L. Ollerton, Sep 13 2006 *)
Table[CatalanNumber @ n, {n, 0, 20}] (* Robert G. Wilson v, Feb 15 2011 *)
CatalanNumber[Range[0, 20]] (* Eric W. Weisstein, Oct 31 2024 *)
CoefficientList[InverseSeries[Series[x/Sum[x^n, {n, 0, 31}], {x, 0, 31}]]/x, x] (* Mats Granvik, Nov 24 2013 *)
CoefficientList[Series[(1 - Sqrt[1 - 4 x])/(2 x), {x, 0, 20}], x] (* Stefano Spezia, Aug 31 2018 *)
  • Maxima
    A000108(n):=binomial(2*n,n)/(n+1)$ makelist(A000108(n),n,0,30); /* Martin Ettl, Oct 24 2012 */
  • MuPAD
    combinat::dyckWords::count(n) $ n = 0..38 // Zerinvary Lajos, Apr 14 2007
  • PARI
    a(n)=binomial(2*n,n)/(n+1) \\ M. F. Hasler, Aug 25 2012
  • PARI
    a(n) = (2*n)! / n! / (n+1)!
  • PARI
    a(n) = my(A, m); if( n<0, 0, m=1; A = 1 + x + O(x^2); while(m<=n, m*=2; A = sqrt(subst(A, x, 4*x^2)); A += (A - 1) / (2*x*A)); polcoeff(A, n));
  • PARI
    {a(n) = if( n<1, n==0, polcoeff( serreverse( x / (1 + x)^2 + x * O(x^n)), n))}; /* Michael Somos */
  • PARI
    (recur(a,b)=if(b<=2,(a==2)+(a==b)+(a!=b)*(1+a/2), (1+a/b)*recur(a,b-1))); a(n)=recur(n,n); \\ R. J. Cano, Nov 22 2012
  • PARI
    x='x+O('x^40); Vec((1-sqrt(1-4*x))/(2*x)) \\ Altug Alkan, Oct 13 2015
  • Python
    from gmpy2 import divexact
A000108 = [1, 1]
for n in range(1, 10**3):
    A000108.append(divexact(A000108[-1]*(4*n+2),(n+2))) # Chai Wah Wu, Aug 31 2014
  • Python
    # Works in Sage also.
A000108 = [1]
for n in range(1000):
    A000108.append(A000108[-1]*(4*n+2)//(n+2)) # Günter Rote, Nov 08 2023
  • Sage
    [catalan_number(i) for i in range(27)] # Zerinvary Lajos, Jun 26 2008
  • Sage
    # Generalized algorithm of L. Seidel
def A000108_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = True; h = 1; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1; R.append(D[1])
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
    return R
A000108_list(31) # Peter Luschny, Jun 02 2012

Formula

a(n) = binomial(2*n, n)/(n+1) = (2*n)!/(n!*(n+1)!) = A000984(n)/(n+1).
Recurrence: a(n) = 2*(2*n-1)*a(n-1)/(n+1) with a(0) = 1.
Recurrence: a(n) = Sum_{k=0..n-1} a(k)a(n-1-k).
G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x), and satisfies A(x) = 1 + x*A(x)^2.
a(n) = Product_{k=2..n} (1 + n/k).
a(n+1) = Sum_{i} binomial(n, 2*i)*2^(n-2*i)*a(i). - Touchard
It is known that a(n) is odd if and only if n=2^k-1, k=0, 1, 2, 3, ... - Emeric Deutsch, Aug 04 2002, corrected by M. F. Hasler, Nov 08 2015
Using the Stirling approximation in A000142 we get the asymptotic expansion a(n) ~ 4^n / (sqrt(Pi * n) * (n + 1)). - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 13 2001
Integral representation: a(n) = (1/(2*Pi))*Integral_{x=0..4} x^n*sqrt((4-x)/x). - Karol A. Penson, Apr 12 2001
E.g.f.: exp(2*x)*(I_0(2*x)-I_1(2*x)), where I_n is Bessel function. - Karol A. Penson, Oct 07 2001
a(n) = polygorial(n, 6)/polygorial(n, 3). - Daniel Dockery (peritus(AT)gmail.com), Jun 24 2003
G.f. A(x) satisfies ((A(x) + A(-x)) / 2)^2 = A(4*x^2). - Michael Somos, Jun 27 2003
G.f. A(x) satisfies Sum_{k>=1} k(A(x)-1)^k = Sum_{n>=1} 4^{n-1}*x^n. - Shapiro, Woan, Getu
a(n+m) = Sum_{k} A039599(n, k)*A039599(m, k). - Philippe Deléham, Dec 22 2003
a(n+1) = (1/(n+1))*Sum_{k=0..n} a(n-k)*binomial(2k+1, k+1). - Philippe Deléham, Jan 24 2004
a(n) = Sum_{k>=0} A008313(n, k)^2. - Philippe Deléham, Feb 14 2004
a(m+n+1) = Sum_{k>=0} A039598(m, k)*A039598(n, k). - Philippe Deléham, Feb 15 2004
a(n) = Sum_{k=0..n} (-1)^k*2^(n-k)*binomial(n, k)*binomial(k, floor(k/2)). - Paul Barry, Jan 27 2005
Sum_{n>=0} 1/a(n) = 2 + 4*Pi/3^(5/2) = F(1,2;1/2;1/4) = A268813 = 2.806133050770763... (see L'Univers de Pi link). - Gerald McGarvey and Benoit Cloitre, Feb 13 2005
a(n) = Sum_{k=0..floor(n/2)} ((n-2*k+1)*binomial(n, n-k)/(n-k+1))^2, which is equivalent to: a(n) = Sum_{k=0..n} A053121(n, k)^2, for n >= 0. - Paul D. Hanna, Apr 23 2005
a((m+n)/2) = Sum_{k>=0} A053121(m, k)*A053121(n, k) if m+n is even. - Philippe Deléham, May 26 2005
E.g.f. Sum_{n>=0} a(n) * x^(2*n) / (2*n)! = BesselI(1, 2*x) / x. - Michael Somos, Jun 22 2005
Given g.f. A(x), then B(x) = x * A(x^3) satisfies 0 = f(x, B(X)) where f(u, v) = u - v + (u*v)^2 or B(x) = x + (x * B(x))^2 which implies B(-B(x)) = -x and also (1 + B^3) / B^2 = (1 - x^3) / x^2. - Michael Somos, Jun 27 2005
a(n) = a(n-1)*(4-6/(n+1)). a(n) = 2a(n-1)*(8a(n-2)+a(n-1))/(10a(n-2)-a(n-1)). - Franklin T. Adams-Watters, Feb 08 2006
Sum_{k>=1} a(k)/4^k = 1. - Franklin T. Adams-Watters, Jun 28 2006
a(n) = A047996(2*n+1, n). - Philippe Deléham, Jul 25 2006
Binomial transform of A005043. - Philippe Deléham, Oct 20 2006
a(n) = Sum_{k=0..n} (-1)^k*A116395(n,k). - Philippe Deléham, Nov 07 2006
a(n) = (1/(s-n))*Sum_{k=0..n} (-1)^k (k+s-n)*binomial(s-n,k) * binomial(s+n-k,s) with s a nonnegative free integer [H. W. Gould].
a(k) = Sum_{i=1..k} |A008276(i,k)| * (k-1)^(k-i) / k!. - André F. Labossière, May 29 2007
a(n) = Sum_{k=0..n} A129818(n,k) * A007852(k+1). - Philippe Deléham, Jun 20 2007
a(n) = Sum_{k=0..n} A109466(n,k) * A127632(k). - Philippe Deléham, Jun 20 2007
Row sums of triangle A124926. - Gary W. Adamson, Oct 22 2007
Limit_{n->oo} (1 + Sum_{k=0..n} a(k)/A004171(k)) = 4/Pi. - Reinhard Zumkeller, Aug 26 2008
a(n) = Sum_{k=0..n} A120730(n,k)^2 and a(k+1) = Sum_{n>=k} A120730(n,k). - Philippe Deléham, Oct 18 2008
Given an integer t >= 1 and initial values u = [a_0, a_1, ..., a_{t-1}], we may define an infinite sequence Phi(u) by setting a_n = a_{n-1} + a_0*a_{n-1} + a_1*a_{n-2} + ... + a_{n-2}*a_1 for n >= t. For example, the present sequence is Phi([1]) (also Phi([1,1])). - Gary W. Adamson, Oct 27 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) and l_(i+1) <> 0 for i=1..n-1 and delta(l_1,l_2,...,l_i,...,l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
a(n) = A000680(n)/A006472(n+1). - Mark Dols, Jul 14 2010; corrected by M. F. Hasler, Nov 08 2015
Let A(x) be the g.f., then B(x)=x*A(x) satisfies the differential equation B'(x)-2*B'(x)*B(x)-1=0. - Vladimir Kruchinin, Jan 18 2011
Complement of A092459; A010058(a(n)) = 1. - Reinhard Zumkeller, Mar 29 2011
G.f.: 1/(1-x/(1-x/(1-x/(...)))) (continued fraction). - Joerg Arndt, Mar 18 2011
With F(x) = (1-2*x-sqrt(1-4*x))/(2*x) an o.g.f. in x for the Catalan series, G(x) = x/(1+x)^2 is the compositional inverse of F (nulling the n=0 term). - Tom Copeland, Sep 04 2011
With H(x) = 1/(dG(x)/dx) = (1+x)^3 / (1-x), the n-th Catalan number is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)), and H(x) is the o.g.f. for A115291. - Tom Copeland, Sep 04 2011
From Tom Copeland, Sep 30 2011: (Start)
With F(x) = (1-sqrt(1-4*x))/2 an o.g.f. in x for the Catalan series, G(x)= x*(1-x) is the compositional inverse and this relates the Catalan numbers to the row sums of A125181.
With H(x) = 1/(dG(x)/dx) = 1/(1-2x), the n-th Catalan number (offset 1) is given by (1/n!)*((H(x)*d/dx)^n)x evaluated at x=0, i.e., F(x) = exp(x*H(u)*d/du)u, evaluated at u = 0. Also, dF(x)/dx = H(F(x)). (End)
G.f.: (1-sqrt(1-4*x))/(2*x) = G(0) where G(k) = 1 + (4*k+1)*x/(k+1-2*x*(k+1)*(4*k+3)/(2*x*(4*k+3)+(2*k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2011
E.g.f.: exp(2*x)*(BesselI(0,2*x) - BesselI(1,2*x)) = G(0) where G(k) = 1 + (4*k+1)*x/((k+1)*(2*k+1)-x*(k+1)*(2*k+1)*(4*k+3)/(x*(4*k+3)+(k+1)*(2*k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Nov 30 2011
E.g.f.: Hypergeometric([1/2],[2],4*x) which coincides with the e.g.f. given just above, and also by Karol A. Penson further above. - Wolfdieter Lang, Jan 13 2012
A076050(a(n)) = n + 1 for n > 0. - Reinhard Zumkeller, Feb 17 2012
a(n) = A208355(2*n-1) = A208355(2*n) for n > 0. - Reinhard Zumkeller, Mar 04 2012
a(n+1) = A214292(2*n+1,n) = A214292(2*n+2,n). - Reinhard Zumkeller, Jul 12 2012
G.f.: 1 + 2*x/(U(0)-2*x) where U(k) = k*(4*x+1) + 2*x + 2 - x*(2*k+3)*(2*k+4)/U(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Sep 20 2012
G.f.: hypergeom([1/2,1],[2],4*x). - Joerg Arndt, Apr 06 2013
Special values of Jacobi polynomials, in Maple notation: a(n) = 4^n*JacobiP(n,1,-1/2-n,-1)/(n+1). - Karol A. Penson, Jul 28 2013
For n > 0: a(n) = sum of row n in triangle A001263. - Reinhard Zumkeller, Oct 10 2013
a(n) = binomial(2n,n-1)/n and a(n) mod n = binomial(2n,n) mod n = A059288(n). - Jonathan Sondow, Dec 14 2013
a(n-1) = Sum_{t1+2*t2+...+n*tn=n} (-1)^(1+t1+t2+...+tn)*multinomial(t1+t2 +...+tn,t1,t2,...,tn)*a(1)^t1*a(2)^t2*...*a(n)^tn. - Mircea Merca, Feb 27 2014
a(n) = Sum_{k=1..n} binomial(n+k-1,n)/n if n > 0. Alexander Adamchuk, Mar 25 2014
a(n) = -2^(2*n+1) * binomial(n-1/2, -3/2). - Peter Luschny, May 06 2014
a(n) = (4*A000984(n) - A000984(n+1))/2. - Stanislav Sykora, Aug 09 2014
a(n) = A246458(n) * A246466(n). - Tom Edgar, Sep 02 2014
a(n) = (2*n)!*[x^(2*n)]hypergeom([],[2],x^2). - Peter Luschny, Jan 31 2015
a(n) = 4^(n-1)*hypergeom([3/2, 1-n], [3], 1). - Peter Luschny, Feb 03 2015
a(2n) = 2*A000150(2n); a(2n+1) = 2*A000150(2n+1) + a(n). - John Bodeen, Jun 24 2015
a(n) = Sum_{t=1..n+1} n^(t-1)*abs(Stirling1(n+1, t)) / Sum_{t=1..n+1} abs(Stirling1(n+1, t)), for n > 0, see (10) in Cereceda link. - Michel Marcus, Oct 06 2015
a(n) ~ 4^(n-2)*(128 + 160/N^2 + 84/N^4 + 715/N^6 - 10180/N^8)/(N^(3/2)*Pi^(1/2)) where N = 4*n+3. - Peter Luschny, Oct 14 2015
a(n) = Sum_{k=1..floor((n+1)/2)} (-1)^(k-1)*binomial(n+1-k,k)*a(n-k) if n > 0; and a(0) = 1. - David Pasino, Jun 29 2016
Sum_{n>=0} (-1)^n/a(n) = 14/25 - 24*arccsch(2)/(25*sqrt(5)) = 14/25 - 24*A002390/(25*sqrt(5)) = 0.353403708337278061333... - Ilya Gutkovskiy, Jun 30 2016
C(n) = (1/n) * Sum_{i+j+k=n-1} C(i)*C(j)*C(k)*(k+1), n >= 1. - Yuchun Ji, Feb 21 2016
C(n) = 1 + Sum_{i+j+kYuchun Ji, Sep 01 2016
a(n) = A001700(n) - A162551(n) = binomial(2*n+1,n+1). - 2*binomial(2*n,n-1). - Taras Goy, Aug 09 2018
G.f.: A(x) = (1 - sqrt(1 - 4*x)) / (2*x) = 2F1(1/2,1;2;4*x). G.f. A(x) satisfies A = 1 + x*A^2. - R. J. Mathar, Nov 17 2018
C(n) = 1 + Sum_{i=0..n-1} A000245(i). - Yuchun Ji, Jan 10 2019
From A.H.M. Smeets, Apr 11 2020: (Start)
(1+sqrt(1+4*x))/2 = 1-Sum_{i >= 0} a(i)*(-x)^(i+1), for any complex x with |x| < 1/4; and sqrt(x+sqrt(x+sqrt(x+...))) = 1-Sum_{i >= 0} a(i)*(-x)^(i+1), for any complex x with |x| < 1/4 and x <> 0. (End)
a(3n+1)*a(5n+4)*a(15n+10) = a(3n+2)*a(5n+2)*a(15n+11). The first case of Catalan product equation of a triple partition of 23n+15. - Yuchun Ji, Sep 27 2020
a(n) = 4^n * (-1)^(n+1) * 3F2[{n + 1,n + 1/2,n}, {3/2,1}, -1], n >= 1. - Sergii Voloshyn, Oct 22 2020
a(n) = 2^(1 + 2 n) * (-1)^(n)/(1 + n) * 3F2[{n, 1/2 + n, 1 + n}, {1/2, 1}, -1], n >= 1. - Sergii Voloshyn, Nov 08 2020
a(n) = (1/Pi)*4^(n+1)*Integral_{x=0..Pi/2} cos(x)^(2*n)*sin(x)^2 dx. - Greg Dresden, May 30 2021
From Peter Bala, Aug 17 2021: (Start)
G.f. A(x) satisfies A(x) = 1/sqrt(1 - 4*x) * A( -x/(1 - 4*x) ) and (A(x) + A(-x))/2 = 1/sqrt(1 - 4*x) * A( -2*x/(1 - 4*x) ); these are the cases k = 0 and k = -1 of the general formula 1/sqrt(1 - 4*x) * A( (k-1)*x/(1 - 4*x) ) = Sum_{n >= 0} ((k^(n+1) - 1)/(k - 1))*Catalan(n)*x^n.
2 - sqrt(1 - 4*x)/A( k*x/(1 - 4*x) ) = 1 + Sum_{n >= 1} (1 + (k + 1)^n) * Catalan(n-1)*x^n. (End)
Sum_{n>=0} a(n)*(-1/4)^n = 2*(sqrt(2)-1) (A163960). - Amiram Eldar, Mar 22 2022
0 = a(n)*(16*a(n+1) - 10*a(n+2)) + a(n+1)*(2*a(n+1) + a(n+2)) for all n>=0. - Michael Somos, Dec 12 2022
G.f.: (offset 1) 1/G(x), with G(x) = 1 - 2*x - x^2/G(x) (Jacobi continued fraction). - Nikolaos Pantelidis, Feb 01 2023
a(n) = K^(2n+1, n, 1) for all n >= 0, where K^(n, s, x) is the Krawtchouk polynomial defined to be Sum_{k=0..s} (-1)^k * binomial(n-x, s-k) * binomial(x, k). - Vladislav Shubin, Aug 17 2023
From Peter Bala, Feb 03 2024: (Start)
The g.f. A(x) satisfies the following functional equations:
A(x) = 1 + x/(1 - 4*x) * A(-x/(1 - 4*x))^2,
A(x^2) = 1/(1 - 2*x) * A(- x/(1 - 2*x))^2 and, for arbitrary k,
1/(1 - k*x) * A(x/(1 - k*x))^2 = 1/(1 - (k+4)*x) * A(-x/(1 - (k+4)*x))^2. (End)
a(n) = A363448(n) + A363449(n). - Julien Rouyer, Jun 28 2024

A001147 Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).

Original entry on oeis.org

1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075, 13749310575, 316234143225, 7905853580625, 213458046676875, 6190283353629375, 191898783962510625, 6332659870762850625, 221643095476699771875, 8200794532637891559375, 319830986772877770815625
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

The solution to Schröder's third problem.
Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085).
a(n-2) is the number of full Steiner topologies on n points with n-2 Steiner points. [corrected by Lyle Ramshaw, Jul 20 2022]
a(n) is also the number of perfect matchings in the complete graph K(2n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001
Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired). - Bartosz Zoltak, Oct 16 2012
For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001
a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy).
a(n) = E(X^(2n)), where X is a standard normal random variable (i.e., X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004
Second Eulerian transform of 1,1,1,1,1,1,... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} E(n,k)s(k), where E(n,k) is a second-order Eulerian number (A008517). - Ross La Haye, Feb 13 2005
Integral representation as n-th moment of a positive function on the positive axis: a(n) = Integral_{x=0..oo} x^n*exp(-x/2)/sqrt(2*Pi*x) dx, n >= 0. - Karol A. Penson, Oct 10 2005
a(n) is the number of binary total partitions of n+1 (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with n+1 labeled leaves (Stanley, ex 5.2.6). - Mitch Harris, Aug 01 2006
a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for iDavid Callan, Sep 25 2006
a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan, Oct 26 2006
Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, Nov 24 2006
a(n) = total weight of all Dyck n-paths (A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan, Dec 29 2006
a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials (A000142) and increasing quaternary trees by triple factorials (A007559). - David Callan, Mar 30 2007
From Tom Copeland, Nov 13 2007, clarified in first and extended in second paragraph, Jun 12 2021: (Start)
a(n) has the e.g.f. (1-2x)^(-1/2) = 1 + x + 3*x^2/2! + ..., whose reciprocal is (1-2x)^(1/2) = 1 - x - x^2/2! - 3*x^3/3! - ... = b(0) - b(1)*x - b(2)*x^2/2! - ... with b(0) = 1 and b(n+1) = -a(n) otherwise. By the formalism of A133314, Sum_{k=0..n} binomial(n,k)*b(k)*a(n-k) = 0^n where 0^0 := 1. In this sense, the sequence a(n) is essentially self-inverse. See A132382 for an extension of this result. See A094638 for interpretations.
This sequence aerated has the e.g.f. e^(t^2/2) = 1 + t^2/2! + 3*t^4/4! + ... = c(0) + c(1)*t + c(2)*t^2/2! + ... and the reciprocal e^(-t^2/2); therefore, Sum_{k=0..n} cos(Pi k/2)*binomial(n,k)*c(k)*c(n-k) = 0^n; i.e., the aerated sequence is essentially self-inverse. Consequently, Sum_{k=0..n} (-1)^k*binomial(2n,2k)*a(k)*a(n-k) = 0^n. (End)
From Ross Drewe, Mar 16 2008: (Start)
This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e., arrangements which are the same after permutations of the labels are equivalent.
If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels.
For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], ..., [332211] }.
By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}
Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End)
A139541(n) = a(n) * a(2*n). - Reinhard Zumkeller, Apr 25 2008
a(n+1) = Sum_{j=0..n} A074060(n,j) * 2^j. - Tom Copeland, Sep 01 2008
From Emeric Deutsch, Jun 05 2009: (Start)
a(n) is the number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.
a(n) = Sum_{k>=0} k*A079267(n,k).
(End)
Hankel transform is A137592. - Paul Barry, Sep 18 2009
(1, 3, 15, 105, ...) = INVERT transform of A000698 starting (1, 2, 10, 74, ...). - Gary W. Adamson, Oct 21 2009
a(n) = (-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomial. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2) = Sum_{i>=0} H(i,x)*t^i/i!. - Leonid Bedratyuk, Oct 31 2009
The Hankel transform of a(n+1) is A168467. - Paul Barry, Dec 04 2009
Partial products of odd numbers. - Juri-Stepan Gerasimov, Oct 17 2010
See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011
a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. - Dennis P. Walsh, Dec 02 2011
a(n) is the leading coefficient of the Bessel polynomial y_n(x) (cf. A001498). - Leonid Bedratyuk, Jun 01 2012
For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013
a(n) is also the numerator of the mean value from 0 to Pi/2 of sin(x)^(2n). - Jean-François Alcover, Jun 13 2013
a(n) is the size of the Brauer monoid on 2n points (see A227545). - James Mitchell, Jul 28 2013
For n>1: a(n) is the numerator of M(n)/M(1) where the numbers M(i) have the property that M(n+1)/M(n) ~ n-1/2 (for example, large Kendell-Mann numbers, see A000140 or A181609, as n --> infinity). - Mikhail Gaichenkov, Jan 14 2014
a(n) = the number of upper-triangular matrix representations required for the symbolic representation of a first order central moment of the multivariate normal distribution of dimension 2(n-1), i.e., E[X_1*X_2...*X_(2n-2)|mu=0, Sigma]. See vignette for symmoments R package on CRAN and Phillips reference below. - Kem Phillips, Aug 10 2014
For n>1: a(n) is the number of Feynman diagrams of order 2n (number of internal vertices) for the vacuum polarization with one charged loop only, in quantum electrodynamics. - Robert Coquereaux, Sep 15 2014
Aerated with intervening zeros (1,0,1,0,3,...) = a(n) (cf. A123023), the e.g.f. is e^(t^2/2), so this is the base for the Appell sequence A099174 with e.g.f. e^(t^2/2) e^(x*t) = exp(P(.,x),t) = unsigned A066325(x,t), the probabilist's (or normalized) Hermite polynomials. P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for A066325(x,t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), where UP(n,t) are the polynomials of A066325 and, e.g., (P(.,t))^n = P(n,t). - Tom Copeland, Nov 15 2014
a(n) = the number of relaxed compacted binary trees of right height at most one of size n. A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. The number of unbounded relaxed compacted binary trees of size n is A082161(n). See the Genitrini et al. link. - Michael Wallner, Jun 20 2017
Also the number of distinct adjacency matrices in the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017
From Christopher J. Smyth, Jan 26 2018: (Start)
a(n) = the number of essentially different ways of writing a probability distribution taking n+1 values as a sum of products of binary probability distributions. See comment of Mitch Harris above. This is because each such way corresponds to a full binary tree with n+1 leaves, with the leaves labeled by the values. (This comment is due to Niko Brummer.)
Also the number of binary trees with root labeled by an (n+1)-set S, its n+1 leaves by the singleton subsets of S, and other nodes labeled by subsets T of S so that the two daughter nodes of the node labeled by T are labeled by the two parts of a 2-partition of T. This also follows from Mitch Harris' comment above, since the leaf labels determine the labels of the other vertices of the tree.
(End)
a(n) is the n-th moment of the chi-squared distribution with one degree of freedom (equivalent to Coleman's Apr 06 2004 comment). - Bryan R. Gillespie, Mar 07 2021
Let b(n) = 0 for n odd and b(2k) = a(k); i.e., let the sequence b(n) be an aerated version of this entry. After expanding the differential operator (x + D)^n and normal ordering the resulting terms, the integer coefficient of the term x^k D^m is n! b(n-k-m) / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n. E.g., (x+D)^2 = x^2 + 2xD + D^2 + 1 with D = d/dx. The result generalizes to the raising (R) and lowering (L) operators of any Sheffer polynomial sequence by replacing x by R and D by L and follows from the disentangling relation e^{t(L+R)} = e^{t^2/2} e^{tR} e^{tL}. Consequently, these are also the coefficients of the reordered 2^n permutations of the binary symbols L and R under the condition LR = RL + 1. E.g., (L+R)^2 = LL + LR + RL + RR = LL + 2RL + RR + 1. (Cf. A344678.) - Tom Copeland, May 25 2021
From Tom Copeland, Jun 14 2021: (Start)
Lando and Zvonkin present several scenarios in which the double factorials occur in their role of enumerating perfect matchings (pairings) and as the nonzero moments of the Gaussian e^(x^2/2).
Speyer and Sturmfels (p. 6) state that the number of facets of the abstract simplicial complex known as the tropical Grassmannian G'''(2,n), the space of phylogenetic T_n trees (see A134991), or Whitehouse complex is a shifted double factorial.
These are also the unsigned coefficients of the x[2]^m terms in the partition polynomials of A134685 for compositional inversion of e.g.f.s, a refinement of A134991.
a(n)*2^n = A001813(n) and A001813(n)/(n+1)! = A000108(n), the Catalan numbers, the unsigned coefficients of the x[2]^m terms in the partition polynomials A133437 for compositional inversion of o.g.f.s, a refinement of A033282, A126216, and A086810. Then the double factorials inherit a multitude of analytic and combinatoric interpretations from those of the Catalan numbers, associahedra, and the noncrossing partitions of A134264 with the Catalan numbers as unsigned-row sums. (End)
Connections among the Catalan numbers A000108, the odd double factorials, values of the Riemann zeta function and its derivative for integer arguments, and series expansions of the reduced action for the simple harmonic oscillator and the arc length of the spiral of Archimedes are given in the MathOverflow post on the Riemann zeta function. - Tom Copeland, Oct 02 2021
b(n) = a(n) / (n! 2^n) = Sum_{k = 0..n} (-1)^n binomial(n,k) (-1)^k a(k) / (k! 2^k) = (1-b.)^n, umbrally; i.e., the normalized double factorial a(n) is self-inverse under the binomial transform. This can be proved by applying the Euler binomial transformation for o.g.f.s Sum_{n >= 0} (1-b.)^n x^n = (1/(1-x)) Sum_{n >= 0} b_n (x / (x-1))^n to the o.g.f. (1-x)^{-1/2} = Sum_{n >= 0} b_n x^n. Other proofs are suggested by the discussion in Watson on pages 104-5 of transformations of the Bessel functions of the first kind with b(n) = (-1)^n binomial(-1/2,n) = binomial(n-1/2,n) = (2n)! / (n! 2^n)^2. - Tom Copeland, Dec 10 2022

Examples

			a(3) = 1*3*5 = 15.
From _Joerg Arndt_, Sep 10 2013: (Start)
There are a(3)=15 involutions of 6 elements without fixed points:
  #:    permutation           transpositions
  01:  [ 1 0 3 2 5 4 ]      (0, 1) (2, 3) (4, 5)
  02:  [ 1 0 4 5 2 3 ]      (0, 1) (2, 4) (3, 5)
  03:  [ 1 0 5 4 3 2 ]      (0, 1) (2, 5) (3, 4)
  04:  [ 2 3 0 1 5 4 ]      (0, 2) (1, 3) (4, 5)
  05:  [ 2 4 0 5 1 3 ]      (0, 2) (1, 4) (3, 5)
  06:  [ 2 5 0 4 3 1 ]      (0, 2) (1, 5) (3, 4)
  07:  [ 3 2 1 0 5 4 ]      (0, 3) (1, 2) (4, 5)
  08:  [ 3 4 5 0 1 2 ]      (0, 3) (1, 4) (2, 5)
  09:  [ 3 5 4 0 2 1 ]      (0, 3) (1, 5) (2, 4)
  10:  [ 4 2 1 5 0 3 ]      (0, 4) (1, 2) (3, 5)
  11:  [ 4 3 5 1 0 2 ]      (0, 4) (1, 3) (2, 5)
  12:  [ 4 5 3 2 0 1 ]      (0, 4) (1, 5) (2, 3)
  13:  [ 5 2 1 4 3 0 ]      (0, 5) (1, 2) (3, 4)
  14:  [ 5 3 4 1 2 0 ]      (0, 5) (1, 3) (2, 4)
  15:  [ 5 4 3 2 1 0 ]      (0, 5) (1, 4) (2, 3)
(End)
G.f. = 1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + 135135*x^7 + ...

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, (26.2.28).
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 317.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228, #19.
  • Hoel, Port and Stone, Introduction to Probability Theory, Section 7.3.
  • F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.
  • C. Itzykson and J.-B. Zuber, Quantum Field Theory, McGraw-Hill, 1980, pages 466-467.
  • 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. 2, 1999; see Example 5.2.6 and also p. 178.
  • R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, New York, 1999, p. 73.
  • G. Watson, The Theory of Bessel Functions, Cambridge Univ. Press, 1922.

Links

Crossrefs

Cf. A000085, A006882, A000165 ((2n)!!), A001818, A009445, A039683, A102992, A001190 (no labels), A000680, A132101.
Cf. A086677; A055142 (for this sequence, |a(n+1)| + 1 is the number of distinct products which can be formed using commutative, nonassociative multiplication and a nonempty subset of n given variables).
Constant terms of polynomials in A098503. First row of array A099020.
Cf. A079267, A000698, A029635, A161198, A076795, A123023, A161124, A051125, A181983, A099174, A087547, A028338 (first column).
Subsequence of A248652.
Cf. A082161 (relaxed compacted binary trees of unbounded right height).
Cf. A053871 (binomial transform).
Cf. A000108, A001813, A033282, A060540, A086810, A094638, A126216, A133437, A134264, A134685, A134991, A344678.

Programs

  • GAP
    A001147 := function(n) local i, s, t; t := 1; i := 0; Print(t, ", "); for i in [1 .. n] do t := t*(2*i-1); Print(t, ", "); od; end; A001147(100); # Stefano Spezia, Nov 13 2018
  • Haskell
    a001147 n = product [1, 3 .. 2 * n - 1]
a001147_list = 1 : zipWith (*) [1, 3 ..] a001147_list
-- Reinhard Zumkeller, Feb 15 2015, Dec 03 2011
  • Magma
    A001147:=func< n | n eq 0 select 1 else &*[ k: k in [1..2*n-1 by 2] ] >; [ A001147(n): n in [0..20] ]; // Klaus Brockhaus, Jun 22 2011
  • Magma
    I:=[1,3]; [1] cat [n le 2 select I[n]  else (3*n-2)*Self(n-1)-(n-1)*(2*n-3)*Self(n-2): n in [1..25] ]; // Vincenzo Librandi, Feb 19 2015
  • Maple
    f := n->(2*n)!/(n!*2^n);
A001147 := proc(n) doublefactorial(2*n-1); end: # R. J. Mathar, Jul 04 2009
A001147 := n -> 2^n*pochhammer(1/2, n); # Peter Luschny, Aug 09 2009
G(x):=(1-2*x)^(-1/2): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n],n=0..19); # Zerinvary Lajos, Apr 03 2009; aligned with offset by Johannes W. Meijer, Aug 11 2009
series(hypergeom([1,1/2],[],2*x),x=0,20); # Mark van Hoeij, Apr 07 2013
  • Mathematica
    Table[(2 n - 1)!!, {n, 0, 19}] (* Robert G. Wilson v, Oct 12 2005 *)
a[ n_] := 2^n Gamma[n + 1/2] / Gamma[1/2]; (* Michael Somos, Sep 18 2014 *)
Join[{1}, Range[1, 41, 2]!!] (* Harvey P. Dale, Jan 28 2017 *)
a[ n_] := If[ n < 0, (-1)^n / a[-n], SeriesCoefficient[ Product[1 - (1 - x)^(2 k - 1), {k, n}], {x, 0, n}]]; (* Michael Somos, Jun 27 2017 *)
(2 Range[0, 20] - 1)!! (* Eric W. Weisstein, Jul 22 2017 *)
  • Maxima
    a(n):=if n=0 then 1 else sum(sum(binomial(n-1,i)*binomial(n-i-1,j)*a(i)*a(j)*a(n-i-j-1),j,0,n-i-1),i,0,n-1); /* Vladimir Kruchinin, May 06 2020 */
  • PARI
    {a(n) = if( n<0, (-1)^n / a(-n), (2*n)! / n! / 2^n)}; /* Michael Somos, Sep 18 2014 */
  • PARI
    x='x+O('x^33); Vec(serlaplace((1-2*x)^(-1/2))) \\ Joerg Arndt, Apr 24 2011
  • Python
    from sympy import factorial2
def a(n): return factorial2(2 * n - 1)
print([a(n) for n in range(101)])  # Indranil Ghosh, Jul 22 2017
  • Sage
    [rising_factorial(n+1,n)/2^n for n in (0..15)] # Peter Luschny, Jun 26 2012

Formula

E.g.f.: 1 / sqrt(1 - 2*x).
D-finite with recurrence: a(n) = a(n-1)*(2*n-1) = (2*n)!/(n!*2^n) = A010050(n)/A000165(n).
a(n) ~ sqrt(2) * 2^n * (n/e)^n.
Rational part of numerator of Gamma(n+1/2): a(n) * sqrt(Pi) / 2^n = Gamma(n+1/2). - Yuriy Brun, Ewa Dominowska (brun(AT)mit.edu), May 12 2001
With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - Paul Barry, Jun 27 2003
The Ramanujan polynomial psi(n+1, n) has value a(n). - Ralf Stephan, Apr 16 2004
a(n) = Sum_{k=0..n} (-2)^(n-k)*A048994(n, k). - Philippe Deléham, Oct 29 2005
Log(1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + ...) = x + 5/2*x^2 + 37/3*x^3 + 353/4*x^4 + 4081/5*x^5 + 55205/6*x^6 + ..., where [1, 5, 37, 353, 4081, 55205, ...] = A004208. - Philippe Deléham, Jun 20 2006
1/3 + 2/15 + 3/105 + ... = 1/2. [Jolley eq. 216]
Sum_{j=1..n} j/a(j+1) = (1 - 1/a(n+1))/2. [Jolley eq. 216]
1/1 + 1/3 + 2/15 + 6/105 + 24/945 + ... = Pi/2. - Gary W. Adamson, Dec 21 2006
a(n) = (1/sqrt(2*Pi))*Integral_{x>=0} x^n*exp(-x/2)/sqrt(x). - Paul Barry, Jan 28 2008
a(n) = A006882(2n-1). - R. J. Mathar, Jul 04 2009
G.f.: 1/(1-x-2x^2/(1-5x-12x^2/(1-9x-30x^2/(1-13x-56x^2/(1- ... (continued fraction). - Paul Barry, Sep 18 2009
a(n) = (-1)^n*subs({log(e)=1,x=0},coeff(simplify(series(e^(x*t-t^2/2),t,2*n+1)),t^(2*n))*(2*n)!). - Leonid Bedratyuk, Oct 31 2009
a(n) = 2^n*gamma(n+1/2)/gamma(1/2). - Jaume Oliver Lafont, Nov 09 2009
G.f.: 1/(1-x/(1-2x/(1-3x/(1-4x/(1-5x/(1- ...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
The g.f. of a(n+1) is 1/(1-3x/(1-2x/(1-5x/(1-4x/(1-7x/(1-6x/(1-.... (continued fraction). - Paul Barry, Dec 04 2009
a(n) = Sum_{i=1..n} binomial(n,i)*a(i-1)*a(n-i). - Vladimir Shevelev, Sep 30 2010
E.g.f.: A(x) = 1 - sqrt(1-2*x) satisfies the differential equation A'(x) - A'(x)*A(x) - 1 = 0. - Vladimir Kruchinin, Jan 17 2011
a(n) = A123023(2*n). - Michael Somos, Jul 24 2011
a(n) = (1/2)*Sum_{i=1..n} binomial(n+1,i)*a(i-1)*a(n-i). See link above. - Dennis P. Walsh, Dec 02 2011
a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n,n+k)*Stirling_1(n+k,k) [Kauers and Ko].
a(n) = A035342(n, 1), n >= 1 (first column of triangle).
a(n) = A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle.
From Gary W. Adamson, Jul 19 2011: (Start)
a(n) = upper left term of M^n and sum of top row terms of M^(n-1), where M = a variant of the (1,2) Pascal triangle (Cf. A029635) as the following production matrix:
1, 2, 0, 0, 0, ...
1, 3, 2, 0, 0, ...
1, 4, 5, 2, 0, ...
1, 5, 9, 7, 2, ...
...
For example, a(3) = 15 is the left term in top row of M^3: (15, 46, 36, 8) and a(4) = 105 = (15 + 46 + 36 + 8).
(End)
G.f.: A(x) = 1 + x/(W(0) - x); W(k) = 1 + x + x*2*k - x*(2*k + 3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011
a(n) = Sum_{i=1..n} binomial(n,i-1)*a(i-1)*a(n-i). - Dennis P. Walsh, Dec 02 2011
a(n) = A009445(n) / A014481(n). - Reinhard Zumkeller, Dec 03 2011
a(n) = (-1)^n*Sum_{k=0..n} 2^(n-k)*s(n+1,k+1), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
a(n) = (2*n)4! = Gauss_factorial(2*n,4) = Product{j=1..2*n, gcd(j,4)=1} j. - Peter Luschny, Oct 01 2012
G.f.: (1 - 1/Q(0))/x where Q(k) = 1 - x*(2*k - 1)/(1 - x*(2*k + 2)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 19 2013
G.f.: 1 + x/Q(0), where Q(k) = 1 + (2*k - 1)*x - 2*x*(k + 1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 2*x*(2*k + 1)/(2*x*(2*k + 1) - 1 + 2*x*(2*k + 2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013
G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(2*k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: G(0), where G(k) = 1 + 2*x*(4*k + 1)/(4*k + 2 - 2*x*(2*k + 1)*(4*k + 3)/(x*(4*k + 3) + 2*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 22 2013
a(n) = (2*n - 3)*a(n-2) + (2*n - 2)*a(n-1), n > 1. - Ivan N. Ianakiev, Jul 08 2013
G.f.: G(0), where G(k) = 1 - x*(k+1)/(x*(k+1) - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 04 2013
a(n) = 2*a(n-1) + (2n-3)^2*a(n-2), a(0) = a(1) = 1. - Philippe Deléham, Oct 27 2013
G.f. of reciprocals: Sum_{n>=0} x^n/a(n) = 1F1(1; 1/2; x/2), confluent hypergeometric Function. - R. J. Mathar, Jul 25 2014
0 = a(n)*(+2*a(n+1) - a(n+2)) + a(n+1)*(+a(n+1)) for all n in Z. - Michael Somos, Sep 18 2014
a(n) = (-1)^n / a(-n) = 2*a(n-1) + a(n-1)^2 / a(n-2) for all n in Z. - Michael Somos, Sep 18 2014
From Peter Bala, Feb 18 2015: (Start)
Recurrence equation: a(n) = (3*n - 2)*a(n-1) - (n - 1)*(2*n - 3)*a(n-2) with a(1) = 1 and a(2) = 3.
The sequence b(n) = A087547(n), beginning [1, 4, 52, 608, 12624, ... ], satisfies the same second-order recurrence equation. This leads to the generalized continued fraction expansion lim_{n -> infinity} b(n)/a(n) = Pi/2 = 1 + 1/(3 - 6/(7 - 15/(10 - ... - n*(2*n - 1)/((3*n + 1) - ... )))). (End)
E.g.f of the sequence whose n-th element (n = 1,2,...) equals a(n-1) is 1-sqrt(1-2*x). - Stanislav Sykora, Jan 06 2017
Sum_{n >= 1} a(n)/(2*n-1)! = exp(1/2). - Daniel Suteu, Feb 06 2017
a(n) = A028338(n, 0), n >= 0. - Wolfdieter Lang, May 27 2017
a(n) = (Product_{k=0..n-2} binomial(2*(n-k),2))/n!. - Stefano Spezia, Nov 13 2018
a(n) = Sum_{i=0..n-1} Sum_{j=0..n-i-1} C(n-1,i)*C(n-i-1,j)*a(i)*a(j)*a(n-i-j-1), a(0)=1, - Vladimir Kruchinin, May 06 2020
From Amiram Eldar, Jun 29 2020: (Start)
Sum_{n>=1} 1/a(n) = sqrt(e*Pi/2)*erf(1/sqrt(2)), where erf is the error function.
Sum_{n>=1} (-1)^(n+1)/a(n) = sqrt(Pi/(2*e))*erfi(1/sqrt(2)), where erfi is the imaginary error function. (End)
G.f. of reciprocals: R(x) = Sum_{n>=0} x^n/a(n) satisfies (1 + x)*R(x) = 1 + 2*x*R'(x). - Werner Schulte, Nov 04 2024

Extensions

Removed erroneous comments: neither the number of n X n binary matrices A such that A^2 = 0 nor the number of simple directed graphs on n vertices with no directed path of length two are counted by this sequence (for n = 3, both are 13). - Dan Drake, Jun 02 2009

A000166 Subfactorial or rencontres numbers, or derangements: number of permutations of n elements with no fixed points.

Original entry on oeis.org

1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 2290792932, 32071101049, 481066515734, 7697064251745, 130850092279664, 2355301661033953, 44750731559645106, 895014631192902121, 18795307255050944540, 413496759611120779881, 9510425471055777937262
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Euler (1809) not only gives the first ten or so terms of the sequence, he also proves both recurrences a(n) = (n-1)*(a(n-1) + a(n-2)) and a(n) = n*a(n-1) + (-1)^n.
a(n) is the permanent of the matrix with 0 on the diagonal and 1 elsewhere. - Yuval Dekel, Nov 01 2003
a(n) is the number of desarrangements of length n. A desarrangement of length n is a permutation p of {1,2,...,n} for which the smallest of all the ascents of p (taken to be n if there are no ascents) is even. Example: a(3) = 2 because we have 213 and 312 (smallest ascents at i = 2). See the J. Désarménien link and the Bona reference (p. 118). - Emeric Deutsch, Dec 28 2007
a(n) is the number of deco polyominoes of height n and having in the last column an even number of cells. A deco polyomino is a directed column-convex polyomino in which the height, measured along the diagonal, is attained only in the last column. - Emeric Deutsch, Dec 28 2007
Attributed to Nicholas Bernoulli in connection with a probability problem that he presented. See Problem #15, p. 494, in "History of Mathematics" by David M. Burton, 6th edition. - Mohammad K. Azarian, Feb 25 2008
a(n) is the number of permutations p of {1,2,...,n} with p(1)!=1 and having no right-to-left minima in consecutive positions. Example a(3) = 2 because we have 231 and 321. - Emeric Deutsch, Mar 12 2008
a(n) is the number of permutations p of {1,2,...,n} with p(n)! = n and having no left to right maxima in consecutive positions. Example a(3) = 2 because we have 312 and 321. - Emeric Deutsch, Mar 12 2008
Number of wedged (n-1)-spheres in the homotopy type of the Boolean complex of the complete graph K_n. - Bridget Tenner, Jun 04 2008
The only prime number in the sequence is 2. - Howard Berman (howard_berman(AT)hotmail.com), Nov 08 2008
From Emeric Deutsch, Apr 02 2009: (Start)
a(n) is the number of permutations of {1,2,...,n} having exactly one small ascent. A small ascent in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. (Example: a(3) = 2 because we have 312 and 231; see the Charalambides reference, pp. 176-180.) [See also David, Kendall and Barton, p. 263. - N. J. A. Sloane, Apr 11 2014]
a(n) is the number of permutations of {1,2,...,n} having exactly one small descent. A small descent in a permutation (p_1,p_2,...,p_n) is a position i such that p_i - p_{i+1} = 1. (Example: a(3)=2 because we have 132 and 213.) (End)
For n > 2, a(n) + a(n-1) = A000255(n-1); where A000255 = (1, 1, 3, 11, 53, ...). - Gary W. Adamson, Apr 16 2009
Connection to A002469 (game of mousetrap with n cards): A002469(n) = (n-2)*A000255(n-1) + A000166(n). (Cf. triangle A159610.) - Gary W. Adamson, Apr 17 2009
From Emeric Deutsch, Jul 18 2009: (Start)
a(n) is the sum of the values of the largest fixed points of all non-derangements of length n-1. Example: a(4)=9 because the non-derangements of length 3 are 123, 132, 213, and 321, having largest fixed points 3, 1, 3, and 2, respectively.
a(n) is the number of non-derangements of length n+1 for which the difference between the largest and smallest fixed point is 2. Example: a(3) = 2 because we have 1'43'2 and 32'14'; a(4) = 9 because we have 1'23'54, 1'43'52, 1'53'24, 52'34'1, 52'14'3, 32'54'1, 213'45', 243'15', and 413'25' (the extreme fixed points are marked).
(End)
a(n), n >= 1, is also the number of unordered necklaces with n beads, labeled differently from 1 to n, where each necklace has >= 2 beads. This produces the M2 multinomial formula involving partitions without part 1 given below. Because M2(p) counts the permutations with cycle structure given by partition p, this formula gives the number of permutations without fixed points (no 1-cycles), i.e., the derangements, hence the subfactorials with their recurrence relation and inputs. Each necklace with no beads is assumed to contribute a factor 1 in the counting, hence a(0)=1. This comment derives from a family of recurrences found by Malin Sjodahl for a combinatorial problem for certain quark and gluon diagrams (Feb 27 2010). - Wolfdieter Lang, Jun 01 2010
From Emeric Deutsch, Sep 06 2010: (Start)
a(n) is the number of permutations of {1,2,...,n, n+1} starting with 1 and having no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 1324 and 1432.
a(n) is the number of permutations of {1,2,...,n} that do not start with 1 and have no successions. A succession in a permutation (p_1,p_2,...,p_n) is a position i such that p_{i+1} - p_i = 1. Example: a(3)=2 because we have 213 and 321.
(End)
Increasing colored 1-2 trees with choice of two colors for the rightmost branch of nonleave except on the leftmost path, there is no vertex of outdegree one on the leftmost path. - Wenjin Woan, May 23 2011
a(n) is the number of zeros in n-th row of the triangle in A170942, n > 0. - Reinhard Zumkeller, Mar 29 2012
a(n) is the maximal number of totally mixed Nash equilibria in games of n players, each with 2 pure options. - Raimundas Vidunas, Jan 22 2014
Convolution of sequence A135799 with the sequence generated by 1+x^2/(2*x+1). - Thomas Baruchel, Jan 08 2016
The number of interior lattice points of the subpolytope of the n-dimensional permutohedron whose vertices correspond to permutations avoiding 132 and 312. - Robert Davis, Oct 05 2016
Consider n circles of different radii, where each circle is either put inside some bigger circle or contains a smaller circle inside it (no common points are allowed). Then a(n) gives the number of such combinations. - Anton Zakharov, Oct 12 2016
If we partition the permutations of [n+1] in A000240 according to their starting digit, we will get (n+1) equinumerous classes each of size a(n), i.e., A000240(n+1) = (n+1)*a(n), hence a(n) is the size of each class of permutations of [n+1] in A000240. For example, for n = 4 we have 45 = 5*9. - Enrique Navarrete, Jan 10 2017
Call d_n1 the permutations of [n] that have the substring n1 but no substring in {12,23,...,(n-1)n}. If we partition them according to their starting digit, we will get (n-1) equinumerous classes each of size A000166(n-2) (the class starting with the digit 1 is empty since we must have the substring n1). Hence d_n1 = (n-1)*A000166(n-2) and A000166(n-2) is the size of each nonempty class in d_n1. For example, d_71 = 6*44 = 264, so there are 264 permutations in d_71 distributed in 6 nonempty classes of size A000166(5) = 44. (To get permutations in d_n1 recursively from more basic ones see the link "Forbidden Patterns" below.) - Enrique Navarrete, Jan 15 2017
Also the number of maximum matchings and minimum edge covers in the n-crown graph. - Eric W. Weisstein, Jun 14 and Dec 24 2017
The sequence a(n) taken modulo a positive integer k is periodic with exact period dividing k when k is even and dividing 2*k when k is odd. This follows from the congruence a(n+k) = (-1)^k*a(n) (mod k) for all n and k, which in turn is easily proved by induction making use of the recurrence a(n) = n*a(n-1) + (-1)^n. - Peter Bala, Nov 21 2017
a(n) is the number of distinct possible solutions for a directed, no self loop containing graph (not necessarily connected) that has n vertices, and each vertex has an in- and out-degree of exactly 1. - Patrik Holopainen, Sep 18 2018
a(n) is the dimension of the kernel of the random-to-top and random-to-random shuffling operators over a collection of n objects (in a vector space of size n!), as noticed by M. Wachs and V. Reiner. See the Reiner, Saliola and Welker reference below. - Nadia Lafreniere, Jul 18 2019
a(n) is the number of distinct permutations for a Secret Santa gift exchange with n participants. - Patrik Holopainen, Dec 30 2019
a(2*n+1) is even. More generally, a(m*n+1) is divisible by m*n, which follows from a(n+1) = n*(a(n) + a(n-1)) = n*A000255(n-1) for n >= 1. a(2*n) is odd; in fact, a(2*n) == 1 (mod 8). Other divisibility properties include a(6*n) == 1 (mod 24), a(9*n+4) == a(9*n+7) == 0 (mod 9), a(10*n) == 1 (mod 40), a(11*n+5) == 0 (mod 11) and a(13*n+8 ) == 0 (mod 13). - Peter Bala, Apr 05 2022
Conjecture: a(n) with n > 2 is a perfect power only for n = 4 with a(4) = 3^2. This has been verified for n <= 1000. - Zhi-Wei Sun, Jan 09 2025

Examples

			a(2) = 1, a(3) = 2 and a(4) = 9 since the possibilities are {BA}, {BCA, CAB} and {BADC, BCDA, BDAC, CADB, CDAB, CDBA, DABC, DCAB, DCBA}. - _Henry Bottomley_, Jan 17 2001
The Boolean complex of the complete graph K_4 is homotopy equivalent to the wedge of 9 3-spheres.
Necklace problem for n = 6: partitions without part 1 and M2 numbers for n = 6: there are A002865(6) = 4 such partitions, namely (6), (2,4), (3^2) and (2^3) in A-St order with the M2 numbers 5!, 90, 40 and 15, respectively, adding up to 265 = a(6). This corresponds to 1 necklace with 6 beads, two necklaces with 2 and 4 beads respectively, two necklaces with 3 beads each and three necklaces with 2 beads each. - _Wolfdieter Lang_, Jun 01 2010
G.f. = 1 + x^2 + 9*x^3 + 44*x^4 + 265*x^5 + 1854*x^6 + 14833*x^7 + 133496*x^8 + ...

References

  • U. Abel, Some new identities for derangement numbers, Fib. Q., 56:4 (2018), 313-318.
  • M. Bona, Combinatorics of Permutations, Chapman & Hall/CRC, Boca Raton, Florida, 2004.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 32.
  • R. A. Brualdi and H. J. Ryser: Combinatorial Matrix Theory, 1992, Section 7.2, p. 202.
  • Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 182.
  • Florence Nightingale David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 168.
  • Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263, Table 7.5.1, row 1.
  • P. R. de Montmort, On the Game of Thirteen (1713), reprinted in Annotated Readings in the History of Statistics, ed. H. A. David and A. W. F. Edwards, Springer-Verlag, 2001, pp. 25-29.
  • J. M. de Saint-Martin, "Le problème des rencontres" in Quadrature, No. 61, pp. 14-19, 2006, EDP-Sciences Les Ulis (France).
  • H. Doerrie, 100 Great Problems of Elementary Mathematics, Dover, NY, 1965, p. 19.
  • Leonhard Euler, Solution quaestionis curiosae ex doctrina combinationum, Mémoires Académie sciences St. Pétersburg 3 (1809/1810), 57-64; also E738 in his Collected Works, series I, volume 7, pages 435-440.
  • J. M. Gandhi, On logarithmic numbers, Math. Student, 31 (1963), 73-83.
  • A. Hald, A History of Probability and Statistics and Their Applications Before 1750, Wiley, NY, 1990 (Chapter 19).
  • Irving Kaplansky, John Riordan, The problème des ménages. Scripta Math. 12 (1946), 113-124. See Eq(1).
  • Arnold Kaufmann, "Introduction à la combinatorique en vue des applications." Dunod, Paris, 1968. See p. 92.
  • Florian Kerschbaum and Orestis Terzidis, Filtering for Private Collaborative Benchmarking, in Emerging Trends in Information and Communication Security, Lecture Notes in Computer Science, Volume 3995/2006.
  • E. Lozansky and C. Rousseau, Winning Solutions, Springer, 1996; see p. 152.
  • P. A. MacMahon, Combinatory Analysis, 2 vols., Chelsea, NY, 1960, see p. 102.
  • M. S. Petković, "Non-attacking rooks", Famous Puzzles of Great Mathematicians, pp. 265-268, Amer. Math. Soc.(AMS), 2009.
  • V. Reiner, F. Saliola, and V. Welker. Spectra of Symmetrized Shuffling Operators, Memoirs of the American Mathematical Society, vol. 228, Amer. Math. Soc., Providence, RI, 2014, pp. 1-121. See section VI.9.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 65.
  • H. J. Ryser, Combinatorial Mathematics. Mathematical Association of America, Carus Mathematical Monograph 14, 1963, p. 23.
  • T. Simpson, Permutations with unique fixed and reflected points. Ars Combin. 39 (1995), 97-108.
  • 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).
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 122.
  • D. B. West, Combinatorial Mathematics, Cambridge, 2021, p. 82.
  • H. S. Wilf, Generatingfunctionology, Academic Press, NY, 1990, p. 147, Eq. 5.2.9 (q=1).

Links

Crossrefs

Cf. A000142, A002467, A003221, A000522, A000240, A000387, A000449, A000475, A129135, A092582, A000255, A002469, A159610, A068985, A068996, A047865, A038205, A008279, A281682.
For the probabilities a(n)/n!, see A053557/A053556 and A103816/A053556.
A diagonal of A008291 and A068106. Column A008290(n,0).
A001120 has a similar recurrence.
For other derangement numbers see also A053871, A033030, A088991, A088992.
Pairwise sums of A002741 and A000757. Differences of A001277.
Cf. A101560, A101559, A000110, A101033, A101032, A000204, A100492, A099731, A000045, A094216, A094638, A000108.
A diagonal in triangles A008305 and A010027.
a(n)/n! = A053557/A053556 = (N(n, n) of A103361)/(D(n, n) of A103360).
Column k=0 of A086764 and of A334715. Column k=1 of A364068.
Row sums of A216963 and of A323671.

Programs

  • Haskell
    a000166 n = a000166_list !! n
a000166_list = 1 : 0 : zipWith (*) [1..]
                       (zipWith (+) a000166_list $ tail a000166_list)
-- Reinhard Zumkeller, Dec 09 2012
  • Magma
    I:=[0,1]; [1] cat [n le 2 select I[n] else (n-1)*(Self(n-1)+Self(n-2)): n in [1..30]]; // Vincenzo Librandi, Jan 07 2016
  • Maple
    A000166 := proc(n) option remember; if n<=1 then 1-n else (n-1)*(procname(n-1)+procname(n-2)); fi; end;
a:=n->n!*sum((-1)^k/k!, k=0..n): seq(a(n), n=0..21); # Zerinvary Lajos, May 17 2007
ZL1:=[S,{S=Set(Cycle(Z,card>1))},labeled]: seq(count(ZL1,size=n),n=0..21); # Zerinvary Lajos, Sep 26 2007
with (combstruct):a:=proc(m) [ZL,{ZL=Set(Cycle(Z,card>=m))},labeled]; end: A000166:=a(2):seq(count(A000166,size=n),n=0..21); # Zerinvary Lajos, Oct 02 2007
Z := (x, m)->m!^2*sum(x^j/((m-j)!^2), j=0..m): R := (x, n, m)->Z(x, m)^n: f := (t, n, m)->sum(coeff(R(x, n, m), x, j)*(t-1)^j*(n*m-j)!, j=0..n*m): seq(f(0, n, 1), n=0..21); # Zerinvary Lajos, Jan 22 2008
a:=proc(n) if `mod`(n,2)=1 then sum(2*k*factorial(n)/factorial(2*k+1), k=1.. floor((1/2)*n)) else 1+sum(2*k*factorial(n)/factorial(2*k+1), k=1..floor((1/2)*n)-1) end if end proc: seq(a(n),n=0..20); # Emeric Deutsch, Feb 23 2008
G(x):=2*exp(-x)/(1-x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od: x:=0: seq(f[n]/2,n=0..21); # Zerinvary Lajos, Apr 03 2009
seq(simplify(KummerU(-n, -n, -1)), n = 0..23); # Peter Luschny, May 10 2022
  • Mathematica
    a[0] = 1; a[n_] := n*a[n - 1] + (-1)^n; a /@ Range[0, 21] (* Robert G. Wilson v *)
a[0] = 1; a[1] = 0; a[n_] := Round[n!/E] /; n >= 1 (* Michael Taktikos, May 26 2006 *)
Range[0, 20]! CoefficientList[ Series[ Exp[ -x]/(1 - x), {x, 0, 20}], x]
dr[{n_,a1_,a2_}]:={n+1,a2,n(a1+a2)}; Transpose[NestList[dr,{0,0,1},30]][[3]] (* Harvey P. Dale, Feb 23 2013 *)
a[n_] := (-1)^n HypergeometricPFQ[{- n, 1}, {}, 1]; (* Michael Somos, Jun 01 2013 *)
a[n_] := n! SeriesCoefficient[Exp[-x] /(1 - x), {x, 0, n}]; (* Michael Somos, Jun 01 2013 *)
Table[Subfactorial[n], {n, 0, 21}] (* Jean-François Alcover, Jan 10 2014 *)
RecurrenceTable[{a[n] == n*a[n - 1] + (-1)^n, a[0] == 1}, a, {n, 0, 23}] (* Ray Chandler, Jul 30 2015 *)
Subfactorial[Range[0, 20]] (* Eric W. Weisstein, Dec 31 2017 *)
nxt[{n_,a_}]:={n+1,a(n+1)+(-1)^(n+1)}; NestList[nxt,{0,1},25][[All,2]] (* Harvey P. Dale, Jun 01 2019 *)
  • Maxima
    s[0]:1$
s[n]:=n*s[n-1]+(-1)^n$
makelist(s[n],n,0,12); /* Emanuele Munarini, Mar 01 2011 */
  • PARI
    {a(n) = if( n<1, 1, n * a(n-1) + (-1)^n)}; /* Michael Somos, Mar 24 2003 */
  • PARI
    {a(n) = n! * polcoeff( exp(-x + x * O(x^n)) / (1 - x), n)}; /* Michael Somos, Mar 24 2003 */
  • PARI
    {a(n)=polcoeff(sum(m=0,n,m^m*x^m/(1+(m+1)*x+x*O(x^n))^(m+1)),n)} /* Paul D. Hanna */
  • PARI
    A000166=n->n!*sum(k=0,n,(-1)^k/k!) \\ M. F. Hasler, Jan 26 2012
  • PARI
    a(n)=if(n,round(n!/exp(1)),1) \\ Charles R Greathouse IV, Jun 17 2012
  • PARI
    apply( {A000166(n)=n!\/exp(n>0)}, [0..22]) \\ M. F. Hasler, Nov 09 2024
  • Python
    See Hobson link.
  • Python
    A000166_list, m, x = [], 1, 1
for n in range(10*2):
    x, m = x*n + m, -m
    A000166_list.append(x) # Chai Wah Wu, Nov 03 2014

Formula

(A000166 + A000522)/2 = A009179, (A000166 - A000522)/2 = A009628.
a(n) = A008290(n,0).
a(n) + A003048(n+1) = 2*n!. - D. G. Rogers, Aug 26 2006
a(n) = {(n-1)!/exp(1)}, n > 1, where {x} is the nearest integer function. - Simon Plouffe, March 1993 [This uses offset 1, see below for the version with offset 0. - Charles R Greathouse IV, Jan 25 2012]
a(0) = 1, a(n) = round(n!/e) = floor(n!/e + 1/2) for n > 0.
a(n) = n!*Sum_{k=0..n} (-1)^k/k!.
D-finite with recurrence a(n) = (n-1)*(a(n-1) + a(n-2)), n > 0.
a(n) = n*a(n-1) + (-1)^n.
E.g.f.: exp(-x)/(1-x).
a(n) = Sum_{k=0..n} binomial(n, k)*(-1)^(n-k)*k! = Sum_{k=0..n} (-1)^(n-k)*n!/(n-k)!. - Paul Barry, Aug 26 2004
The e.g.f. y(x) satisfies y' = x*y/(1-x).
Inverse binomial transform of A000142. - Ross La Haye, Sep 21 2004
In Maple notation, representation as n-th moment of a positive function on [-1, infinity]: a(n)= int( x^n*exp(-x-1), x=-1..infinity ), n=0, 1... . a(n) is the Hamburger moment of the function exp(-1-x)*Heaviside(x+1). - Karol A. Penson, Jan 21 2005
a(n) = A001120(n) - n!. - Philippe Deléham, Sep 04 2005
a(n) = Integral_{x=0..oo} (x-1)^n*exp(-x) dx. - Gerald McGarvey, Oct 14 2006
a(n) = Sum_{k=2,4,...} T(n,k), where T(n,k) = A092582(n,k) = k*n!/(k+1)! for 1 <= k < n and T(n,n)=1. - Emeric Deutsch, Feb 23 2008
a(n) = n!/e + (-1)^n*(1/(n+2 - 1/(n+3 - 2/(n+4 - 3/(n+5 - ...))))). Asymptotic result (Ramanujan): (-1)^n*(a(n) - n!/e) ~ 1/n - 2/n^2 + 5/n^3 - 15/n^4 + ..., where the sequence [1,2,5,15,...] is the sequence of Bell numbers A000110. - Peter Bala, Jul 14 2008
From William Vaughn (wvaughn(AT)cvs.rochester.edu), Apr 13 2009: (Start)
a(n) = Integral_{p=0..1} (log(1/(1-p)) - 1)^n dp.
Proof: Using the substitutions 1=log(e) and y = e(1-p) the above integral can be converted to ((-1)^n/e) Integral_{y=0..e} (log(y))^n dy.
From CRC Integral tables we find the antiderivative of (log(y))^n is (-1)^n n! Sum_{k=0..n} (-1)^k y(log(y))^k / k!.
Using the fact that e(log(e))^r = e for any r >= 0 and 0(log(0))^r = 0 for any r >= 0 the integral becomes n! * Sum_{k=0..n} (-1)^k / k!, which is line 9 of the Formula section. (End)
a(n) = exp(-1)*Gamma(n+1,-1) (incomplete Gamma function). - Mark van Hoeij, Nov 11 2009
G.f.: 1/(1-x^2/(1-2x-4x^2/(1-4x-9x^2/(1-6x-16x^2/(1-8x-25x^2/(1-... (continued fraction). - Paul Barry, Nov 27 2009
a(n) = Sum_{p in Pano1(n)} M2(p), n >= 1, with Pano1(n) the set of partitions without part 1, and the multinomial M2 numbers. See the characteristic array for partitions without part 1 given by A145573 in Abramowitz-Stegun (A-S) order, with A002865(n) the total number of such partitions. The M2 numbers are given for each partition in A-St order by the array A036039. - Wolfdieter Lang, Jun 01 2010
a(n) = row sum of A008306(n), n > 1. - Gary Detlefs, Jul 14 2010
a(n) = ((-1)^n)*(n-1)*hypergeom([-n+2, 2], [], 1), n>=1; 1 for n=0. - Wolfdieter Lang, Aug 16 2010
a(n) = (-1)^n * hypergeom([ -n, 1], [], 1), n>=1; 1 for n=0. From the binomial convolution due to the e.g.f. - Wolfdieter Lang, Aug 26 2010
Integral_{x=0..1} x^n*exp(x) = (-1)^n*(a(n)*e - n!).
O.g.f.: Sum_{n>=0} n^n*x^n/(1 + (n+1)*x)^(n+1). - Paul D. Hanna, Oct 06 2011
Abs((a(n) + a(n-1))*e - (A000142(n) + A000142(n-1))) < 2/n. - Seiichi Kirikami, Oct 17 2011
G.f.: hypergeom([1,1],[],x/(x+1))/(x+1). - Mark van Hoeij, Nov 07 2011
From Sergei N. Gladkovskii, Nov 25 2011, Jul 05 2012, Sep 23 2012, Oct 13 2012, Mar 09 2013, Mar 10 2013, Oct 18 2013: (Start)
Continued fractions:
In general, e.g.f. (1+a*x)/exp(b*x) = U(0) with U(k) = 1 + a*x/(1-b/(b-a*(k+1)/U(k+1))). For a=-1, b=-1: exp(-x)/(1-x) = 1/U(0).
E.g.f.: (1-x/(U(0)+x))/(1-x), where U(k) = k+1 - x + (k+1)*x/U(k+1).
E.g.f.: 1/Q(0) where Q(k) = 1 - x/(1 - 1/(1 - (k+1)/Q(k+1))).
G.f.: 1/U(0) where U(k) = 1 + x - x*(k+1)/(1 - x*(k+1)/U(k+1)).
G.f.: Q(0)/(1+x) where Q(k) = 1 + (2*k+1)*x/((1+x)-2*x*(1+x)*(k+1)/(2*x*(k+1)+(1+x)/ Q(k+1))).
G.f.: 1/Q(0) where Q(k) = 1 - 2*k*x - x^2*(k + 1)^2/Q(k+1).
G.f.: T(0) where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2-(1-2*x*k)*(1-2*x-2*x*k)/T(k+1)). (End)
0 = a(n)*(a(n+1) + a(n+2) - a(n+3)) + a(n+1)*(a(n+1) + 2*a(n+2) - a(n+3)) + a(n+2)*a(n+2) if n>=0. - Michael Somos, Jan 25 2014
a(n) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^k*(k + x + 1)^(n-k) = Sum_{k = 0..n} (-1)^(n-k)*binomial(n,k)*(k + x)^(n-k)*(k + x - 1)^k, for arbitrary x. - Peter Bala, Feb 19 2017
From Peter Luschny, Jun 20 2017: (Start)
a(n) = Sum_{j=0..n} Sum_{k=0..n} binomial(-j-1, -n-1)*abs(Stirling1(j, k)).
a(n) = Sum_{k=0..n} (-1)^(n-k)*Pochhammer(n-k+1, k) (cf. A008279). (End)
a(n) = n! - Sum_{j=0..n-1} binomial(n,j) * a(j). - Alois P. Heinz, Jan 23 2019
Sum_{n>=2} 1/a(n) = A281682. - Amiram Eldar, Nov 09 2020
a(n) = KummerU(-n, -n, -1). - Peter Luschny, May 10 2022
a(n) = (-1)^n*Sum_{k=0..n} Bell(k)*Stirling1(n+1, k+1). - Mélika Tebni, Jul 05 2022

Extensions

Minor edits by M. F. Hasler, Jan 16 2017

A000204 Lucas numbers (beginning with 1): L(n) = L(n-1) + L(n-2) with L(1) = 1, L(2) = 3.

Original entry on oeis.org

1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, 2207, 3571, 5778, 9349, 15127, 24476, 39603, 64079, 103682, 167761, 271443, 439204, 710647, 1149851, 1860498, 3010349, 4870847, 7881196, 12752043, 20633239, 33385282, 54018521, 87403803, 141422324
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

See A000032 for the version beginning 2, 1, 3, 4, 7, ...
Also called Schoute's accessory series (see Jean, 1984). - N. J. A. Sloane, Jun 08 2011
L(n) is the number of matchings in a cycle on n vertices: L(4)=7 because the matchings in a square with edges a, b, c, d (labeled consecutively) are the empty set, a, b, c, d, ac and bd. - Emeric Deutsch, Jun 18 2001
This comment covers a family of sequences which satisfy a recurrence of the form a(n) = a(n-1) + a(n-m), with a(n) = 1 for n = 1..m - 1, a(m) = m + 1. The generating function is (x + m*x^m)/(1 - x - x^m). Also a(n) = 1 + n*Sum_{i=1..n/m} binomial(n - 1 - (m - 1)*i, i - 1)/i. This gives the number of ways to cover (without overlapping) a ring lattice (or necklace) of n sites with molecules that are m sites wide. Special cases: m = 2: A000204, m = 3: A001609, m = 4: A014097, m = 5: A058368, m = 6: A058367, m = 7: A058366, m = 8: A058365, m = 9: A058364.
L(n) is the number of points of period n in the golden mean shift. The number of orbits of length n in the golden mean shift is given by the n-th term of the sequence A006206. - Thomas Ward, Mar 13 2001
Row sums of A029635 are 1, 1, 3, 4, 7, ... - Paul Barry, Jan 30 2005
a(n) counts circular n-bit strings with no repeated 1's. E.g., for a(5): 00000 00001 00010 00100 00101 01000 01001 01010 10000 10010 10100. Note #{0...} = fib(n+1), #{1...} = fib(n-1), #{000..., 001..., 100...} = a(n-1), #{010..., 101...} = a(n-2). - Len Smiley, Oct 14 2001
Row sums of the triangle in A182579. - Reinhard Zumkeller, May 07 2012
If p is prime then L(p) == 1 (mod p). L(2^k) == -1 (mod 2^(k+1)) for k = 0,1,2,... - Thomas Ordowski, Sep 25 2013
Satisfies Benford's law [Brown-Duncan, 1970; Berger-Hill, 2017]. - N. J. A. Sloane, Feb 08 2017

Examples

			G.f. = x + 3*x^2 + 4*x^3 + 7*x^4 + 11*x^5 + 18*x^6 + 29*x^7 + 47*x^8 + ...

References

  • P. Bachmann, Niedere Zahlentheorie (1902, 1910), reprinted Chelsea, NY, 1968, vol. 2, p. 69.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 46.
  • Leonhard Euler, Introductio in analysin infinitorum (1748), sections 216 and 229.
  • G. Everest, A. van der Poorten, I. Shparlinski and T. Ward, Recurrence Sequences, Amer. Math. Soc., 2003; see esp. p. 255.
  • G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 148.
  • Silvia Heubach and Toufik Mansour, Combinatorics of Compositions and Words, CRC Press, 2010.
  • V. E. Hoggatt, Jr., Fibonacci and Lucas Numbers. Houghton, Boston, MA, 1969.
  • R. V. Jean, Mathematical Approach to Pattern and Form in Plant Growth, Wiley, 1984. See p. 5. - N. J. A. Sloane, Jun 08 2011
  • Thomas Koshy, "Fibonacci and Lucas Numbers with Applications", John Wiley and Sons, 2001.
  • 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).
  • S. Vajda, Fibonacci and Lucas numbers and the Golden Section, Ellis Horwood Ltd., Chichester, 1989.

Links

Crossrefs

Cf. A000032, A000045, A061084, A027960, A001609, A014097, A000079, A003269, A003520, A005708, A005709, A005710, A006206, A101033, A101032, A100492, A099731, A094216, A094638, A000108, A090946 (complement).

Programs

  • Haskell
    a000204 n = a000204_list !! n
a000204_list = 1 : 3 : zipWith (+) a000204_list (tail a000204_list)
-- Reinhard Zumkeller, Dec 18 2011
  • Magma
    [Lucas(n): n in [1..30]]; // G. C. Greubel, Dec 17 2017
  • Maple
    A000204 := proc(n) option remember; if n <=2 then 2*n-1; else procname(n-1)+procname(n-2); fi; end;
with(combinat): A000204 := n->fibonacci(n+1)+fibonacci(n-1);
# alternative Maple program:
L:= n-> (<<1|1>, <1|0>>^n. <<2, -1>>)[1, 1]:
seq(L(n), n=1..50);  # Alois P. Heinz, Jul 25 2008
# Alternative:
a := n -> `if`(n=1, 1, `if`(n=2, 3, hypergeom([(1-n)/2, -n/2], [1-n], -4))):
seq(simplify(a(n)), n=1..39); # Peter Luschny, Sep 03 2019
  • Mathematica
    c = (1 + Sqrt[5])/2; Table[Expand[c^n + (1 - c)^n], {n, 30}] (* Artur Jasinski, Oct 05 2008 *)
Table[LucasL[n, 1], {n, 36}] (* Zerinvary Lajos, Jul 09 2009 *)
LinearRecurrence[{1, 1},{1, 3}, 50] (* Sture Sjöstedt, Nov 28 2011 *)
lukeNum[n_] := If[n < 1, 0, LucasL[n]]; (* Michael Somos, May 18 2015 *)
lukeNum[n_] := SeriesCoefficient[x D[Log[1 / (1 - x - x^2)], x], {x, 0, n}]; (* Michael Somos, May 18 2015 *)
  • PARI
    A000204(n)=fibonacci(n+1)+fibonacci(n-1) \\ Michael B. Porter, Nov 05 2009
  • Python
    from functools import cache
@cache
def a(n): return [1, 3][n-1] if n < 3 else a(n-1) + a(n-2)
print([a(n) for n in range(1, 41)]) # Michael S. Branicky, Nov 13 2022
  • Python
    [(i:=-1)+(j:=2)] + [(j:=i+j)+(i:=j-i) for  in range(100)] # _Jwalin Bhatt, Apr 02 2025
  • Sage
    def A000204():
    x, y = 1, 2
    while true:
       yield x
       x, y = x + y, x
a = A000204(); print([next(a) for i in range(39)])  # Peter Luschny, Dec 17 2015
  • Scala
    def lucas(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, 2, 1)
}
(1 to 50).map(lucas()) // _Alonso del Arte, Oct 20 2019

Formula

Expansion of x(1 + 2x)/(1 - x - x^2). - Simon Plouffe, dissertation 1992; multiplied by x. - R. J. Mathar, Nov 14 2007
a(n) = A000045(2n)/A000045(n). - Benoit Cloitre, Jan 05 2003
For n > 1, L(n) = F(n + 2) - F(n - 2), where F(n) is the n-th Fibonacci number (A000045). - Gerald McGarvey, Jul 10 2004
a(n+1) = 4*A054886(n+3) - A022388(n) - 2*A022120(n+1) (a conjecture; note that the above sequences have different offsets). - Creighton Dement, Nov 27 2004
a(n) = Sum_{k=0..floor((n+1)/2)} (n+1)*binomial(n - k + 1, k)/(n - k + 1). - Paul Barry, Jan 30 2005
L(n) = A000045(n+3) - 2*A000045(n). - Creighton Dement, Oct 07 2005
L(n) = A000045(n+1) + A000045(n-1). - John Blythe Dobson, Sep 29 2007
a(n) = 2*Fibonacci(n-1) + Fibonacci(n), n >= 1. - Zerinvary Lajos, Oct 05 2007
L(n) is the term (1, 1) in the 1 X 2 matrix [2, -1].[1, 1; 1, 0]^n. - Alois P. Heinz, Jul 25 2008
a(n) = phi^n + (1 - phi)^n = phi^n + (-phi)^(-n) = ((1 + sqrt(5))^n + (1 - sqrt(5))^n)/(2^n) where phi is the golden ratio (A001622). - Artur Jasinski, Oct 05 2008
a(n) = A014217(n+1) - A014217(n-1). See A153263. - Paul Curtz, Dec 22 2008
a(n) = ((1 + sqrt(5))^n - (1 - sqrt(5))^n)/(2^n*sqrt(5)) + ((1 + sqrt(5))^(n - 1) - (1 - sqrt(5))^(n - 1))/(2^(n - 2)*sqrt(5)). - Al Hakanson (hawkuu(AT)gmail.com), Jan 12 2009, Jan 14 2009
From Hieronymus Fischer, Oct 20 2010 (Start)
Continued fraction for n odd: [L(n); L(n), L(n), ...] = L(n) + fract(Fib(n) * phi).
Continued fraction for n even: [L(n); -L(n), L(n), -L(n), L(n), ...] = L(n) - 1 + fract(Fib(n)*phi). Also: [L(n) - 2; 1, L(n) - 2, 1, L(n) - 2, ...] = L(n) - 2 + fract(Fib(n)*phi). (End)
INVERT transform of (1, 2, -1, -2, 1, 2, ...). - Gary W. Adamson, Mar 07 2012
L(2n - 1) = floor(phi^(2n - 1)); L(2n) = ceiling(phi^(2n)). - Thomas Ordowski, Jun 15 2012
a(n) = hypergeom([(1 - n)/2, -n/2], [1 - n], -4) for n >= 3. - Peter Luschny, Sep 03 2019
E.g.f.: 2*(exp(x/2)*cosh(sqrt(5)*x/2) - 1). - Stefano Spezia, Jul 26 2022

Extensions

Additional comments from Yong Kong (ykong(AT)curagen.com), Dec 16 2000
Plouffe Maple line edited by N. J. A. Sloane, May 13 2008

A014137 Partial sums of Catalan numbers (A000108).

Original entry on oeis.org

1, 2, 4, 9, 23, 65, 197, 626, 2056, 6918, 23714, 82500, 290512, 1033412, 3707852, 13402697, 48760367, 178405157, 656043857, 2423307047, 8987427467, 33453694487, 124936258127, 467995871777, 1757900019101, 6619846420553, 24987199492705, 94520750408709, 358268702159069
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This is also the result of applying the transformation on generating functions A -> 1/((1 - x)*(1 - x*A)) to the g.f. for the Catalan numbers.
p divides a(p) - 3 for prime p = 3 and p = {7, 13, 19, 31, 37, 43, ...} = A002476 (Primes of the form 6*n + 1). p^2 divides a(p^2) - 3 for prime p > 3. - Alexander Adamchuk, Jul 11 2006
Prime p divides a(p) for p = {2, 3, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, 101, ...} = A045309 (Primes congruent to {0, 2} mod 3); and A045309 (Primes p such that x^3 = n (integer) has only one solution mod p). Nonprime numbers n such that n divides a(n) are listed in A128287 = {1, 8, 133, ...}. - Alexander Adamchuk, Feb 23 2007
For p prime >= 5, a(p-1) = 1 or -2 (mod p) according as p = 1 or -1 (mod 3) (see Pan and Sun link). For example, with p=5, a(p-1) = 23 = -2 (mod p). - David Callan, Nov 29 2007
Hankel transform is A010892(n+1). - Paul Barry, Apr 24 2009
Equals INVERTi transform of A000245: (1, 3, 9, 28, ...). - Gary W. Adamson, May 15 2009
The subsequence of prime partial sums of Catalan numbers begins: a(1) = 2, a(4) = 23, a(6) = 197, a(16) = 48760367; see A121852. - Jonathan Vos Post, Feb 10 2010
Number of lattice paths from (0,0) to (n,n) which do not go above the diagonal x=y using steps (1,k), (k,1) with k >= 1 including two kinds of (1,1). - Alois P. Heinz, Oct 14 2015
Binomial transform of A086246(n+1) = [1, 1, 1, 2, 4, 9, ...], or, equivalently, of A001006 (Motzkin numbers) with 1 prepended.

Examples

			G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 23*x^4 + 65*x^5 + 197*x^6 + 626*x^7 + 2056*x^8 + ...

Links

Crossrefs

Cf. A000108, A000245, A000984, A001246, A002476, A002897, A006134, A033536, A045309, A079727, A082894, A094638, A094639, A128287, A358436.

Programs

  • Magma
    [(&+[Catalan(k): k in [0..n]]): n in [0..40]]; // G. C. Greubel, Jun 30 2024
  • Maple
    a:= proc(n) option remember; `if`(n<2, n+1,
      ((5*n-1)*a(n-1)-(4*n-2)*a(n-2))/(n+1))
    end:
seq(a(n), n=0..30);  # Alois P. Heinz, May 18 2013
A014137List := proc(m) local A, P, n; A := [1]; P := [1];
for n from 1 to m - 2 do P := ListTools:-PartialSums([op(P), P[-n]]);
A := [op(A), P[-1]] od; A end: A014137List(30); # Peter Luschny, Mar 26 2022
  • Mathematica
    Table[Sum[(2k)!/(k!)^2/(k+1),{k,0,n}],{n,0,30}] (* Alexander Adamchuk, Jul 11 2006 *)
Accumulate[CatalanNumber[Range[0,30]]] (* Harvey P. Dale, May 08 2012 *)
a[ n_] := SeriesCoefficient[ (1 - (1 - 4 x)^(1/2)) / (2 x (1 - x)), {x, 0, n}]; (* Michael Somos, Oct 24 2015 *)
Table[(1 + CatalanNumber[n] (3 (n + 1) Hypergeometric2F1[1, -n, 1/2 - n, 1/4] - 4 n - 2))/2, {n, 0, 20}] (* Vladimir Reshetnikov, Oct 03 2016 *)
  • PARI
    Vec((1-(1-4*x)^(1/2))/(2*x*(1-x))+O(x^99)) \\ Charles R Greathouse IV, Feb 11 2011
  • PARI
    sm(v)={my(s=vector(#v)); s[1]=v[1]; for(n=2, #v, s[n]=v[n]+s[n-1]); s; }
C(n)=binomial(2*n, n)/(n+1);
sm(vector(66, n, C(n-1)))
/* Joerg Arndt, May 04 2013 */
  • Python
    from _future_ import division
A014137_list, b, s = [], 1, 0
for n in range(10**2):
    s += b
    A014137_list.append(s)
    b = b*(4*n+2)//(n+2) # Chai Wah Wu, Jan 28 2016
  • Sage
    def A014137():
    f, c, n = 1, 1, 1
    while True:
        yield f
        n += 1
        c = c * (4*n - 6) // n
        f = c + f
a = A014137()
print([next(a) for  in range(29)]) # _Peter Luschny, Nov 30 2016

Formula

a(n) = A014138(n-1) + 1.
G.f.: (1 - (1 - 4*x)^(1/2))/(2*x*(1 - x)).
a(n) = Sum_{k=0..n} (2k)!/(k!)^2/(k+1). - Alexander Adamchuk, Jul 11 2006
D-finite with recurrence: (n+1)*a(n) + (1-5*n)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Dec 14 2011
Mathar's formula reduces to 2*(2*n-1)*C(n-1) = (n+1)*C(n), which is a known recurrence of the Catalan numbers, so the conjecture is true. - Peter J. Taylor, Mar 23 2015
Let C(n+1) = binomial(2*n+2,n+1)/(n+2) and H(n) = hypergeometric([1,n+3/2],[n+3],4) then A014137(n) = -(-1)^(2/3) - C(n+1)*H(n) and A014138(n) = -I^(2/3) - C(n+1)*H(n). - Peter Luschny, Aug 09 2012
G.f. (conjecture): Q(0)/(1-x), where Q(k)= 1 + (4*k + 1)*x/(k + 1 - 2*x*(k + 1)*(4*k + 3)/(2*x*(4*k + 3) + (2*k + 3)/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 14 2013
a(n) ~ 2^(2*n + 2)/(3*sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Dec 10 2013
0 = a(n)*(16*a(n+1) - 26*a(n+2) + 10*a(n+3)) + a(n+1)*(-14*a(n+1) + 23*a(n+2) - 11*a(n+3)) + a(n+2)*(a(n+2) + a(n+3)) if n >= 0. - Michael Somos, Oct 24 2015
a(n) = (1 + A000108(n)*(3*(n+1)*hypergeom([1,-n], [1/2-n], 1/4) - 4*n - 2))/2. - Vladimir Reshetnikov, Oct 03 2016
G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x * (1 - x) * A(x)^2. - Ilya Gutkovskiy, Jul 25 2021
From Peter Luschny, Nov 16 2022: (Start)
a(n) = C(n)*hypergeom([1, -n - 1], [1/2 - n], 1/4) + 1/2.
a(n) = A358436(n) / C(n). (End)
E.g.f.: exp(2*x)*(BesselI(0, 2*x)/2 - BesselI(1, 2*x)) + exp(x)/2*(3*Integral_{x=-oo..oo} BesselI(0,2*x)*exp(x) dx + 1). - Mélika Tebni, Sep 01 2024

A001710 Order of alternating group A_n, or number of even permutations of n letters.

Original entry on oeis.org

1, 1, 1, 3, 12, 60, 360, 2520, 20160, 181440, 1814400, 19958400, 239500800, 3113510400, 43589145600, 653837184000, 10461394944000, 177843714048000, 3201186852864000, 60822550204416000, 1216451004088320000, 25545471085854720000, 562000363888803840000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n >= 3, a(n-1) is also the number of ways that a 3-cycle in the symmetric group S_n can be written as a product of 2 long cycles (of length n). - Ahmed Fares (ahmedfares(AT)my-deja.com), Aug 14 2001
a(n) is the number of Hamiltonian circuit masks for an n X n adjacency matrix of an undirected graph. - Chad Brewbaker, Jan 31 2003
a(n-1) is the number of necklaces one can make with n distinct beads: n! bead permutations, divide by two to represent flipping the necklace over, divide by n to represent rotating the necklace. Related to Stirling numbers of the first kind, Stirling cycles. - Chad Brewbaker, Jan 31 2003
Number of increasing runs in all permutations of [n-1] (n>=2). Example: a(4)=12 because we have 12 increasing runs in all the permutations of [3] (shown in parentheses): (123), (13)(2), (3)(12), (2)(13), (23)(1), (3)(2)(1). - Emeric Deutsch, Aug 28 2004
Minimum permanent over all n X n (0,1)-matrices with exactly n/2 zeros. - Simone Severini, Oct 15 2004
The number of permutations of 1..n that have 2 following 1 for n >= 1 is 0, 1, 3, 12, 60, 360, 2520, 20160, ... . - Jon Perry, Sep 20 2008
Starting (1, 3, 12, 60, ...) = binomial transform of A000153: (1, 2, 7, 32, 181, ...). - Gary W. Adamson, Dec 25 2008
First column of A092582. - Mats Granvik, Feb 08 2009
The asymptotic expansion of the higher order exponential integral E(x,m=1,n=3) ~ exp(-x)/x*(1 - 3/x + 12/x^2 - 60/x^3 + 360/x^4 - 2520/x^5 + 20160/x^6 - 81440/x^7 + ...) leads to the sequence given above. See A163931 and A130534 for more information. - Johannes W. Meijer, Oct 20 2009
For n>1: a(n) = A173333(n,2). - Reinhard Zumkeller, Feb 19 2010
Starting (1, 3, 12, 60, ...) = eigensequence of triangle A002260, (a triangle with k terms of (1,2,3,...) in each row given k=1,2,3,...). Example: a(6) = 360, generated from (1, 2, 3, 4, 5) dot (1, 1, 3, 12, 60) = (1 + 2 + 9 + 48 + 300). - Gary W. Adamson, Aug 02 2010
For n>=2: a(n) is the number of connected 2-regular labeled graphs on (n+1) nodes (Cf. A001205). - Geoffrey Critzer, Feb 16 2011.
The Fi1 and Fi2 triangle sums of A094638 are given by the terms of this sequence (n>=1). For the definition of these triangle sums see A180662. - Johannes W. Meijer, Apr 20 2011
Also [1, 1] together with the row sums of triangle A162608. - Omar E. Pol, Mar 09 2012
a(n-1) is, for n>=2, also the number of necklaces with n beads (only C_n symmetry, no turnover) with n-1 distinct colors and signature c[.]^2 c[.]^(n-2). This means that two beads have the same color, and for n=2 the second factor is omitted. Say, cyclic(c[1]c[1]c[2]c[3]..c[n-1]), in short 1123...(n-1), taken cyclically. E.g., n=2: 11, n=3: 112, n=4: 1123, 1132, 1213, n=5: 11234, 11243, 11324, 11342, 11423, 11432, 12134, 12143, 13124, 13142, 14123, 14132. See the next-to-last entry in line n>=2 of the representative necklace partition array A212359. - Wolfdieter Lang, Jun 26 2012
For m >= 3, a(m-1) is the number of distinct Hamiltonian circuits in a complete simple graph with m vertices. See also A001286. - Stanislav Sykora, May 10 2014
In factorial base (A007623) these numbers have a simple pattern: 1, 1, 1, 11, 200, 2200, 30000, 330000, 4000000, 44000000, 500000000, 5500000000, 60000000000, 660000000000, 7000000000000, 77000000000000, 800000000000000, 8800000000000000, 90000000000000000, 990000000000000000, etc. See also the formula based on this observation, given below. - Antti Karttunen, Dec 19 2015
Also (by definition) the independence number of the n-transposition graph. - Eric W. Weisstein, May 21 2017
Number of permutations of n letters containing an even number of even cycles. - Michael Somos, Jul 11 2018
Equivalent to Brewbaker's and Sykora's comments, a(n - 1) is the number of undirected cycles covering n labeled vertices, hence the logarithmic transform of A002135. - Gus Wiseman, Oct 20 2018
For n >= 2 and a set of n distinct leaf labels, a(n) is the number of binary, rooted, leaf-labeled tree topologies that have a caterpillar shape (column k=1 of A306364). - Noah A Rosenberg, Feb 11 2019
Also the clique covering number of the n-Bruhat graph. - Eric W. Weisstein, Apr 19 2019
a(n) is the number of lattices of the form [s,w] in the weak order on S_n, for a fixed simple reflection s. - Bridget Tenner, Jan 16 2020
For n > 3, a(n) = p_1^e_1*...*p_m^e_m, where p_1 = 2 and e_m = 1. There exists p_1^x where x <= e_1 such that p_1^x*p_m^e_m is a primitive Zumkeller number (A180332) and p_1^e_1*p_m^e_m is a Zumkeller number (A083207). Therefore, for n > 3, a(n) = p_1^e_1*p_m^e_m*r, where r is relatively prime to p_1*p_m, is also a Zumkeller number. - Ivan N. Ianakiev, Mar 11 2020
For n>1, a(n) is the number of permutations of [n] that have 1 and 2 as cycle-mates, that is, 1 and 2 are contained in the same cycle of a cyclic representation of permutations of [n]. For example, a(4) counts the 12 permutations with 1 and 2 as cycle-mates, namely, (1 2 3 4), (1 2 4 3), (1 3 2 4), (1 3 4 2), (1 4 2 3), (1 4 3 2), (1 2 3) (4), (1 3 2) (4), (1 2 4 )(3), (1 4 2)(3), (1 2)(3 4), and (1 2)(3)(4). Since a(n+2)=row sums of A162608, our result readily follows. - Dennis P. Walsh, May 28 2020

Examples

			G.f. = 1 + x + x^2 + 3*x^3 + 12*x^4 + 60*x^5 + 360*x^6 + 2520*x^7 + ...

References

  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 87-8, 20. (a), c_n^e(t=1).
  • 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. A000142, A000153, A000255, A001147, A001286, A001720, A002135, A002260, A007623, A007717, A049444, A049459, A093468, A094587, A094638, A138533, A153880, A173333, A213936, A215771, A319225, A319226, A320655.
a(n+1)= A046089(n, 1), n >= 1 (first column of triangle), A161739 (q(n) sequence).
Bisections are A002674 and A085990 (essentially).
Row 3 of A265609 (essentially).
Row sums of A307429.

Programs

  • Magma
    [1] cat [Order(AlternatingGroup(n)): n in [1..20]]; // Arkadiusz Wesolowski, May 17 2014
  • Maple
    seq(mul(k, k=3..n), n=0..20); # Zerinvary Lajos, Sep 14 2007
  • Mathematica
    a[n_]:= If[n > 2, n!/2, 1]; Array[a, 21, 0]
a[n_]:= If[n<3, 1, n*a[n-1]]; Array[a, 21, 0]; (* Robert G. Wilson v, Apr 16 2011 *)
a[ n_]:= If[n<0, 0, n! SeriesCoefficient[(2-x^2)/(2-2x), {x, 0, n}]]; (* Michael Somos, May 22 2014 *)
a[ n_]:= If[n<0, 0, n! SeriesCoefficient[1 +Sinh[-Log[1-x]], {x, 0, n}]]; (* Michael Somos, May 22 2014 *)
Numerator[Range[0, 20]!/2] (* Eric W. Weisstein, May 21 2017 *)
Table[GroupOrder[AlternatingGroup[n]], {n, 0, 20}] (* Eric W. Weisstein, May 21 2017 *)
  • PARI
    {a(n) = if( n<2, n>=0, n!/2)};
  • PARI
    a(n)=polcoeff(1+x*sum(m=0,n,m^m*x^m/(1+m*x+x*O(x^n))^m),n) \\ Paul D. Hanna
  • PARI
    A001710=n->n!\2+(n<2) \\ M. F. Hasler, Dec 01 2013
  • Python
    from math import factorial
def A001710(n): return factorial(n)>>1 if n > 1 else 1 # Chai Wah Wu, Feb 14 2023
  • SageMath
    def A001710(n): return (factorial(n) +int(n<2))//2
[A001710(n) for n in range(31)] # G. C. Greubel, Sep 28 2024
  • Scheme
    ;; Using memoization-macro definec for which an implementation can be found in http://oeis.org/wiki/Memoization
(definec (A001710 n) (cond ((<= n 2) 1) (else (* n (A001710 (- n 1))))))
;; Antti Karttunen, Dec 19 2015

Formula

a(n) = numerator(n!/2) and A141044(n) = denominator(n!/2).
D-finite with recurrence: a(0) = a(1) = a(2) = 1; a(n) = n*a(n-1) for n>2. - Chad Brewbaker, Jan 31 2003 [Corrected by N. J. A. Sloane, Jul 25 2008]
a(0) = 0, a(1) = 1; a(n) = Sum_{k=1..n-1} k*a(k). - Amarnath Murthy, Oct 29 2002
Stirling transform of a(n+1) = [1, 3, 12, 160, ...] is A083410(n) = [1, 4, 22, 154, ...]. - Michael Somos, Mar 04 2004
First Eulerian transform of A000027. See A000142 for definition of FET. - Ross La Haye, Feb 14 2005
From Paul Barry, Apr 18 2005: (Start)
a(n) = 0^n + Sum_{k=0..n} (-1)^(n-k-1)*T(n-1, k)*cos(Pi*(n-k-1)/2)^2.
T(n,k) = abs(A008276(n, k)). (End)
E.g.f.: (2 - x^2)/(2 - 2*x).
E.g.f. of a(n+2), n>=0, is 1/(1-x)^3.
E.g.f.: 1 + sinh(log(1/(1-x))). - Geoffrey Critzer, Dec 12 2010
a(n+1) = (-1)^n * A136656(n,1), n>=1.
a(n) = n!/2 for n>=2 (proof from the e.g.f). - Wolfdieter Lang, Apr 30 2010
a(n) = (n-2)! * t(n-1), n>1, where t(n) is the n-th triangular number (A000217). - Gary Detlefs, May 21 2010
a(n) = ( A000254(n) - 2* A001711(n-3) )/3, n>2. - Gary Detlefs, May 24 2010
O.g.f.: 1 + x*Sum_{n>=0} n^n*x^n/(1 + n*x)^n. - Paul D. Hanna, Sep 13 2011
a(n) = if n < 2 then 1, otherwise Pochhammer(n,n)/binomial(2*n,n). - Peter Luschny, Nov 07 2011
a(n) = Sum_{k=0..floor(n/2)} s(n,n-2*k) where s(n,k) are Stirling number of the first kind, A048994. - Mircea Merca, Apr 07 2012
a(n-1), n>=3, is M_1([2,1^(n-2)])/n = (n-1)!/2, with the M_1 multinomial numbers for the given n-1 part partition of n. See the second to last entry in line n>=3 of A036038, and the above necklace comment by W. Lang. - Wolfdieter Lang, Jun 26 2012
G.f.: A(x) = 1 + x + x^2/(G(0)-2*x) where G(k) = 1 - (k+1)*x/(1 - x*(k+3)/G(k+1)); (continued fraction). - Sergei N. Gladkovskii, Dec 26 2012.
G.f.: 1 + x + (Q(0)-1)*x^2/(2*(sqrt(x)+x)), where Q(k) = 1 + (k+2)*sqrt(x)/(1 - sqrt(x)/(sqrt(x) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 15 2013
G.f.: 1 + x + (x*Q(x)-x^2)/(2*(sqrt(x)+x)), where Q(x) = Sum_{n>=0} (n+1)!*x^n*sqrt(x)*(sqrt(x) + x*(n+2)). - Sergei N. Gladkovskii, May 15 2013
G.f.: 1 + x/2 + (Q(0)-1)*x/(2*(sqrt(x)+x)), where Q(k) = 1 + (k+1)*sqrt(x)/(1 - sqrt(x)/(sqrt(x) + 1/Q(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 15 2013
G.f.: 1 + x + x^2*G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(k+3)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013
G.f.: 1+x + x^2*W(0), where W(k) = 1 - x*(k+3)/( x*(k+3) - 1/(1 - x*(k+1)/( x*(k+1) - 1/W(k+1) ))); (continued fraction). - Sergei N. Gladkovskii, Aug 26 2013
From Antti Karttunen, Dec 19 2015: (Start)
a(0)=a(1)=1; after which, for even n: a(n) = (n/2) * (n-1)!, and for odd n: a(n) = (n-1)/2 * ((n-1)! + (n-2)!). [The formula was empirically found after viewing these numbers in factorial base, A007623, and is easily proved by considering formulas from Lang (Apr 30 2010) and Detlefs (May 21 2010) shown above.]
For n >= 1, a(2*n+1) = a(2*n) + A153880(a(2*n)). [Follows from above.] (End)
Inverse Stirling transform of a(n) is (-1)^(n-1)*A009566(n). - Anton Zakharov, Aug 07 2016
a(n) ~ sqrt(Pi/2)*n^(n+1/2)/exp(n). - Ilya Gutkovskiy, Aug 07 2016
a(n) = A006595(n-1)*n/A000124(n) for n>=2. - Anton Zakharov, Aug 23 2016
a(n) = A001563(n-1) - A001286(n-1) for n>=2. - Anton Zakharov, Sep 23 2016
From Peter Bala, May 24 2017: (Start)
The o.g.f. A(x) satisfies the Riccati equation x^2*A'(x) + (x - 1)*A(x) + 1 - x^2 = 0.
G.f.: A(x) = 1 + x + x^2/(1 - 3*x/(1 - x/(1 - 4*x/(1 - 2*x/(1 - 5*x/(1 - 3*x/(1 - ... - (n + 2)*x/(1 - n*x/(1 - ... ))))))))) (apply Stokes, 1982).
A(x) = 1 + x + x^2/(1 - 2*x - x/(1 - 3*x/(1 - 2*x/(1 - 4*x/(1 - 3*x/(1 - 5*x/(1 - ... - n*x/(1 - (n+2)*x/(1 - ... ))))))))). (End)
H(x) = (1 - (1 + x)^(-2)) / 2 = x - 3*x^2/2! + 12*x^3/3! - ..., an e.g.f. for the signed sequence here (n!/2!), ignoring the first two terms, is the compositional inverse of G(x) = (1 - 2*x)^(-1/2) - 1 = x + 3*x^2/2! + 15*x^3/3! + ..., an e.g.f. for A001147. Cf. A094638. H(x) is the e.g.f. for the sequence (-1)^m * m!/2 for m = 2,3,4,... . Cf. A001715 for n!/3! and A001720 for n!/4!. Cf. columns of A094587, A173333, and A213936 and rows of A138533. - Tom Copeland, Dec 27 2019
From Amiram Eldar, Jan 08 2023: (Start)
Sum_{n>=0} 1/a(n) = 2*(e-1).
Sum_{n>=0} (-1)^n/a(n) = 2/e. (End)

Extensions

More terms from Larry Reeves (larryr(AT)acm.org), Aug 20 2001
Further terms from Simone Severini, Oct 15 2004

A007559 Triple factorial numbers (3*n-2)!!! with leading 1 added.

Original entry on oeis.org

1, 1, 4, 28, 280, 3640, 58240, 1106560, 24344320, 608608000, 17041024000, 528271744000, 17961239296000, 664565853952000, 26582634158080000, 1143053268797440000, 52580450364682240000, 2576442067869429760000, 133974987529210347520000, 7368624314106569113600000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of increasing quaternary trees on n vertices. (See A001147 for ternary and A000142 for binary trees.) - David Callan, Mar 30 2007
a(n) is the product of the positive integers k <= 3*n that have k modulo 3 = 1. - Peter Luschny, Jun 23 2011
See A094638 for connections to differential operators. - Tom Copeland, Sep 20 2011
Partial products of A016777. - Reinhard Zumkeller, Sep 20 2013
For n > 2, a(n) is a Zumkeller number. - Ivan N. Ianakiev, Jan 28 2020
a(n) is the number of generalized permutations of length n related to the degenerate Eulerian numbers (see arXiv:2007.13205), cf. A336633. - Orli Herscovici, Jul 28 2020

Examples

			G.f. = 1 + x + 4*x^2 + 28*x^3 + 280*x^4 + 3640*x^5 + 58240*x^6 + ...
a(3) = 28 and a(4) = 280; with top row of M^3 = (28, 117, 108, 27), sum = 280.

References

  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A001147, A004987, A008544, A032031, A051141, A129116.
a(n)= A035469(n, 1), n >= 1, (first column of triangle A035469(n, m)).
Cf. A107716. - Gary W. Adamson, Oct 22 2009
Cf. A095660. - Gary W. Adamson, Jul 19 2011
Subsequence of A007661. A007696, A008548.
a(n) = A286718(n,0), n >= 0.
Row sums of A336633.

Programs

  • GAP
    List([0..20], n-> Product([0..n-1], k-> 3*k+1 )); # G. C. Greubel, Aug 20 2019
  • Haskell
    a007559 n = a007559_list !! n
a007559_list = scanl (*) 1 a016777_list
-- Reinhard Zumkeller, Sep 20 2013
  • Magma
    b:= func< n | (n lt 2) select n else (3*n-2)*Self(n-1) >;
[1] cat [b(n): n in [1..20]]; // G. C. Greubel, Aug 20 2019
  • Maple
    A007559 := n -> mul(k, k = select(k-> k mod 3 = 1, [$1 .. 3*n])): seq(A007559(n), n = 0 .. 17); # Peter Luschny, Jun 23 2011
# second Maple program:
b:= proc(n) option remember; `if`(n<1, 1, n*b(n-3)) end:
a:= n-> b(3*n-2):
seq(a(n), n=0..20);  # Alois P. Heinz, Dec 18 2024
  • Mathematica
    a[ n_] := If[ n < 0, 1 / Product[ k, {k, - 2, 3 n - 1, -3}],
  Product[ k, {k, 1, 3 n - 2, 3}]]; (* Michael Somos, Oct 14 2011 *)
FoldList[Times,1,Range[1,100,3]] (* Harvey P. Dale, Jul 05 2013 *)
Range[0, 19]! CoefficientList[Series[((1 - 3 x)^(-1/3)), {x, 0, 19}], x] (* Vincenzo Librandi, Oct 08 2015 *)
  • Maxima
    a(n):=if n=1 then 1 else (n)!*(sum(m/n*sum(binomial(k,n-m-k)*(-1/3)^(n-m-k)* binomial (k+n-1,n-1),k,1,n-m),m,1,n)+1); /* Vladimir Kruchinin, Aug 09 2010 */
  • PARI
    {a(n) = if( n<0, (-1)^n / prod(k=0,-1-n, 3*k + 2), prod(k=0, n-1, 3*k + 1))}; /* Michael Somos, Oct 14 2011 */
  • PARI
    my(x='x+O('x^33)); Vec(serlaplace((1-3*x)^(-1/3))) /* Joerg Arndt, Apr 24 2011 */
  • Sage
    def A007559(n) : return mul(j for j in range(1,3*n,3))
[A007559(n) for n in (0..17)]  # Peter Luschny, May 20 2013

Formula

a(n) = Product_{k=0..n-1} (3*k + 1).
a(n) = (3*n - 2)!!!.
a(n) = A007661(3*n-2).
E.g.f.: (1-3*x)^(-1/3).
a(n) ~ sqrt(2*Pi)/Gamma(1/3)*n^(-1/6)*(3*n/e)^n*(1 - (1/36)/n - ...). - Joe Keane (jgk(AT)jgk.org), Nov 22 2001
a(n) = 3^n*Pochhammer(1/3, n).
a(n) = Sum_{k=0..n} (-3)^(n-k)*A048994(n, k). - Philippe Deléham, Oct 29 2005
a(n) = n!*(1+Sum_{m=1..n} (m/n)*Sum_{k=1..n-m} binomial(k, n-m-k)*(-1/3)^(n-m-k)*binomial(k+n-1, n-1)), n>1. - Vladimir Kruchinin, Aug 09 2010
From Gary W. Adamson, Jul 19 2011: (Start)
a(n) = upper left term in M^n, M = a variant of Pascal (1,3) triangle (Cf. A095660); as an infinite square production matrix:
1, 3, 0, 0, 0,...
1, 4, 3, 0, 0,...
1, 5, 7, 3, 0,...
...
a(n+1) = sum of top row terms of M^n. (End)
a(n) = (-2)^n*Sum_{k=0..n} (3/2)^k*s(n+1,n+1-k), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012
G.f.: 1/Q(0) where Q(k) = 1 - x*(3*k+1)/( 1 - x*(3*k+3)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 21 2013
G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(3*k+1)/(x*(3*k+1) + 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
E.g.f.: E(0)/2, where E(k)= 1 + 1/(1 - x*(3*k+1)/(x*(3*k+1) + (k+1)/E(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 26 2013
Let D(x) = 1/sqrt(1 - 2*x) be the e.g.f. for the sequence of double factorial numbers A001147. Then the e.g.f. A(x) for the triple factorial numbers satisfies D( Integral_{t=0..x} A(t) dt ) = A(x). Cf. A007696 and A008548. - Peter Bala, Jan 02 2015
O.g.f.: hypergeom([1, 1/3], [], 3*x). - Peter Luschny, Oct 08 2015
a(n) = 3^n * Gamma(n + 1/3)/Gamma(1/3). - Artur Jasinski, Aug 23 2016
a(n) = sigma[3,1]^{(n)}n, n >= 0, with the elementary symmetric function of degree n in the n numbers 1, 4, 7, ..., 1+3*(n-1), with sigma[3,1]^{(n)}_0 := 1. See the first formula. - _Wolfdieter Lang, May 29 2017
a(n) = (-1)^n / A008544(n), 0 = a(n)*(+3*a(n+1) -a(n+2)) +a(n+1)*a(n+1) for all n in Z. - Michael Somos, Sep 30 2018
D-finite with recurrence: a(n) +(-3*n+2)*a(n-1)=0, n>=1. - R. J. Mathar, Feb 14 2020
Sum_{n>=1} 1/a(n) = (e/9)^(1/3) * (Gamma(1/3) - Gamma(1/3, 1/3)). - Amiram Eldar, Jun 29 2020

Extensions

Better description from Wolfdieter Lang

A003422 Left factorials: !n = Sum_{k=0..n-1} k!.

Original entry on oeis.org

0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114, 4037914, 43954714, 522956314, 6749977114, 93928268314, 1401602636314, 22324392524314, 378011820620314, 6780385526348314, 128425485935180314, 2561327494111820314, 53652269665821260314, 1177652997443428940314
Offset: 0

Views

Author

N. J. A. Sloane, R. K. Guy

Keywords

Comments

Number of {12, 12*, 1*2, 21*}- and {12, 12*, 21, 21*}-avoiding signed permutations in the hyperoctahedral group.
a(n) is the number of permutations on [n] that avoid the patterns 2n1 and n12. An occurrence of a 2n1 pattern is a (scattered) subsequence a-n-b with a > b. - David Callan, Nov 29 2007
Also, numbers left over after the following sieving process: At step 1, keep all numbers of the set N = {0, 1, 2, ...}. In step 2, keep only every second number after a(2) = 2: N' = {0, 1, 2, 4, 6, 8, 10, ...}. In step 3, keep every third of the numbers following a(3) = 4, N" = {0, 1, 2, 4, 10, 16, 22, ...}. In step 4, keep every fourth of the numbers beyond a(4) = 10: {0, 1, 2, 4, 10, 34, 58, ...}, and so on. - M. F. Hasler, Oct 28 2010
If s(n) is a second-order recurrence defined as s(0) = x, s(1) = y, s(n) = n*(s(n - 1) - s(n - 2)), n > 1, then s(n) = n*y - n*a(n - 1)*x. - Gary Detlefs, May 27 2012
a(n) is the number of lists of {1, ..., n} with (1st element) = (smallest element) and (k-th element) <> (k-th smallest element) for k > 1, where a list means an ordered subset. a(4) = 10 because we have the lists: [1], [2], [3], [4], [1, 3, 2], [1, 4, 2], [1, 4, 3], [2, 4, 3], [1, 3, 4, 2], [1, 4, 2, 3]. Cf. A000262. - Geoffrey Critzer, Oct 04 2012
Consider a tree graph with 1 vertex. Add an edge to it with another vertex. Now add 2 edges with vertices to this vertex, and then 3 edges to each open vertex of the tree (not the first one!), and the next stage is to add 4 edges, and so on. The total number of vertices at each stage give this sequence (see example). - Jon Perry, Jan 27 2013
Additive version of the superfactorials A000178. - Jon Perry, Feb 09 2013
Repunits in the factorial number system (see links). - Jon Perry, Feb 17 2013
Whether n|a(n) only for 1 and 2 remains an open problem. A published 2004 proof was retracted in 2011. This is sometimes known as Kurepa's conjecture. - Robert G. Wilson v, Jun 15 2013, corrected by Jeppe Stig Nielsen, Nov 07 2015.
!n is not always squarefree for n > 3. Miodrag Zivkovic found that 54503^2 divides !26541. - Arkadiusz Wesolowski, Nov 20 2013
a(n) gives the position of A007489(n) in A227157. - Antti Karttunen, Nov 29 2013
Matches the total domination number of the Bruhat graph from n = 2 to at least n = 5. - Eric W. Weisstein, Jan 11 2019
For the connection with Kurepa trees, see A. Petojevic, The {K_i(z)}{i=1..oo} functions, Rocky Mtn. J. Math., 36 (2006), 1637-1650. - _Aleksandar Petojevic, Jun 29 2018
This sequence converges in the p-adic topology, for every prime number p. - Harry Richman, Aug 13 2024

Examples

			!5 = 0! + 1! + 2! + 3! + 4! = 1 + 1 + 2 + 6 + 24 = 34.
x + 2*x^2 + 4*x^3 + 10*x^4 + 34*x^5 + 154*x^6 + 874*x^7 + 5914*x^8 + 46234*x^9 + ...
From _Arkadiusz Wesolowski_, Aug 06 2012: (Start)
Illustration of initial terms:
.
. o        o         o            o                         o
.          o         o            o                         o
.                   o o          o o                       o o
.                              ooo ooo                   ooo ooo
.                                             oooo oooo oooo oooo oooo oooo
.
. 1        2         4            10                        34
.
(End)
The tree graph. The total number of vertices at each stage is 1, 2, 4, 10, ...
    0 0
    |/
    0-0
   /
0-0
   \
    0-0
    |\
    0 0
- _Jon Perry_, Jan 27 2013

References

  • Richard K. Guy, Unsolved Problems Number Theory, Section B44.
  • D. Kurepa, On the left factorial function !n. Math. Balkanica 1 1971 147-153.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Equals A007489(n-1)+1 for n>=1. Cf. A000142, A014144, A005165.
Twice A014288. See also A049782, A100612.
Cf. A102639, A102411, A102412, A101752, A094216, A094638, A008276, A000166, A000110, A000204, A000045, A000108, A135722, A227157, A000178, A137338, A232845, A357145.

Programs

  • Haskell
    a003422 n = a003422_list !! n
a003422_list = scanl (+) 0 a000142_list
-- Reinhard Zumkeller, Dec 27 2011
  • Maple
    A003422 := proc(n) local k; add(k!,k=0..n-1); end proc:
# Alternative, using the Charlier polynomials A137338:
C := proc(n, x) option remember; if n > 0 then (x-n)*C(n-1, x) - n*C(n-2, x)
elif n = 0 then 1 else 0 fi end: A003422 := n -> (-1)^(n+1)*C(n-1, -1):
seq(A003422(n), n=0..22); # Peter Luschny, Nov 28 2018
# third Maple program:
a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+(n-1)!) end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 24 2022
  • Mathematica
    Table[Sum[i!, {i, 0, n - 1}], {n, 0, 20}] (* Stefan Steinerberger, Mar 31 2006 *)
Join[{0}, Accumulate[Range[0, 25]!]] (* Harvey P. Dale, Nov 19 2011 *)
a[0] = 0; a[1] = 1; a[n_] := a[n] = n*a[n - 1] - (n - 1)*a[n - 2]; Array[a, 23, 0] (* Robert G. Wilson v, Jun 15 2013 *)
a[n_] := (-1)^n*n!*Subfactorial[-n-1]-Subfactorial[-1]; Table[a[n] // FullSimplify, {n, 0, 22}] (* Jean-François Alcover, Jan 09 2014 *)
RecurrenceTable[{a[n] == n a[n - 1] - (n - 1) a[n - 2], a[0] == 0, a[1] == 1}, a, {n, 0, 10}] (* Eric W. Weisstein, Jan 11 2019 *)
Range[0, 20]! CoefficientList[Series[(ExpIntegralEi[1] - ExpIntegralEi[1 - x]) Exp[x - 1], {x, 0, 20}], x] (* Eric W. Weisstein, Jan 11 2019 *)
Table[(-1)^n n! Subfactorial[-n - 1] - Subfactorial[-1], {n, 0, 20}] // FullSimplify (* Eric W. Weisstein, Jan 11 2019 *)
Table[(I Pi + ExpIntegralEi[1] + (-1)^n n! Gamma[-n, -1])/E, {n, 0, 20}] // FullSimplify (* Eric W. Weisstein, Jan 11 2019 *)
  • Maxima
    makelist(sum(k!,k,0,n-1), n, 0, 20); /* Stefano Spezia, Jan 11 2019 */
  • PARI
    a003422(n)=sum(k=0,n-1,k!) \\ Charles R Greathouse IV, Jun 15 2011
  • Python
    from itertools import count, islice
def A003422_gen(): # generator of terms
    yield from (0,1)
    c, f = 1, 1
    for n in count(1):
        yield (c:= c + (f:= f*n))
A003422_list = list(islice(A003422_gen(),20)) # Chai Wah Wu, Jun 22 2022
  • Python
    def a(n):
    if n == 0: return 0
    s = f = 1
    for k in range(1, n):
        f *= k
        s += f
    return round(s)
print([a(n) for n in range(24)])  # Peter Luschny, Mar 05 2024

Formula

D-finite with recurrence: a(n) = n*a(n - 1) - (n - 1)*a(n - 2). - Henry Bottomley, Feb 28 2001
Sequence is given by 1 + 1*(1 + 2*(1 + 3*(1 + 4*(1 + ..., terminating in n*(1)...). - Jon Perry, Jun 01 2004
a(n) = Sum_{k=0..n-1} P(n, k) / C(n, k). - Ross La Haye, Sep 20 2004
E.g.f.: (Ei(1) - Ei(1 - x))*exp(-1 + x) where Ei(x) is the exponential integral. - Djurdje Cvijovic and Aleksandar Petojevic, Apr 11 2000
a(n) = Integral_{x = 0..oo} [(x^n - 1)/(x - 1)]*exp(-x) dx. - Gerald McGarvey, Oct 12 2007
A007489(n) = !(n + 1) - 1 = a(n + 1) - 1. - Artur Jasinski, Nov 08 2007. Typos corrected by Antti Karttunen, Nov 29 2013
Starting (1, 2, 4, 10, 34, 154, ...), = row sums of triangle A135722. - Gary W. Adamson, Nov 25 2007
a(n) = a(n - 1) + (n - 1)! for n >= 2. - Jaroslav Krizek, Jun 16 2009
E.g.f. A(x) satisfies the differential equation A'(x) = A(x) + 1/(1 - x). - Vladimir Kruchinin, Jan 19 2011
a(n + 1) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = A182386(k) for k = 0, 1, ..., n. - Michael Somos, Apr 27 2012
From Sergei N. Gladkovskii, May 09 2013 to Oct 22 2013: (Start)
Continued fractions:
G.f.: x/(1-x)*Q(0) where Q(k) = 1 + (2*k + 1)*x/( 1 - 2*x*(k+1)/(2*x*(k+1) + 1/Q(k+1))).
G.f.: G(0)*x/(1-x)/2 where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + 1/G(k+1))).
G.f.: 2*x/(1-x)/G(0) where G(k) = 1 + 1/(1 - 1/(1 - 1/(2*x*(k+1)) + 1/G(k+1))).
G.f.: W(0)*x/(1+sqrt(x))/(1-x) where W(k) = 1 + sqrt(x)/(1 - sqrt(x)*(k+1)/(sqrt(x)*(k+1) + 1/W(k+1))).
G.f.: B(x)*(1+x)/(1-x) where B(x) is the g.f. of A153229.
G.f.: x/(1-x) + x^2/(1-x)/Q(0) where Q(k) = 1 - 2*x*(2*k+1) - x^2*(2*k+1)*(2*k+2)/(1 - 2*x*(2*k+2) - x^2*(2*k+2)*(2*k+3)/Q(k+1)).
G.f.: x*(1+x)*B(x) where B(x) is the g.f. of A136580. (End)
a(n) = (-1)^(n+1)*C(n-1, -1) where C(n, x) are the Charlier polynomials (with parameter a=1) as given in A137338. (Evaluation at x = 1 gives A232845.) - Peter Luschny, Nov 28 2018
a(n) = (a(n-3)*(n-2)^2*(n-3)! + a(n-1)^2)/a(n-2) (empirical). - Gary Detlefs, Feb 25 2022
a(n) = signum(n)/b(1,n) with b(i,n) = i - [iMohammed Bouras, Sep 07 2022
Sum_{n>=1} 1/a(n) = A357145. - Amiram Eldar, Oct 01 2022

A008297 Triangle of Lah numbers.

Original entry on oeis.org

-1, 2, 1, -6, -6, -1, 24, 36, 12, 1, -120, -240, -120, -20, -1, 720, 1800, 1200, 300, 30, 1, -5040, -15120, -12600, -4200, -630, -42, -1, 40320, 141120, 141120, 58800, 11760, 1176, 56, 1, -362880, -1451520, -1693440, -846720, -211680, -28224, -2016, -72, -1, 3628800, 16329600, 21772800, 12700800
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

|a(n,k)| = number of partitions of {1..n} into k lists, where a list means an ordered subset.
Let N be a Poisson random variable with parameter (mean) lambda, and Y_1,Y_2,... independent exponential(theta) variables, independent of N, so that their density is given by (1/theta)*exp(-x/theta), x > 0. Set S=Sum_{i=1..N} Y_i. Then E(S^n), i.e., the n-th moment of S, is given by (theta^n) * L_n(lambda), n >= 0, where L_n(y) is the Lah polynomial Sum_{k=0..n} |a(n,k)| * y^k. - Shai Covo (green355(AT)netvision.net.il), Feb 09 2010
For y = lambda > 0, formula 2) for the Lah polynomial L_n(y) dated Feb 02 2010 can be restated as follows: L_n(lambda) is the n-th ascending factorial moment of the Poisson distribution with parameter (mean) lambda. - Shai Covo (green355(AT)netvision.net.il), Feb 10 2010
See A111596 for an expression of the row polynomials in terms of an umbral composition of the Bell polynomials and relation to an inverse Mellin transform and a generalized Dobinski formula. - Tom Copeland, Nov 21 2011
Also the Bell transform of the sequence (-1)^(n+1)*(n+1)! without column 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 28 2016
Named after the Slovenian mathematician and actuary Ivo Lah (1896-1979). - Amiram Eldar, Jun 13 2021

Examples

			|a(2,1)| = 2: (12), (21); |a(2,2)| = 1: (1)(2). |a(4,1)| = 24: (1234) (24 ways); |a(4,2)| = 36: (123)(4) (6*4 ways), (12)(34) (3*4 ways); |a(4,3)| = 12: (12)(3)(4) (6*2 ways); |a(4,4)| = 1: (1)(2)(3)(4) (1 way).
Triangle:
    -1;
     2,    1;
    -6,   -6,   -1;
    24,   36,   12,   1;
  -120, -240, -120, -20, -1; ...

References

  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 156.
  • Shai Covo, The moments of a compound Poisson process with exponential or centered normal jumps, J. Probab. Stat. Sci., Vol. 7, No. 1 (2009), pp. 91-100.
  • Theodore S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176; the sequence called {!}^{n+}. For a link to this paper see A000262.
  • John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 44.
  • S. Gill Williamson, Combinatorics for Computer Science, Computer Science Press, 1985; see p. 176.

Links

Crossrefs

Same as A066667 and A105278 except for signs. Other variants: A111596 (differently signed triangle and (0,0)-based), A271703 (unsigned and (0,0)-based), A089231.
A293125 (row sums) and A000262 (row sums of unsigned triangle).
Columns 1-6 (unsigned): A000142, A001286, A001754, A001755, A001777, A001778.
A002868 gives maximal element (in magnitude) in each row.
A248045 (central terms, negated). A130561 is a natural refinement.
Cf. A007318, A048786, A001263, A008275, A008277, A048993, A094638, A130534.
Cf. A008296, A360177.

Programs

  • Haskell
    a008297 n k = a008297_tabl !! (n-1) !! (k-1)
a008297_row n = a008297_tabl !! (n-1)
a008297_tabl = [-1] : f [-1] 2 where
   f xs i = ys : f ys (i + 1) where
     ys = map negate $
          zipWith (+) ([0] ++ xs) (zipWith (*) [i, i + 1 ..] (xs ++ [0]))
-- Reinhard Zumkeller, Sep 30 2014
  • Maple
    A008297 := (n,m) -> (-1)^n*n!*binomial(n-1,m-1)/m!;
  • Mathematica
    a[n_, m_] := (-1)^n*n!*Binomial[n-1, m-1]/m!; Table[a[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Dec 12 2012, after Maple *)
T[n_, n_] := (-1)^n; T[n_, k_]/;0Oliver Seipel, Dec 06 2024 *)
  • PARI
    T(n, m) = (-1)^n*n!*binomial(n-1, m-1)/m!
for(n=1,9, for(m=1,n, print1(T(n,m)", "))) \\ Charles R Greathouse IV, Mar 09 2016
  • Perl
    use bigint; use ntheory ":all"; my @L; for my $n (1..9) { push @L, map { stirling($n,$,3)*(-1)**$n } 1..$n; } say join(", ",@L); # _Dana Jacobsen, Mar 16 2017
  • Sage
    def A008297_triangle(dim): # computes unsigned T(n, k).
    M = matrix(ZZ,dim,dim)
    for n in (0..dim-1): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1]+(2+2*k)*M[n-1,k]+((k+1)*(k+2))*M[n-1,k+1]
    return M
A008297_triangle(9) # Peter Luschny, Sep 19 2012

Formula

a(n, m) = (-1)^n*n!*A007318(n-1, m-1)/m!, n >= m >= 1.
a(n+1, m) = (n+m)*a(n, m)+a(n, m-1), a(n, 0) := 0; a(n, m) := 0, n < m; a(1, 1)=1.
a(n, m) = ((-1)^(n-m+1))*L(1, n-1, m-1) where L(1, n, m) is the triangle of coefficients of the generalized Laguerre polynomials n!*L(n, a=1, x). These polynomials appear in the radial l=0 eigen-functions for discrete energy levels of the H-atom.
|a(n, m)| = Sum_{k=m..n} |A008275(n, k)|*A008277(k, m), where A008275 = Stirling numbers of first kind, A008277 = Stirling numbers of second kind. - Wolfdieter Lang
If L_n(y) = Sum_{k=0..n} |a(n, k)|*y^k (a Lah polynomial) then the e.g.f. for L_n(y) is exp(x*y/(1-x)). - Vladeta Jovovic, Jan 06 2001
E.g.f. for the k-th column (unsigned): x^k/(1-x)^k/k!. - Vladeta Jovovic, Dec 03 2002
a(n, k) = (n-k+1)!*N(n, k) where N(n, k) is the Narayana triangle A001263. - Philippe Deléham, Jul 20 2003
From Shai Covo (green355(AT)netvision.net.il), Feb 02 2010: (Start)
We have the following expressions for the Lah polynomial L_n(y) = Sum_{k=0..n} |a(n, k)|*y^k -- exact generalizations of results in A000262 for A000262(n) = L_n(1):
1) L_n(y) = y*exp(-y)*n!*M(n+1,2,y), n >= 1, where M (=1F1) is the confluent hypergeometric function of the first kind;
2) L_n(y) = exp(-y)* Sum_{m>=0} y^m*[m]^n/m!, n>=0, where [m]^n = m*(m+1)*...*(m+n-1) is the rising factorial;
3) L_n(y) = (2n-2+y)L_{n-1}(y)-(n-1)(n-2)L_{n-2}(y), n>=2;
4) L_n(y) = y*(n-1)!*Sum_{k=1..n} (L_{n-k}(y) k!)/((n-k)! (k-1)!), n>=1. (End)
The row polynomials are given by D^n(exp(-x*t)) evaluated at x = 0, where D is the operator (1-x)^2*d/dx. Cf. A008277 and A035342. - Peter Bala, Nov 25 2011
n!C(-xD,n) = Lah(n,:xD:) where C(m,n) is the binomial coefficient, xD= x d/dx, (:xD:)^k = x^k D^k, and Lah(n,x) are the row polynomials of this entry. E.g., 2!C(-xD,2)= 2 xD + x^2 D^2. - Tom Copeland, Nov 03 2012
From Tom Copeland, Sep 25 2016: (Start)
The Stirling polynomials of the second kind A048993 (A008277), i.e., the Bell-Touchard-exponential polynomials B_n[x], are umbral compositional inverses of the Stirling polynomials of the first kind signed A008275 (A130534), i.e., the falling factorials, (x)_n = n! binomial(x,n); that is, umbrally B_n[(x).] = x^n = (B.[x])_n.
An operational definition of the Bell polynomials is (xD_x)^n = B_n[:xD:], where, by definition, (:xD_x:)^n = x^n D_x^n, so (B.[:xD_x:])_n = (xD_x)_n = :xD_x:^n = x^n (D_x)^n.
Let y = 1/x, then D_x = -y^2 D_y; xD_x = -yD_y; and P_n(:yD_y:) = (-yD_y)_n = (-1)^n (1/y)^n (y^2 D_y)^n, the row polynomials of this entry in operational form, e.g., P_3(:yD_y:) = (-yD_y)_3 = (-yD_y) (yD_y-1) (yD_y-2) = (-1)^3 (1/y)^3 (y^2 D_y)^3 = -( 6 :yD_y: + 6 :yD_y:^2 + :yD_y:^3 ) = - ( 6 y D_y + 6 y^2 (D_y)^2 + y^3 (D_y)^3).
Therefore, P_n(y) = e^(-y) P_n(:yD_y:) e^y = e^(-y) (-1/y)^n (y^2 D_y)^n e^y = e^(-1/x) x^n (D_x)^n e^(1/x) = P_n(1/x) and P_n(x) = e^(-1/x) x^n (D_x)^n e^(1/x) = e^(-1/x) (:x D_x:)^n e^(1/x). (Cf. also A094638.) (End)
T(n,k) = Sum_{j=k..n} (-1)^j*A008296(n,j)*A360177(j,k). - Mélika Tebni, Feb 02 2023
Showing 1-10 of 62 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.