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

A007318 Pascal's triangle read by rows: C(n,k) = binomial(n,k) = n!/(k!*(n-k)!), 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 6, 4, 1, 1, 5, 10, 10, 5, 1, 1, 6, 15, 20, 15, 6, 1, 1, 7, 21, 35, 35, 21, 7, 1, 1, 8, 28, 56, 70, 56, 28, 8, 1, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11, 1
Offset: 0

Views

Author

N. J. A. Sloane and Mira Bernstein, Apr 28 1994

Keywords

Comments

A. W. F. Edwards writes: "It [the triangle] was first written down long before 1654, the year in which Blaise Pascal wrote his Traité du triangle arithmétique, but it was this work that brought together all the different aspects of the numbers for the first time. In it Pascal developed the properties of the number as a piece of pure mathematics ... and then, in a series of appendices, showed how these properties were relevant to the study of the figurate numbers, to the theory of combinations, to the expansion of binomial expressions, and to the solution of an important problem in the theory of probability." (A. W. F. Edwards, Pascal's Arithmetical Triangle, Johns Hopkins University Press (2002), p. xiii)
Edwards reports that the naming of the triangle after Pascal was done first by Montmort in 1708 as the "Table de M. Pascal pour les combinaisons" and then by De Moivre in 1730 as the "Triangulum Arithmeticum PASCALANIUM". (Edwards, p. xiv)
In China, Yang Hui in 1261 listed the coefficients of (a+b)^n up to n=6, crediting the expansion to Chia Hsein's Shih-so suan-shu circa 1100. Another prominent early use was in Chu Shih-Chieh's Precious Mirror of the Four Elements in 1303. (Edwards, p. 51)
In Persia, Al-Karaji discovered the binomial triangle "some time soon after 1007", and Al-Samawal published it in the Al-bahir some time before 1180. (Edwards, p. 52)
In India, Halayuda's commentary (circa 900) on Pingala's treatise on syllabic combinations (circa 200 B.C.E.) contains a clear description of the additive computation of the triangle. (Amulya Kumar Bag, Binomial Theorem in Ancient India, p. 72)
Also in India, the multiplicative formula for C(n,k) was known to Mahavira in 850 and restated by Bhaskara in 1150. (Edwards, p. 27)
In Italy, Tartaglia published the triangle in his General trattato (1556), and Cardano published it in his Opus novum (1570). (Edwards, p. 39, 44) - Russ Cox, Mar 29 2022
Also sometimes called Omar Khayyam's triangle.
Also sometimes called Yang Hui's triangle.
C(n,k) = number of k-element subsets of an n-element set.
Row n gives coefficients in expansion of (1+x)^n.
Binomial(n+k-1,n-1) is the number of ways of placing k indistinguishable balls into n boxes (the "bars and stars" argument - see Feller).
Binomial(n-1,k-1) is the number of compositions (ordered partitions) of n with k summands.
Binomial(n+k-1,k-1) is the number of weak compositions (ordered weak partitions) of n into exactly k summands. - Juergen Will, Jan 23 2016
Binomial(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (1,0) and (1,1). - Joerg Arndt, Jul 01 2011
If thought of as an infinite lower triangular matrix, inverse begins:
+1
-1 +1
+1 -2 +1
-1 +3 -3 +1
+1 -4 +6 -4 +1
All 2^n palindromic binomial coefficients starting after the A006516(n)-th entry are odd. - Lekraj Beedassy, May 20 2003
Binomial(n+k-1,n-1) is the number of standard tableaux of shape (n,1^k). - Emeric Deutsch, May 13 2004
Can be viewed as an array, read by antidiagonals, where the entries in the first row and column are all 1's and A(i,j) = A(i-1,j) + A(i,j-1) for all other entries. The determinant of each of its n X n subarrays starting at (0,0) is 1. - Gerald McGarvey, Aug 17 2004
Also the lower triangular readout of the exponential of a matrix whose entry {j+1,j} equals j+1 (and all other entries are zero). - Joseph Biberstine (jrbibers(AT)indiana.edu), May 26 2006
Binomial(n-3,k-1) counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 132 and k descents. Binomial(n-3,k-1) also counts the permutations in S_n which have zero occurrences of the pattern 231 and one occurrence of the pattern 213 and k descents. - David Hoek (david.hok(AT)telia.com), Feb 28 2007
Inverse of A130595 (as an infinite lower triangular matrix). - Philippe Deléham, Aug 21 2007
Consider integer lists LL of lists L of the form LL = [m#L] = [m#[k#2]] (where '#' means 'times') like LL(m=3,k=3) = [[2,2,2],[2,2,2],[2,2,2]]. The number of the integer list partitions of LL(m,k) is equal to binomial(m+k,k) if multiple partitions like [[1,1],[2],[2]] and [[2],[2],[1,1]] and [[2],[1,1],[2]] are counted only once. For the example, we find 4*5*6/3! = 20 = binomial(6,3). - Thomas Wieder, Oct 03 2007
The infinitesimal generator for Pascal's triangle and its inverse is A132440. - Tom Copeland, Nov 15 2007
Row n>=2 gives the number of k-digit (k>0) base n numbers with strictly decreasing digits; e.g., row 10 for A009995. Similarly, row n-1>=2 gives the number of k-digit (k>1) base n numbers with strictly increasing digits; see A009993 and compare A118629. - Rick L. Shepherd, Nov 25 2007
From Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008: (Start)
Binomial(n+k-1, k) is the number of ways a sequence of length k can be partitioned into n subsequences (see the Naish link).
Binomial(n+k-1, k) is also the number of n- (or fewer) digit numbers written in radix at least k whose digits sum to k. For example, in decimal, there are binomial(3+3-1,3)=10 3-digit numbers whose digits sum to 3 (see A052217) and also binomial(4+2-1,2)=10 4-digit numbers whose digits sum to 2 (see A052216). This relationship can be used to generate the numbers of sequences A052216 to A052224 (and further sequences using radix greater than 10). (End)
From Milan Janjic, May 07 2008: (Start)
Denote by sigma_k(x_1,x_2,...,x_n) the elementary symmetric polynomials. Then:
Binomial(2n+1,2k+1) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2(i*Pi/(2n+1)), (i=1,2,...,n).
Binomial(2n,2k+1) = 2n*sigma_{n-1-k}(x_1,x_2,...,x_{n-1}), where x_i = tan^2(i*Pi/(2n)), (i=1,2,...,n-1).
Binomial(2n,2k) = sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n)), (i=1,2,...,n).
Binomial(2n+1,2k) = (2n+1)sigma_{n-k}(x_1,x_2,...,x_n), where x_i = tan^2((2i-1)Pi/(4n+2)), (i=1,2,...,n). (End)
Given matrices R and S with R(n,k) = binomial(n,k)*r(n-k) and S(n,k) = binomial(n,k)*s(n-k), then R*S = T where T(n,k) = binomial(n,k)*[r(.)+s(.)]^(n-k), umbrally. And, the e.g.f.s for the row polynomials of R, S and T are, respectively, exp(x*t)*exp[r(.)*x], exp(x*t)*exp[s(.)*x] and exp(x*t)*exp[r(.)*x]*exp[s(.)*x] = exp{[t+r(.)+s(.)]*x}. The row polynomials are essentially Appell polynomials. See A132382 for an example. - Tom Copeland, Aug 21 2008
As the rectangle R(m,n) = binomial(m+n-2,m-1), the weight array W (defined generally at A144112) of R is essentially R itself, in the sense that if row 1 and column 1 of W=A144225 are deleted, the remaining array is R. - Clark Kimberling, Sep 15 2008
If A007318 = M as an infinite lower triangular matrix, M^n gives A130595, A023531, A007318, A038207, A027465, A038231, A038243, A038255, A027466, A038279, A038291, A038303, A038315, A038327, A133371, A147716, A027467 for n=-1,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 11 2008
The coefficients of the polynomials with e.g.f. exp(x*t)*(cosh(t)+sinh(t)). - Peter Luschny, Jul 09 2009
The triangle or chess sums, see A180662 for their definitions, link Pascal's triangle with twenty different sequences, see the crossrefs. All sums come in pairs due to the symmetrical nature of this triangle. The knight sums Kn14 - Kn110 have been added. It is remarkable that all knight sums are related to the Fibonacci numbers, i.e., A000045, but none of the others. - Johannes W. Meijer, Sep 22 2010
Binomial(n,k) is also the number of ways to distribute n+1 balls into k+1 urns so that each urn gets at least one ball. See example in the example section below. - Dennis P. Walsh, Jan 29 2011
Binomial(n,k) is the number of increasing functions from {1,...,k} to {1,...,n} since there are binomial(n,k) ways to choose the k distinct, ordered elements of the range from the codomain {1,...,n}. See example in the example section below. - Dennis P. Walsh, Apr 07 2011
Central binomial coefficients: T(2*n,n) = A000984(n), T(n, floor(n/2)) = A001405(n). - Reinhard Zumkeller, Nov 09 2011
Binomial(n,k) is the number of subsets of {1,...,n+1} with k+1 as median element. To see this, note that Sum_{j=0..min(k,n-k)}binomial(k,j)*binomial(n-k,j) = binomial(n,k). See example in Example section below. - Dennis P. Walsh, Dec 15 2011
This is the coordinator triangle for the lattice Z^n, see Conway-Sloane, 1997. - N. J. A. Sloane, Jan 17 2012
One of three infinite families of integral factorial ratio sequences of height 1 (see Bober, Theorem 1.2). The other two are A046521 and A068555. For real r >= 0, C_r(n,k) := floor(r*n)!/(floor(r*k)!*floor(r*(n-k))!) is integral. See A211226 for the case r = 1/2. - Peter Bala, Apr 10 2012
Define a finite triangle T(m,k) with n rows such that T(m,0) = 1 is the left column, T(m,m) = binomial(n-1,m) is the right column, and the other entries are T(m,k) = T(m-1,k-1) + T(m-1,k) as in Pascal's triangle. The sum of all entries in T (there are A000217(n) elements) is 3^(n-1). - J. M. Bergot, Oct 01 2012
The lower triangular Pascal matrix serves as a representation of the operator exp(RLR) in a basis composed of a sequence of polynomials p_n(x) characterized by ladder operators defined by R p_n(x) = p_(n+1)(x) and L p_n(x) = n p_(n-1)(x). See A132440, A218272, A218234, A097805, and A038207. The transposed and padded Pascal matrices can be associated to the special linear group SL2. - Tom Copeland, Oct 25 2012
See A193242. - Alexander R. Povolotsky, Feb 05 2013
A permutation p_1...p_n of the set {1,...,n} has a descent at position i if p_i > p_(i+1). Let S(n) denote the subset of permutations p_1...p_n of {1,...,n} such that p_(i+1) - p_i <= 1 for i = 1,...,n-1. Then binomial(n,k) gives the number of permutations in S(n+1) with k descents. Alternatively, binomial(n,k) gives the number of permutations in S(n+1) with k+1 increasing runs. - Peter Bala, Mar 24 2013
Sum_{n=>0} binomial(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where binomial(n,k) = 0. Also Sum_{n>=0} binomial(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
The square n X n submatrix (first n rows and n columns) of the Pascal matrix P(x) defined in the formulas below when multiplying on the left the Vandermonde matrix V(x_1,...,x_n) (with ones in the first row) translates the matrix to V(x_1+x,...,x_n+x) while leaving the determinant invariant. - Tom Copeland, May 19 2014
For k>=2, n>=k, k/((k/(k-1) - Sum_{n=k..m} 1/binomial(n,k))) = m!/((m-k+1)!*(k-2)!). Note: k/(k-1) is the infinite sum. See A000217, A000292, A000332 for examples. - Richard R. Forberg, Aug 12 2014
Let G_(2n) be the subgroup of the symmetric group S_(2n) defined by G_(2n) = {p in S_(2n) | p(i) = i (mod n) for i = 1,2,...,2n}. G_(2n) has order 2^n. Binomial(n,k) gives the number of permutations in G_(2n) having n + k cycles. Cf. A130534 and A246117. - Peter Bala, Aug 15 2014
C(n,k) = the number of Dyck paths of semilength n+1, with k+1 "u"'s in odd numbered positions and k+1 returns to the x axis. Example: {U = u in odd position and = return to x axis} binomial(3,0)=1 (Uudududd); binomial(3,1)=3 [(Uududd_Ud_), (Ud_Uududd_), (Uudd_Uudd_)]; binomial(3,2)=3 [(Ud_Ud_Uudd_), (Uudd_Ud_Ud_), (Ud_Uudd_Ud_)]; binomial(3,3)=1 (Ud_Ud_Ud_Ud_). - Roger Ford, Nov 05 2014
From Daniel Forgues, Mar 12 2015: (Start)
The binomial coefficients binomial(n,k) give the number of individuals of the k-th generation after n population doublings. For each doubling of population, each individual's clone has its generation index incremented by 1, and thus goes to the next row. Just tally up each row from 0 to 2^n - 1 to get the binomial coefficients.
0 1 3 7 15
0: O | . | . . | . . . . | . . . . . . . . |
1: | O | O . | O . . . | O . . . . . . . |
2: | | O | O O . | O O . O . . . |
3: | | | O | O O O . |
4: | | | | O |
This is a fractal process: to get the pattern from 0 to 2^n - 1, append a shifted down (by one row) copy of the pattern from 0 to 2^(n-1) - 1 to the right of the pattern from 0 to 2^(n-1) - 1. (Inspired by the "binomial heap" data structure.)
Sequence of generation indices: 1's-counting sequence: number of 1's in binary expansion of n (or the binary weight of n) (see A000120):
{0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, ...}
Binary expansion of 0 to 15:
0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1111
(End)
A258993(n,k) = T(n+k,n-k), n > 0. - Reinhard Zumkeller, Jun 22 2015
T(n,k) is the number of set partitions w of [n+1] that avoid 1/2/3 with rb(w)=k. The same holds for ls(w)=k, where avoidance is in the sense of Klazar and ls,rb defined by Wachs and White.
Satisfies Benford's law [Diaconis, 1977] - N. J. A. Sloane, Feb 09 2017
Let {A(n)} be a set with exactly n identical elements, with {A(0)} being the empty set E. Let {A(n,k)} be the k-th iteration of {A(n)}, with {A(n,0)} = {A(n)}. {A(n,1)} = The set of all the subsets of A{(n)}, including {A(n)} and E. {A(n,k)} = The set of all subsets of {A(n,k-1)}, including all of the elements of {A(n,k-1)}. Let A(n,k) be the number of elements in {A(n,k)}. Then A(n,k) = C(n+k,k), with each successive iteration replicating the members of the k-th diagonal of Pascal's Triangle. See examples. - Gregory L. Simay, Aug 06 2018
Binomial(n-1,k) is also the number of permutations avoiding both 213 and 312 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n-1,k) is also the number of permutations avoiding both 132 and 213 with k ascents. - Lara Pudwell, Dec 19 2018
Binomial(n,k) is the dimension of the k-th exterior power of a vector space of dimension n. - Stefano Spezia, Dec 22 2018
C(n,k-1) is the number of unoriented colorings of the facets (or vertices) of an n-dimensional simplex using exactly k colors. Each chiral pair is counted as one when enumerating unoriented arrangements. - Robert A. Russell, Oct 20 2020
From Dilcher and Stolarsky: "Two of the most ubiquitous objects in mathematics are the sequence of prime numbers and the binomial coefficients (and thus Pascal's triangle). A connection between the two is given by a well-known characterization of the prime numbers: Consider the entries in the k-th row of Pascal's triangle, without the initial and final entries. They are all divisible by k if and only if k is a prime." - Tom Copeland, May 17 2021
Named "Table de M. Pascal pour les combinaisons" by Pierre Remond de Montmort (1708) after the French mathematician, physicist and philosopher Blaise Pascal (1623-1662). - Amiram Eldar, Jun 11 2021
Consider the n-th diagonal of the triangle as a sequence b(n) with n starting at 0. From it form a new sequence by leaving the 0th term as is, and thereafter considering all compositions of n, taking the product of b(i) over the respective numbers i in each composition, adding terms corresponding to compositions with an even number of parts subtracting terms corresponding to compositions with an odd number of parts. Then the n-th row of the triangle is obtained, with every second term multiplied by -1, followed by infinitely many zeros. For sequences starting with 1, this operation is a special case of a self-inverse operation, and therefore the converse is true. - Thomas Anton, Jul 05 2021
C(n,k) is the number of vertices in an n-dimensional unit hypercube, at an L1 distance of k (or: with a shortest path of k 1d-edges) from a given vertex. - Eitan Y. Levine, May 01 2023
C(n+k-1,k-1) is the number of vertices at an L1 distance from a given vertex in an infinite-dimensional box, which has k sides of length 2^m for each m >= 0. Equivalently, given a set of tokens containing k distinguishable tokens with value 2^m for each m >= 0, C(n+k-1,k-1) is the number of subsets of tokens with a total value of n. - Eitan Y. Levine, Jun 11 2023
Numbers in the k-th column, i.e., numbers of the form C(n,k) for n >= k, are known as k-simplex numbers. - Pontus von Brömssen, Jun 26 2023
Let r(k) be the k-th row and c(k) the k-th column. Denote convolution by * and repeated convolution by ^. Then r(k)*r(m)=r(k+m) and c(k)*c(m)=c(k+m+1). This is because r(k) = r(1) ^ k and c(k) = c(0) ^ k+1. - Eitan Y. Levine, Jul 23 2023
Number of permutations of length n avoiding simultaneously the patterns 231 and 312(resp., 213 and 231; 213 and 312) with k descents (equivalently, with k ascents). An ascent (resp., descent) in a permutation a(1)a(2)...a(n) is position i such that a(i)a(i+1)). - Tian Han, Nov 25 2023
C(n,k) are generalized binomial coefficients of order m=0. Calculated by the formula C(n,k) = Sum_{i=0..n-k} binomial(n+1, n-k-i)*Stirling2(i+ m+ 1, i+1) *(-1)^i, where m = 0 for n>= 0, 0 <= k <= n. - Igor Victorovich Statsenko, Feb 26 2023
The Akiyama-Tanigawa algorithm applied to the diagonals, binomial(n+k,k), yields the powers of n. - Shel Kaphan, May 03 2024

Examples

			Triangle T(n,k) begins:
   n\k 0   1   2   3   4   5   6   7   8   9  10  11 ...
   0   1
   1   1   1
   2   1   2   1
   3   1   3   3   1
   4   1   4   6   4   1
   5   1   5  10  10   5   1
   6   1   6  15  20  15   6   1
   7   1   7  21  35  35  21   7   1
   8   1   8  28  56  70  56  28   8   1
   9   1   9  36  84 126 126  84  36   9   1
  10   1  10  45 120 210 252 210 120  45  10   1
  11   1  11  55 165 330 462 462 330 165  55  11   1
  ...
There are C(4,2)=6 ways to distribute 5 balls BBBBB, among 3 different urns, < > ( ) [ ], so that each urn gets at least one ball, namely, <BBB>(B)[B], <B>(BBB)[B], <B>(B)[BBB], <BB>(BB)[B], <BB>(B)[BB], and <B>(BB)[BB].
There are C(4,2)=6 increasing functions from {1,2} to {1,2,3,4}, namely, {(1,1),(2,2)},{(1,1),(2,3)}, {(1,1),(2,4)}, {(1,2),(2,3)}, {(1,2),(2,4)}, and {(1,3),(2,4)}. - _Dennis P. Walsh_, Apr 07 2011
There are C(4,2)=6 subsets of {1,2,3,4,5} with median element 3, namely, {3}, {1,3,4}, {1,3,5}, {2,3,4}, {2,3,5}, and {1,2,3,4,5}. - _Dennis P. Walsh_, Dec 15 2011
The successive k-iterations of {A(0)} = E are E;E;E;...; the corresponding number of elements are 1,1,1,... The successive k-iterations of {A(1)} = {a} are (omitting brackets) a;a,E; a,E,E;...; the corresponding number of elements are 1,2,3,... The successive k-iterations of {A(2)} = {a,a} are aa; aa,a,E; aa, a, E and a,E and E;...; the corresponding number of elements are 1,3,6,... - _Gregory L. Simay_, Aug 06 2018
Boas-Buck type recurrence for column k = 4: T(8, 4) = (5/4)*(1 + 5 + 15 + 35) = 70. See the Boas-Buck comment above. - _Wolfdieter Lang_, Nov 12 2018

References

  • M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 828.
  • Amulya Kumar Bag, Binomial theorem in ancient India, Indian Journal of History of Science, vol. 1 (1966), pp. 68-74.
  • Arthur T. Benjamin and Jennifer Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 63ff.
  • Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids (in Russian), FAN, Tashkent, 1990, ISBN 5-648-00738-8.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 306.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 68-74.
  • Paul Curtz, Intégration numérique des systèmes différentiels à conditions initiales, Centre de Calcul Scientifique de l'Armement, Arcueil, 1969.
  • A. W. F. Edwards, Pascal's Arithmetical Triangle, 2002.
  • William Feller, An Introduction to Probability Theory and Its Application, Vol. 1, 2nd ed. New York: Wiley, p. 36, 1968.
  • Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 2nd. ed., 1994, p. 155.
  • Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.4 Powers and Roots, pp. 140-141.
  • David Hök, Parvisa mönster i permutationer [Swedish], 2007.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 1, 2nd ed., p. 52.
  • Sergei K. Lando, Lecture on Generating Functions, Amer. Math. Soc., Providence, R.I., 2003, pp. 60-61.
  • Blaise Pascal, Traité du triangle arithmétique, avec quelques autres petits traitez sur la mesme matière, Desprez, Paris, 1665.
  • Clifford A. Pickover, A Passion for Mathematics, Wiley, 2005; see p. 71.
  • Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, pages 271-275.
  • A. P. Prudnikov, Yu. A. Brychkov, and O. I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992.
  • John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 6.
  • John Riordan, Combinatorial Identities, Wiley, 1968, p. 2.
  • Robert Sedgewick and Philippe Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996, p. 143.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Jerome Spanier and Keith B. Oldham, "Atlas of Functions", Hemisphere Publishing Corp., 1987, chapter 6, pages 43-52.
  • James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, pages 13, 30-33.
  • David Wells, The Penguin Dictionary of Curious and Interesting Numbers, Penguin Books, 1987, pp. 115-118.
  • Douglas B. West, Combinatorial Mathematics, Cambridge, 2021, p. 25.

Links

Crossrefs

Equals differences between consecutive terms of A102363. - David G. Williams (davidwilliams(AT)Paxway.com), Jan 23 2006
Row sums give A000079 (powers of 2).
Cf. A083093 (triangle read mod 3), A214292 (first differences of rows).
Partial sums of rows give triangle A008949.
The triangle of the antidiagonals is A011973.
Infinite matrix squared: A038207, cubed: A027465.
Cf. A101164. If rows are sorted we get A061554 or A107430.
Another version: A108044.
Cf. A008277, A132311, A132312, A052216, A052217, A052218, A052219, A052220, A052221, A052222, A052223, A144225, A202750, A211226, A047999, A026729, A052553, A051920, A193242.
Triangle sums (see the comments): A000079 (Row1); A000007 (Row2); A000045 (Kn11 & Kn21); A000071 (Kn12 & Kn22); A001924 (Kn13 & Kn23); A014162 (Kn14 & Kn24); A014166 (Kn15 & Kn25); A053739 (Kn16 & Kn26); A053295 (Kn17 & Kn27); A053296 (Kn18 & Kn28); A053308 (Kn19 & Kn29); A053309 (Kn110 & Kn210); A001519 (Kn3 & Kn4); A011782 (Fi1 & Fi2); A000930 (Ca1 & Ca2); A052544 (Ca3 & Ca4); A003269 (Gi1 & Gi2); A055988 (Gi3 & Gi4); A034943 (Ze1 & Ze2); A005251 (Ze3 & Ze4). - Johannes W. Meijer, Sep 22 2010
Fibonacci-Pascal triangles: A027926, A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074, A228196, A228576.
Cf. A137948, A245334.
Cf. A085478, A258993.
Cf. A115940 (pandigital binomial coefficients C(m,k) with k>1).
Cf. (simplex colorings) A325002 (oriented), [k==n+1] (chiral), A325003 (achiral), A325000 (k or fewer colors), A325009 (orthotope facets, orthoplex vertices), A325017 (orthoplex facets, orthotope vertices).
Triangles of generalized binomial coefficients (n,k)_m (or generalized Pascal triangles) for m = 2..12: A001263, A056939, A056940, A056941, A142465, A142467, A142468, A174109, A342889, A342890, A342891.

Programs

  • Axiom
    -- (start)
)set expose add constructor OutputForm
pascal(0,n) == 1
pascal(n,n) == 1
pascal(i,j | 0 < i and i < j) == pascal(i-1,j-1) + pascal(i,j-1)
pascalRow(n) == [pascal(i,n) for i in 0..n]
displayRow(n) == output center blankSeparate pascalRow(n)
for i in 0..20 repeat displayRow i -- (end)
  • GAP
    Flat(List([0..12],n->List([0..n],k->Binomial(n,k)))); # Stefano Spezia, Dec 22 2018
  • Haskell
    a007318 n k = a007318_tabl !! n !! k
a007318_row n = a007318_tabl !! n
a007318_list = concat a007318_tabl
a007318_tabl = iterate (\row -> zipWith (+) ([0] ++ row) (row ++ [0])) [1]
-- Cf. http://www.haskell.org/haskellwiki/Blow_your_mind#Mathematical_sequences
-- Reinhard Zumkeller, Nov 09 2011, Oct 22 2010
  • Magma
    /* As triangle: */ [[Binomial(n, k): k in [0..n]]: n in [0.. 10]]; // Vincenzo Librandi, Jul 29 2015
  • Maple
    A007318 := (n,k)->binomial(n,k);
  • Mathematica
    Flatten[Table[Binomial[n, k], {n, 0, 11}, {k, 0, n}]] (* Robert G. Wilson v, Jan 19 2004 *)
Flatten[CoefficientList[CoefficientList[Series[1/(1 - x - x*y), {x, 0, 12}], x], y]] (* Mats Granvik, Jul 08 2014 *)
  • Maxima
    create_list(binomial(n,k),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */
  • PARI
    C(n,k)=binomial(n,k) \\ Charles R Greathouse IV, Jun 08 2011
  • Python
    # See Hobson link. Further programs:
from math import prod,factorial
def C(n,k): return prod(range(n,n-k,-1))//factorial(k) # M. F. Hasler, Dec 13 2019, updated Apr 29 2022, Feb 17 2023
  • Python
    from math import comb, isqrt
def A007318(n): return comb(r:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)),n-comb(r+1,2)) # Chai Wah Wu, Nov 11 2024
  • Sage
    def C(n,k): return Subsets(range(n), k).cardinality() # Ralf Stephan, Jan 21 2014

Formula

a(n, k) = C(n,k) = binomial(n, k).
C(n, k) = C(n-1, k) + C(n-1, k-1).
The triangle is symmetric: C(n,k) = C(n,n-k).
a(n+1, m) = a(n, m) + a(n, m-1), a(n, -1) := 0, a(n, m) := 0, n
C(n, k) = n!/(k!(n-k)!) if 0<=k<=n, otherwise 0.
C(n, k) = ((n-k+1)/k) * C(n, k-1) with C(n, 0) = 1. - Michael B. Porter, Mar 23 2025
G.f.: 1/(1-y-x*y) = Sum_(C(n, k)*x^k*y^n, n, k>=0)
G.f.: 1/(1-x-y) = Sum_(C(n+k, k)*x^k*y^n, n, k>=0).
G.f. for row n: (1+x)^n = Sum_{k=0..n} C(n, k)*x^k.
G.f. for column k: x^k/(1-x)^(k+1); [corrected by Werner Schulte, Jun 15 2022].
E.g.f.: A(x, y) = exp(x+x*y).
E.g.f. for column n: x^n*exp(x)/n!.
In general the m-th power of A007318 is given by: T(0, 0) = 1, T(n, k) = T(n-1, k-1) + m*T(n-1, k), where n is the row-index and k is the column; also T(n, k) = m^(n-k)*C(n, k).
Triangle T(n, k) read by rows; given by A000007 DELTA A000007, where DELTA is Deléham's operator defined in A084938.
Let P(n+1) = the number of integer partitions of (n+1); let p(i) = the number of parts of the i-th partition of (n+1); let d(i) = the number of different parts of the i-th partition of (n+1); let m(i, j) = multiplicity of the j-th part of the i-th partition of (n+1). Define the operator Sum_{i=1..P(n+1), p(i)=k+1} as the sum running from i=1 to i=P(n+1) but taking only partitions with p(i)=(k+1) parts into account. Define the operator Product_{j=1..d(i)} = product running from j=1 to j=d(i). Then C(n, k) = Sum_{p(i)=(k+1), i=1..P(n+1)} p(i)! / [Product_{j=1..d(i)} m(i, j)!]. E.g., C(5, 3) = 10 because n=6 has the following partitions with m=3 parts: (114), (123), (222). For their multiplicities one has: (114): 3!/(2!*1!) = 3; (123): 3!/(1!*1!*1!) = 6; (222): 3!/3! = 1. The sum is 3 + 6 + 1 = 10 = C(5, 3). - Thomas Wieder, Jun 03 2005
C(n, k) = Sum_{j=0..k} (-1)^j*C(n+1+j, k-j)*A000108(j). - Philippe Deléham, Oct 10 2005
G.f.: 1 + x*(1 + x) + x^3*(1 + x)^2 + x^6*(1 + x)^3 + ... . - Michael Somos, Sep 16 2006
Sum_{k=0..floor(n/2)} x^(n-k)*T(n-k,k) = A000007(n), A000045(n+1), A002605(n), A030195(n+1), A057087(n), A057088(n), A057089(n), A057090(n), A057091(n), A057092(n), A057093(n) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, respectively. Sum_{k=0..floor(n/2)} (-1)^k*x^(n-k)*T(n-k,k) = A000007(n), A010892(n), A009545(n+1), A057083(n), A001787(n+1), A030191(n), A030192(n), A030240(n), A057084(n), A057085(n+1), A057086(n), A084329(n+1) for x = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, respectively. - Philippe Deléham, Sep 16 2006
C(n,k) <= A062758(n) for n > 1. - Reinhard Zumkeller, Mar 04 2008
C(t+p-1, t) = Sum_{i=0..t} C(i+p-2, i) = Sum_{i=1..p} C(i+t-2, t-1). A binomial number is the sum of its left parent and all its right ancestors, which equals the sum of its right parent and all its left ancestors. - Lee Naish (lee(AT)cs.mu.oz.au), Mar 07 2008
From Paul D. Hanna, Mar 24 2011: (Start)
Let A(x) = Sum_{n>=0} x^(n*(n+1)/2)*(1+x)^n be the g.f. of the flattened triangle:
A(x) = 1 + (x + x^2) + (x^3 + 2*x^4 + x^5) + (x^6 + 3*x^7 + 3*x^8 + x^9) + ...
then A(x) equals the series Sum_{n>=0} (1+x)^n*x^n*Product_{k=1..n} (1-(1+x)*x^(2*k-1))/(1-(1+x)*x^(2*k));
also, A(x) equals the continued fraction 1/(1- x*(1+x)/(1+ x*(1-x)*(1+x)/(1- x^3*(1+x)/(1+ x^2*(1-x^2)*(1+x)/(1- x^5*(1+x)/(1+ x^3*(1-x^3)*(1+x)/(1- x^7*(1+x)/(1+ x^4*(1-x^4)*(1+x)/(1- ...))))))))).
These formulas are due to (1) a q-series identity and (2) a partial elliptic theta function expression. (End)
For n > 0: T(n,k) = A029600(n,k) - A029635(n,k), 0 <= k <= n. - Reinhard Zumkeller, Apr 16 2012
Row n of the triangle is the result of applying the ConvOffs transform to the first n terms of the natural numbers (1, 2, 3, ..., n). See A001263 or A214281 for a definition of this transformation. - Gary W. Adamson, Jul 12 2012
From L. Edson Jeffery, Aug 02 2012: (Start)
Row n (n >= 0) of the triangle is given by the n-th antidiagonal of the infinite matrix P^n, where P = (p_{i,j}), i,j >= 0, is the production matrix
0, 1,
1, 0, 1,
0, 1, 0, 1,
0, 0, 1, 0, 1,
0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 1, 0, 1,
0, 0, 0, 0, 0, 0, 1, 0, 1,
... (End)
Row n of the triangle is also given by the n+1 coefficients of the polynomial P_n(x) defined by the recurrence P_0(x) = 1, P_1(x) = x + 1, P_n(x) = x*P_{n-1}(x) + P_{n-2}(x), n > 1. - L. Edson Jeffery, Aug 12 2013
For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013
(1+x)^n = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*Sum_{i=0..k} k^(n-i)*binomial(k,i)*x^(n-i)/(n-i)!. - Vladimir Kruchinin, Oct 21 2013
E.g.f.: A(x,y) = exp(x+x*y) = 1 + (x+y*x)/( E(0)-(x+y*x)), where E(k) = 1 + (x+y*x)/(1 + (k+1)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013
E.g.f.: E(0) -1, where E(k) = 2 + x*(1+y)/(2*k+1 - x*(1+y)/E(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
G.f.: 1 + x*(1+x)*(1+x^2*(1+x)/(W(0)-x^2-x^3)), where W(k) = 1 + (1+x)*x^(k+2) - (1+x)*x^(k+3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
Sum_{n>=0} C(n,k)/n! = e/k!, where e = exp(1), while allowing n < k where C(n,k) = 0. Also Sum_{n>=0} C(n+k-1,k)/n! = e * A000262(k)/k!, and for k>=1 equals e * A067764(k)/A067653(k). - Richard R. Forberg, Jan 01 2014
Sum_{n>=k} 1/C(n,k) = k/(k-1) for k>=1. - Richard R. Forberg, Feb 10 2014
From Tom Copeland, Apr 26 2014: (Start)
Multiply each n-th diagonal of the Pascal lower triangular matrix by x^n and designate the result by A007318(x) = P(x). Then with :xD:^n = x^n*(d/dx)^n and B(n,x), the Bell polynomials (A008277),
A) P(x)= exp(x*dP) = exp[x*(e^M-I)] = exp[M*B(.,x)] = (I+dP)^B(.,x)
with dP = A132440, M = A238385-I, and I = identity matrix, and
B) P(:xD:) = exp(dP:xD:) = exp[(e^M-I):xD:] = exp[M*B(.,:xD:)] = exp[M*xD] = (I+dP)^(xD) with action P(:xD:)g(x) = exp(dP:xD:)g(x) = g[(I+dP)*x] (cf. also A238363).
C) P(x)^y = P(y*x). P(2x) = A038207(x) = exp[M*B(.,2x)], the face vectors of the n-dim hypercubes.
D) P(x) = [St2]*exp(x*M)*[St1] = [St2]*(I+dP)^x*[St1]
E) = [St1]^(-1)*(I+dP)^x*[St1] = [St2]*(I+dP)^x*[St2]^(-1)
where [St1]=padded A008275 just as [St2]=A048993=padded A008277 and exp(x*M) = (I+dP)^x = Sum_{k>=0} C(x,k) dP^k. (End)
T(n,k) = A245334(n,k) / A137948(n,k), 0 <= k <= n. - Reinhard Zumkeller, Aug 31 2014
From Peter Bala, Dec 21 2014: (Start)
Recurrence equation: T(n,k) = T(n-1,k)*(n + k)/(n - k) - T(n-1,k-1) for n >= 2 and 1 <= k < n, with boundary conditions T(n,0) = T(n,n) = 1. Note, changing the minus sign in the recurrence to a plus sign gives a recurrence for the square of the binomial coefficients - see A008459.
There is a relation between the e.g.f.'s of the rows and the diagonals of the triangle, namely, exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(1 + 3*x + 3*x^2/2! + x^3/3!) = 1 + 4*x + 10*x^2/2! + 20*x^3/3! + 35*x^4/4! + .... This property holds more generally for the Riordan arrays of the form ( f(x), x/(1 - x) ), where f(x) is an o.g.f. of the form 1 + f_1*x + f_2*x^2 + .... See, for example, A055248 and A106516.
Let P denote the present triangle. For k = 0,1,2,... define P(k) to be the lower unit triangular block array
/I_k 0\
\ 0 P/ having the k X k identity matrix I_k as the upper left block; in particular, P(0) = P. The infinite product P(0)*P(1)*P(2)*..., which is clearly well-defined, is equal to the triangle of Stirling numbers of the second kind A008277. The infinite product in the reverse order, that is, ...*P(2)*P(1)*P(0), is equal to the triangle of Stirling cycle numbers A130534. (End)
C(a+b,c) = Sum_{k=0..a} C(a,k)*C(b,b-c+k). This is a generalization of equation 1 from section 4.2.5 of the Prudnikov et al. reference, for a=b=c=n: C(2*n,n) = Sum_{k=0..n} C(n,k)^2. See Links section for animation of new formula. - Hermann Stamm-Wilbrandt, Aug 26 2015
The row polynomials of the Pascal matrix P(n,x) = (1+x)^n are related to the Bernoulli polynomials Br(n,x) and their umbral compositional inverses Bv(n,x) by the umbral relation P(n,x) = (-Br(.,-Bv(.,x)))^n = (-1)^n Br(n,-Bv(.,x)), which translates into the matrix relation P = M * Br * M * Bv, where P is the Pascal matrix, M is the diagonal matrix diag(1,-1,1,-1,...), Br is the matrix for the coefficients of the Bernoulli polynomials, and Bv that for the umbral inverse polynomials defined umbrally by Br(n,Bv(.,x)) = x^n = Bv(n,Br(.,x)). Note M = M^(-1). - Tom Copeland, Sep 05 2015
1/(1-x)^k = (r(x) * r(x^2) * r(x^4) * ...) where r(x) = (1+x)^k. - Gary W. Adamson, Oct 17 2016
Boas-Buck type recurrence for column k for Riordan arrays (see the Aug 10 2017 remark in A046521, also for the reference) with the Boas-Buck sequence b(n) = {repeat(1)}. T(n, k) = ((k+1)/(n-k))*Sum_{j=k..n-1} T(j, k), for n >= 1, with T(n, n) = 1. This reduces, with T(n, k) = binomial(n, k), to a known binomial identity (e.g, Graham et al. p. 161). - Wolfdieter Lang, Nov 12 2018
C((p-1)/a, b) == (-1)^b * fact_a(a*b-a+1)/fact_a(a*b) (mod p), where fact_n denotes the n-th multifactorial, a divides p-1, and the denominator of the fraction on the right side of the equation represents the modular inverse. - Isaac Saffold, Jan 07 2019
C(n,k-1) = A325002(n,k) - [k==n+1] = (A325002(n,k) + A325003(n,k)) / 2 = [k==n+1] + A325003(n,k). - Robert A. Russell, Oct 20 2020
From Hermann Stamm-Wilbrandt, May 13 2021: (Start)
Binomial sums are Fibonacci numbers A000045:
Sum_{k=0..n} C(n + k, 2*k + 1) = F(2*n).
Sum_{k=0..n} C(n + k, 2*k) = F(2*n + 1). (End)
C(n,k) = Sum_{i=0..k} A000108(i) * C(n-2i-1, k-i), for 0 <= k <= floor(n/2)-1. - Tushar Bansal, May 17 2025

Extensions

Checked all links, deleted 8 that seemed lost forever and were probably not of great importance. - N. J. A. Sloane, May 08 2018

A000124 Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pancake with n cuts.

Original entry on oeis.org

1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, 704, 742, 781, 821, 862, 904, 947, 991, 1036, 1082, 1129, 1177, 1226, 1276, 1327, 1379
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

These are Hogben's central polygonal numbers with the (two-dimensional) symbol
2
.P
1 n
The first line cuts the pancake into 2 pieces. For n > 1, the n-th line crosses every earlier line (avoids parallelism) and also avoids every previous line intersection, thus increasing the number of pieces by n. For 16 lines, for example, the number of pieces is 2 + 2 + 3 + 4 + 5 + ... + 16 = 137. These are the triangular numbers plus 1 (cf. A000217).
m = (n-1)(n-2)/2 + 1 is also the smallest number of edges such that all graphs with n nodes and m edges are connected. - Keith Briggs, May 14 2004
Also maximal number of grandchildren of a binary vector of length n+2. E.g., a binary vector of length 6 can produce at most 11 different vectors when 2 bits are deleted.
This is also the order dimension of the (strong) Bruhat order on the finite Coxeter group B_{n+1}. - Nathan Reading (reading(AT)math.umn.edu), Mar 07 2002
Number of 132- and 321-avoiding permutations of {1,2,...,n+1}. - Emeric Deutsch, Mar 14 2002
For n >= 1 a(n) is the number of terms in the expansion of (x+y)*(x^2+y^2)*(x^3+y^3)*...*(x^n+y^n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 28 2003
Also the number of terms in (1)(x+1)(x^2+x+1)...(x^n+...+x+1); see A000140.
Narayana transform (analog of the binomial transform) of vector [1, 1, 0, 0, 0, ...] = A000124; using the infinite lower Narayana triangle of A001263 (as a matrix), N; then N * [1, 1, 0, 0, 0, ...] = A000124. - Gary W. Adamson, Apr 28 2005
Number of interval subsets of {1, 2, 3, ..., n} (cf. A002662). - Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006
Define a number of straight lines in the plane to be in general arrangement when (1) no two lines are parallel, (2) there is no point common to three lines. Then these are the maximal numbers of regions defined by n straight lines in general arrangement in the plane. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Note that a(n) = a(n-1) + A000027(n-1). This has the following geometrical interpretation: Suppose there are already n-1 lines in general arrangement, thus defining the maximal number of regions in the plane obtainable by n-1 lines and now one more line is added in general arrangement. Then it will cut each of the n-1 lines and acquire intersection points which are in general arrangement. (See the comments on A000027 for general arrangement with points.) These points on the new line define the maximal number of regions in 1-space definable by n-1 points, hence this is A000027(n-1), where for A000027 an offset of 0 is assumed, that is, A000027(n-1) = (n+1)-1 = n. Each of these regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n-1) regions already there, hence a(n) = a(n-1) + A000027(n-1). Cf. the comments on A000125 for an analogous interpretation. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
When constructing a zonohedron, one zone at a time, out of (up to) 3-d non-intersecting parallelepipeds, the n-th element of this sequence is the number of edges in the n-th zone added with the n-th "layer" of parallelepipeds. (Verified up to 10-zone zonohedron, the enneacontahedron.) E.g., adding the 10th zone to the enneacontahedron requires 46 parallel edges (edges in the 10th zone) by looking directly at a 5-valence vertex and counting visible vertices. - Shel Kaphan, Feb 16 2006
Binomial transform of (1, 1, 1, 0, 0, 0, ...) and inverse binomial transform of A072863: (1, 3, 9, 26, 72, 192, ...). - Gary W. Adamson, Oct 15 2007
If Y is a 2-subset of an n-set X then, for n >= 3, a(n-3) is the number of (n-2)-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007
Equals row sums of triangle A144328. - Gary W. Adamson, Sep 18 2008
It appears that a(n) is the number of distinct values among the fractions F(i+1)/F(j+1) as j ranges from 1 to n and, for each fixed j, i ranges from 1 to j, where F(i) denotes the i-th Fibonacci number. - John W. Layman, Dec 02 2008
a(n) is the number of subsets of {1,2,...,n} that contain at most two elements. - Geoffrey Critzer, Mar 10 2009
For n >= 2, a(n) gives the number of sets of subsets A_1, A_2, ..., A_n of n = {1, 2, ..., n} such that Meet_{i = 1..n} A_i is empty and Sum_{j in [n]} (|Meet{i = 1..n, i != j} A_i|) is a maximum. - Srikanth K S, Oct 22 2009
The numbers along the left edge of Floyd's triangle. - Paul Muljadi, Jan 25 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = A[i,i]:=1, A[i,i-1] = -1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = (-1)^(n-1)*coeff(charpoly(A,x),x). - Milan Janjic, Jan 24 2010
Also the number of deck entries of Euler's ship. See the Meijer-Nepveu link. - Johannes W. Meijer, Jun 21 2010
(1 + x^2 + x^3 + x^4 + x^5 + ...)*(1 + 2x + 3x^2 + 4x^3 + 5x^4 + ...) = (1 + 2x + 4x^2 + 7x^3 + 11x^4 + ...). - Gary W. Adamson, Jul 27 2010
The number of length n binary words that have no 0-digits between any pair of consecutive 1-digits. - Jeffrey Liese, Dec 23 2010
Let b(0) = b(1) = 1; b(n) = max(b(n-1)+n-1, b(n-2)+n-2) then a(n) = b(n+1). - Yalcin Aktar, Jul 28 2011
Also number of triangular numbers so far, for n > 0: a(n) = a(n-1) + Sum(A010054(a(k)): 0 <= k < n), see also A097602, A131073. - Reinhard Zumkeller, Nov 15 2012
Also number of distinct sums of 1 through n where each of those can be + or -. E.g., {1+2,1-2,-1+2,-1-2} = {3,-1,1,-3} and a(2) = 4. - Toby Gottfried, Nov 17 2011
This sequence is complete because the sum of the first n terms is always greater than or equal to a(n+1)-1. Consequently, any nonnegative number can be written as a sum of distinct terms of this sequence. See A204009, A072638. - Frank M Jackson, Jan 09 2012
The sequence is the number of distinct sums of subsets of the nonnegative integers, and its first differences are the positive integers. See A208531 for similar results for the squares. - John W. Layman, Feb 28 2012
Apparently the number of Dyck paths of semilength n+1 in which the sum of the first and second ascents add to n+1. - David Scambler, Apr 22 2013
Without 1 and 2, a(n) equals the terminus of the n-th partial sum of sequence 1, 1, 2. Explanation: 1st partial sums of 1, 1, 2 are 1, 2, 4; 2nd partial sums are 1, 3, 7; 3rd partial sums are 1, 4, 11; 4th partial sums are 1, 5, 16, etc. - Bob Selcoe, Jul 04 2013
Equivalently, numbers of the form 2*m^2+m+1, where m = 0, -1, 1, -2, 2, -3, 3, ... . - Bruno Berselli, Apr 08 2014
For n >= 2: quasi-triangular numbers; the almost-triangular numbers being A000096(n), n >= 2. Note that 2 is simultaneously almost-triangular and quasi-triangular. - Daniel Forgues, Apr 21 2015
n points in general position determine "n choose 2" lines, so A055503(n) <= a(n(n-1)/2). If n > 3, the lines are not in general position and so A055503(n) < a(n(n-1)/2). - Jonathan Sondow, Dec 01 2015
The digital root is period 9 (1, 2, 4, 7, 2, 7, 4, 2, 1), also the digital roots of centered 10-gonal numbers (A062786), for n > 0, A133292. - Peter M. Chema, Sep 15 2016
Partial sums of A028310. - J. Conrad, Oct 31 2016
For n >= 0, a(n) is the number of weakly unimodal sequences of length n over the alphabet {1, 2}. - Armend Shabani, Mar 10 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) != e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) and e(i) < e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) != e(k). [Martinez and Savage, 2.4]
(End)
Numbers m such that 8m - 7 is a square. - Bruce J. Nicholson, Jul 24 2017
From Klaus Purath, Jan 29 2020: (Start)
The odd prime factors != 7 occur in an interval of p successive terms either never or exactly twice, while 7 always occurs only once. If a prime factor p appears in a(n) and a(m) within such an interval, then n + m == -1 (mod p). When 7 divides a(n), then 2*n == -1 (mod 7). a(n) is never divisible by the prime numbers given in A003625.
While all prime factors p != 7 can occur to any power, a(n) is never divisible by 7^2. The prime factors are given in A045373. The prime terms of this sequence are given in A055469.
(End)
From Roger Ford, May 10 2021: (Start)
a(n-1) is the greatest sum of arch lengths for the top arches of a semi-meander with n arches. An arch length is the number of arches covered + 1.
/\ The top arch has a length of 3. /\ The top arch has a length of 3.
/ \ Both bottom arches have a //\\ The middle arch has a length of 2.
//\/\\ length of 1. ///\\\ The bottom arch has a length of 1.
Example: for n = 4, a(4-1) = a(3) = 7 /\
//\\
/\ ///\\\ 1 + 3 + 2 + 1 = 7. (End)
a(n+1) is the a(n)-th smallest positive integer that has not yet appeared in the sequence. - Matthew Malone, Aug 26 2021
For n> 0, let the n-dimensional cube {0,1}^n be, provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 2. Example: n = 4. (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (0,0,1,1), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,0,0) are at distance <= 2 from (0,0,0,0), so a(4) = 11. - Yosu Yurramendi, Dec 10 2021
a(n) is the sum of the first three entries of row n of Pascal's triangle. - Daniel T. Martin, Apr 13 2022
a(n-1) is the number of Grassmannian permutations that avoid a pattern, sigma, where sigma is a pattern of size 3 with exactly one descent. For example, sigma is one of the patterns, {132, 213, 231, 312}. - Jessica A. Tomasko, Sep 14 2022
a(n+4) is the number of ways to tile an equilateral triangle of side length 2*n with smaller equilateral triangles of side length n and side length 1. For example, with n=2, there are 22 ways to tile an equilateral triangle of side length 4 with smaller ones of sides 2 and 1, including the one tiling with sixteen triangles of sides 1 and the one tiling with four triangles of sides 2. - Ahmed ElKhatib and Greg Dresden, Aug 19 2024
Define a "hatpin" to be the planar graph consisting of a distinguished point (called the "head") and a semi-infinite line from that point. The maximum number of regions than can be formed by drawing n hatpins is a(n-1). See link for the case n = 4. - N. J. A. Sloane, Jun 25 2025

Examples

			a(3) = 7 because the 132- and 321-avoiding permutations of {1, 2, 3, 4} are 1234, 2134, 3124, 2314, 4123, 3412, 2341.
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 11*x^4 + 16*x^5 + 22*x^6 + 29*x^7 + ...

References

  • Robert B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 24.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
  • John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See p. 80.
  • Henry Ernest Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
  • Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83.
  • Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
  • Alain M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
  • 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. 98.
  • William Allen Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
  • Akiva M. Yaglom and Isaak M. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #44 (First published: San Francisco: Holden-Day, Inc., 1964).

Links

Crossrefs

Cf. A000096 (Maximal number of pieces that can be obtained by cutting an annulus with n cuts, for n >= 1).
Slicing a cake: A000125, a bagel: A003600.
Partial sums =(A033547)/2, (A014206)/2.
The first 20 terms are also found in A025732 and A025739.
Cf. A002061, A002522, A016028, A055503, A072863, A144328, A177862, A263883, A000127, A005408, A006261, A016813, A058331, A080856, A086514, A161701, A161702, A161703, A161704, A161706, A161707, A161708, A161710, A161711, A161712, A161713, A161715, A051601, A228918.
Cf. also A055469 Quasi-triangular primes, A002620, A000217.
A row of the array in A386478.

Programs

Formula

G.f.: (1 - x + x^2)/(1 - x)^3. - Simon Plouffe in his 1992 dissertation
a(n) = A108561(n+3, 2). - Reinhard Zumkeller, Jun 10 2005
G.f.: (1 - x^6)/((1 - x)^2*(1 - x^2)*(1 - x^3)). a(n) = a(-1 - n) for all n in Z. - Michael Somos, Sep 04 2006
Euler transform of length 6 sequence [ 2, 1, 1, 0, 0, -1]. - Michael Somos, Sep 04 2006
a(n+3) = 3*a(n+2) - 3*a(n+1) + a(n) and a(1) = 1, a(2) = 2, a(3) = 4. - Artur Jasinski, Oct 21 2008
a(n) = A000217(n) + 1.
a(n) = a(n-1) + n. E.g.f.:(1 + x + x^2/2)*exp(x). - Geoffrey Critzer, Mar 10 2009
a(n) = Sum_{k = 0..n + 1} binomial(n+1, 2(k - n)). - Paul Barry, Aug 29 2004
a(n) = binomial(n+2, 1) - 2*binomial(n+1, 1) + binomial(n+2, 2). - Zerinvary Lajos, May 12 2006
From Thomas Wieder, Feb 25 2009: (Start)
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 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. (End)
a(n) = A034856(n+1) - A005843(n) = A000217(n) + A005408(n) - A005843(n). - Jaroslav Krizek, Sep 05 2009
a(n) = 2*a(n-1) - a(n-2) + 1. - Eric Werley, Jun 27 2011
E.g.f.: exp(x)*(1+x+(x^2)/2) = Q(0); Q(k) = 1+x/(1-x/(2+x-4/(2+x*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
a(n) = A014132(n, 1) for n > 0. - Reinhard Zumkeller, Dec 12 2012
a(n) = 1 + floor(n/2) + ceiling(n^2/2) = 1 + A004526(n) + A000982(n). - Wesley Ivan Hurt, Jun 14 2013
a(n) = A228074(n+1, n). - Reinhard Zumkeller, Aug 15 2013
For n > 0: A228446(a(n)) = 3. - Reinhard Zumkeller, Mar 12 2014
a(n) >= A263883(n) and a(n(n-1)/2) >= A055503(n). - Jonathan Sondow, Dec 01 2015
From Ilya Gutkovskiy, Jun 29 2016: (Start)
Dirichlet g.f.: (zeta(s-2) + zeta(s-1) + 2*zeta(s))/2.
Sum_{n >= 0} 1/a(n) = 2*Pi*tanh(sqrt(7)*Pi/2)/sqrt(7) = A226985. (End)
a(n) = (n+1)^2 - A000096(n). - Anton Zakharov, Jun 29 2016
a(n) = A101321(1, n). - R. J. Mathar, Jul 28 2016
a(n) = 2*a(n-1) - binomial(n-1, 2) and a(0) = 1. - Armend Shabani, Mar 10 2017
a(n) = A002620(n+2) + A002620(n-1). - Anton Zakharov, May 11 2017
From Klaus Purath, Jan 29 2020: (Start)
a(n) = (Sum_{i=n-2..n+2} A000217(i))/5.
a(n) = (Sum_{i=n-2..n+2} A002378(i))/10.
a(n) = (Sum_{i=n..n+2} A002061(i)+1)/6.
a(n) = (Sum_{i=n-1..n+2} A000290(i)+2)/8.
a(n) = A060533(n-1) + 10, n > 5.
a(n) = (A002378(n) + 2)/2.
a(n) = A152948(n+2) - 1.
a(n) = A152950(n+1) - 2.
a(n) = (A002061(n) + A002061(n+2))/4.
(End)
Sum_{n>=0} (-1)^n/a(n) = A228918. - Amiram Eldar, Nov 20 2020
From Amiram Eldar, Feb 17 2021: (Start)
Product_{n>=0} (1 + 1/a(n)) = cosh(sqrt(15)*Pi/2)*sech(sqrt(7)*Pi/2).
Product_{n>=1} (1 - 1/a(n)) = 2*Pi*sech(sqrt(7)*Pi/2). (End)
a((n^2-3n+6)/2) + a((n^2-n+4)/2) = a(n^2-2n+6)/2. - Charlie Marion, Feb 14 2023

A000071 a(n) = Fibonacci(n) - 1.

Original entry on oeis.org

0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of allowable transition rules for passing from one change to the next (on n-1 bells) in the English art of bell-ringing. This is also the number of involutions in the symmetric group S_{n-1} which can be represented as a product of transpositions of consecutive numbers from {1, 2, ..., n-1}. Thus for n = 6 we have a(6) from (12), (12)(34), (12)(45), (23), (23)(45), (34), (45), for instance. See my 1983 Math. Proc. Camb. Phil. Soc. paper. - Arthur T. White, letter to N. J. A. Sloane, Dec 18 1986
Number of permutations p of {1, 2, ..., n-1} such that max|p(i) - i| = 1. Example: a(4) = 2 since only the permutations 132 and 213 of {1, 2, 3} satisfy the given condition. - Emeric Deutsch, Jun 04 2003 [For a(5) = 4 we have 2143, 1324, 2134 and 1243. - Jon Perry, Sep 14 2013]
Number of 001-avoiding binary words of length n-3. a(n) is the number of partitions of {1, ..., n-1} into two blocks in which only 1- or 2-strings of consecutive integers can appear in a block and there is at least one 2-string. E.g., a(6) = 7 because the enumerated partitions of {1, 2, 3, 4, 5} are 124/35, 134/25, 14/235, 13/245, 1245/3, 145/23, 125/34. - Augustine O. Munagi, Apr 11 2005
Numbers for which only one Fibonacci bit-representation is possible and for which the maximal and minimal Fibonacci bit-representations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8 + 3 + 1 = 12. - Casey Mongoven, Mar 19 2006
Beginning with a(2), the "Recamán transform" (see A005132) of the Fibonacci numbers (A000045). - Nick Hobson, Mar 01 2007
Starting with nonzero terms, a(n) gives the row sums of triangle A158950. - Gary W. Adamson, Mar 31 2009
a(n+2) is the minimum number of elements in an AVL tree of height n. - Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010
a(n) is the number of branch nodes in the Fibonacci tree of order n-1. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417). - Emeric Deutsch, Jun 14 2010
a(n+3) is the number of distinct three-strand positive braids of length n (cf. Burckel). - Maxime Bourrigan, Apr 04 2011
a(n+1) is the number of compositions of n with maximal part 2. - Joerg Arndt, May 21 2013
a(n+2) is the number of leafs of great-grandparent DAG (directed acyclic graph) of height n. A great-grandparent DAG of height n is a single node for n = 1; for n > 1 each leaf of ggpDAG(n-1) has two child nodes where pairs of adjacent new nodes are merged into single node if and only if they have disjoint grandparents and same great-grandparent. Consequence: a(n) = 2*a(n-1) - a(n-3). - Hermann Stamm-Wilbrandt, Jul 06 2014
2 and 7 are the only prime numbers in this sequence. - Emmanuel Vantieghem, Oct 01 2014
From Russell Jay Hendel, Mar 15 2015: (Start)
We can establish Gerald McGarvey's conjecture mentioned in the Formula section, however we require n > 4. We need the following 4 prerequisites.
(1) a(n) = F(n) - 1, with {F(n)}A000045.%20(2)%20(Binet%20form)%20F(n)%20=%20(d%5En%20-%20e%5En)/sqrt(5)%20with%20d%20=%20phi%20and%20e%20=%201%20-%20phi,%20de%20=%20-1%20and%20d%20+%20e%20=%201.%20It%20follows%20that%20a(n)%20=%20(d(n)%20-%20e(n))/sqrt(5)%20-%201.%20(3)%20To%20prove%20floor(x)%20=%20y%20is%20equivalent%20to%20proving%20that%20x%20-%20y%20lies%20in%20the%20half-open%20interval%20%5B0,%201).%20(4)%20The%20series%20%7Bs(n)%20=%20c1%20x%5En%20+%20c2%7D">{n >= 1} the Fibonacci numbers A000045. (2) (Binet form) F(n) = (d^n - e^n)/sqrt(5) with d = phi and e = 1 - phi, de = -1 and d + e = 1. It follows that a(n) = (d(n) - e(n))/sqrt(5) - 1. (3) To prove floor(x) = y is equivalent to proving that x - y lies in the half-open interval [0, 1). (4) The series {s(n) = c1 x^n + c2}{n >= 1}, with -1 < x < 0, and c1 and c2 positive constants, converges by oscillation with s(1) < s(3) < s(5) < ... < s(6) < s(4) < s(2). If follows that for any odd n, the open interval (s(n), s(n+1)) contains the subsequence {s(t)}_{t >= n + 2}. Using these prerequisites we can analyze the conjecture.
Using prerequisites (2) and (3) we see we must prove, for all n > 4, that d((d^(n-1) - e^(n-1))/sqrt(5) - 1) - (d^n - e^n)/sqrt(5) + 1 + c lies in the interval [0, 1). But de = -1, implying de^(n-1) = -e^(n-2). It follows that we must equivalently prove (for all n > 4) that E(n, c) = (e^(n-2) + e^n)/sqrt(5) + 1 - d + c = e^(n-2) (e^2 + 1)/sqrt(5) + e + c lies in [0, 1). Clearly, for any particular n, E(n, c) has extrema (maxima, minima) when c = 2*(1-d) and c = (1+d)*(1-d). Therefore, the proof is completed by using prerequisite (4). It suffices to verify E(5, 2*(1-d)) = 0, E(6, 2*(1-d)) = 0.236068, E(5, (1-d)*(1+d)) = 0.618034, E(6, (1-d)*(1+d)) = 0.854102, all lie in [0, 1).
(End)
a(n) can be shown to be the number of distinct nonempty matchings on a path with n vertices. (A matching is a collection of disjoint edges.) - Andrew Penland, Feb 14 2017
Also, for n > 3, the lexicographically earliest sequence of positive integers such that {phi*a(n)} is located strictly between {phi*a(n-1)} and {phi*a(n-2)}. - Ivan Neretin, Mar 23 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) <= e(k). [Martinez and Savage, 2.5]
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) <= e(k) and e(i) != e(k). [Martinez and Savage, 2.5]
(End)
Numbers whose Zeckendorf (A014417) and dual Zeckendorf (A104326) representations are the same: alternating digits of 1 and 0. - Amiram Eldar, Nov 01 2019
a(n+2) is the length of the longest array whose local maximum element can be found in at most n reveals. See link to the puzzle by Alexander S. Kulikov. - Dmitry Kamenetsky, Aug 08 2020
a(n+2) is the number of nonempty subsets of {1,2,...,n} that contain no consecutive elements. For example, the a(6)=7 subsets of {1,2,3,4} are {1}, {2}, {3}, {4}, {1,3}, {1,4} and {2,4}. - Muge Olucoglu, Mar 21 2021
a(n+3) is the number of allowed patterns of length n in the even shift (that is, a(n+3) is the number of binary words of length n in which there are an even number of 0s between any two occurrences of 1). For example, a(7)=12 and the 12 allowed patterns of length 4 in the even shift are 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1100, 1110, 1111. - Zoran Sunic, Apr 06 2022
Conjecture: for k a positive odd integer, the sequence {a(k^n): n >= 1} is a strong divisibility sequence; that is, for n, m >= 1, gcd(a(k^n), a(k^m)) = a(k^gcd(n,m)). - Peter Bala, Dec 05 2022
In general, the sum of a second-order linear recurrence having signature (c,d) will be a third-order recurrence having a signature (c+1,d-c,-d). - Gary Detlefs, Jan 05 2023
a(n) is the number of binary strings of length n-2 whose longest run of 1's is of length 1, for n >= 3. - Félix Balado, Apr 03 2025

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
  • GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 28.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 64.
  • D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Links

Crossrefs

Cf. A000032, A000045, A000119, A001611, A001654, A001911, A005968, A005969.
Cf. A006327, A014417, A054761, A081006, A081007, A081008, A081009, A083368.
Cf. A098531, A098532, A098533, A101220, A104326, A105488, A105489, A119282.
Cf. A128697, A157725, A157726, A157727, A157728, A157729, A158950, A167616.
Cf. A001622, A228074.
Antidiagonal sums of array A004070.
Right-hand column 2 of triangle A011794.
Related to sum of Fibonacci(kn) over n. Cf. A099919, A058038, A138134, A053606.
Subsequence of A226538. Also a subsequence of A061489.

Programs

  • Haskell
    a000071 n = a000071_list !! n
a000071_list = map (subtract 1) $ tail a000045_list
-- Reinhard Zumkeller, May 23 2013
  • Magma
    [Fibonacci(n)-1: n in [1..60]]; // Vincenzo Librandi, Apr 04 2011
  • Maple
    A000071 := proc(n) combinat[fibonacci](n)-1 ; end proc; # R. J. Mathar, Apr 07 2011
a:= n-> (Matrix([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^(n-1))[3, 2]; seq(a(n), n=1..50); # Alois P. Heinz, Jul 24 2008
  • Mathematica
    Fibonacci[Range[40]] - 1 (* or *) LinearRecurrence[{2, 0, -1}, {0, 0, 1}, 40] (* Harvey P. Dale, Aug 23 2013 *)
Join[{0}, Accumulate[Fibonacci[Range[0, 39]]]] (* Alonso del Arte, Oct 22 2017, based on Giorgi Dalakishvili's formula *)
  • PARI
    {a(n) = if( n<1, 0, fibonacci(n)-1)};
  • SageMath
    [fibonacci(n)-1 for n in range(1,60)] # G. C. Greubel, Oct 21 2024

Formula

a(n) = A000045(n) - 1.
a(0) = -1, a(1) = 0; thereafter a(n) = a(n-1) + a(n-2) + 1.
a(n) = A101220(1, 1, n-2), for n > 1.
G.f.: x^3/((1-x-x^2)*(1-x)). - Simon Plouffe in his 1992 dissertation, dropping initial 0's
a(n) = 2*a(n-1) - a(n-3). - R. H. Hardin, Apr 02 2011
Partial sums of Fibonacci numbers. - Wolfdieter Lang
a(n) = -1 + (A*B^n + C*D^n)/10, with A, C = 5 +- 3*sqrt(5), B, D = (1 +- sqrt(5))/2. - Ralf Stephan, Mar 02 2003
a(1) = 0, a(2) = 0, a(3) = 1, then a(n) = ceiling(phi*a(n-1)) where phi is the golden ratio (1 + sqrt(5))/2. - Benoit Cloitre, May 06 2003
Conjecture: for all c such that 2*(2 - Phi) <= c < (2 + Phi)*(2 - Phi) we have a(n) = floor(Phi*a(n-1) + c) for n > 4. - Gerald McGarvey, Jul 22 2004. This is true provided n > 3 is changed to n > 4, see proof in Comments section. - Russell Jay Hendel, Mar 15 2015
a(n) = Sum_{k = 0..floor((n-2)/2)} binomial(n-k-2, k+1). - Paul Barry, Sep 23 2004
a(n+3) = Sum_{k = 0..floor(n/3)} binomial(n-2*k, k)*(-1)^k*2^(n-3*k). - Paul Barry, Oct 20 2004
a(n+1) = Sum(binomial(n-r, r)), r = 1, 2, ... which is the case t = 2 and k = 2 in the general case of t-strings and k blocks: a(n+1, k, t) = Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r = 1, 2, ... - Augustine O. Munagi, Apr 11 2005
a(n) = Sum_{k = 0..n-2} k*Fibonacci(n - k - 3). - Ross La Haye, May 31 2006
a(n) = term (3, 2) in the 3 X 3 matrix [1, 1, 0; 1, 0, 0; 1, 0, 1]^(n-1). - Alois P. Heinz, Jul 24 2008
For n >= 4, a(n) = ceiling(phi*a(n-1)), where phi is the golden ratio. - Vladimir Shevelev, Jul 04 2010
Closed-form without two leading zeros g.f.: 1/(1 - 2*x - x^3); ((5 + 2*sqrt(5))*((1 + sqrt(5))/2)^n + (5 - 2*sqrt(5))*((1 - sqrt(5))/2)^n - 5)/5; closed-form with two leading 0's g.f.: x^2/(1 - 2*x - x^3); ((5 + sqrt(5))*((1 + sqrt(5))/2)^n + (5 - sqrt(5))*((1 - sqrt(5))/2)^n - 10)/10. - Tim Monahan, Jul 10 2011
A000119(a(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
a(n) = A228074(n - 1, 2) for n > 2. - Reinhard Zumkeller, Aug 15 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 - x^2)/( x*(4*k + 4 - x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
A083368(a(n+3)) = n. - Reinhard Zumkeller, Aug 10 2014
E.g.f.: 1 - exp(x) + 2*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5). - Ilya Gutkovskiy, Jun 15 2016
a(n) = A000032(3+n) - 1 mod A000045(3+n). - Mario C. Enriquez, Apr 01 2017
a(n) = Sum_{i=0..n-2} Fibonacci(i). - Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005 [corrected by Doug Bell, Jun 01 2017]
a(n+2) = Sum_{j = 0..floor(n/2)} Sum_{k = 0..j} binomial(n - 2*j, k+1)*binomial(j, k). - Tony Foster III, Sep 08 2017
From Peter Bala, Nov 12 2021: (Start)
a(4*n) = Fibonacci(2*n+1)*Lucas(2*n-1) = A081006(n);
a(4*n+1) = Fibonacci(2*n)*Lucas(2*n+1) = A081007(n);
a(4*n+2) = Fibonacci(2*n)*Lucas(2*n+2) = A081008(n);
a(4*n+3) = Fibonacci(2*n+2)*Lucas(2*n+1) = A081009(n). (End)
G.f.: x^3/((1 - x - x^2)*(1 - x)) = Sum_{n >= 0} (-1)^n * x^(n+3) *( Product_{k = 1..n} (k - x)/Product_{k = 1..n+2} (1 - k*x) ) (a telescoping series). - Peter Bala, May 08 2024
Product_{n>=4} (1 + (-1)^n/a(n)) = 3*phi/4, where phi is the golden ratio (A001622). - Amiram Eldar, Nov 28 2024

Extensions

Edited by N. J. A. Sloane, Apr 04 2011

A004006 a(n) = C(n,1) + C(n,2) + C(n,3), or n*(n^2 + 5)/6.

Original entry on oeis.org

0, 1, 3, 7, 14, 25, 41, 63, 92, 129, 175, 231, 298, 377, 469, 575, 696, 833, 987, 1159, 1350, 1561, 1793, 2047, 2324, 2625, 2951, 3303, 3682, 4089, 4525, 4991, 5488, 6017, 6579, 7175, 7806, 8473, 9177, 9919, 10700, 11521, 12383, 13287, 14234, 15225
Offset: 0

Views

Author

Albert D. Rich (Albert_Rich(AT)msn.com)

Keywords

Comments

3-dimensional analog of centered polygonal numbers.
The Burnside group B(3,n) has order 3^a(n).
Answer to the question: if you have a tall building and 3 plates and you need to find the highest story, a plate thrown from which does not break, what is the number of stories you can handle given n tries? - Leonid Broukhis, Oct 24 2000
Equals row sums of triangle A144329 starting with "1". - Gary W. Adamson, Sep 18 2008
Let A be the Hessenberg matrix of order n, defined by: A[1,j]=A[i,i]:=1, A[i,i-1]=-1, and A[i,j]=0 otherwise. Then, for n>=4, a(n-1)=-coeff(charpoly(A,x),x^(n-3)). - Milan Janjic, Jan 24 2010
From J. M. Bergot, Aug 03 2011: (Start)
If one formed the 3 X 3 square
| n | n+1 | n+2 |
| n+3 | n+4 | n+5 |
| n+6 | n+7 | n+8 |
and found the sum of the horizontal products n*(n + 1)*(n + 2) + (n + 3)*(n + 4)*(n + 5) + (n + 6)*(n + 7)*(n + 8) and added the sum of the vertical products n*(n + 3)*(n + 6) + (n + 1)*(n + 4)*(n + 7) + (n + 2)*(n + 5)(n + 8) one gets 6*n^3 + 72*n^2 + 318*n + 504. This will give 36 times the values of all the terms in this sequence. (End)
a(n) is divisible by n for n congruent to {1,5} mod 6. (see A007310). - Gary Detlefs, Dec 08 2011
From Beimar Naranjo, Feb 22 2024: (Start)
Number of compositions with at most three parts and sum at most n.
Also the number of compositions with at most one part distinct from 1 and with a sum at most n. (End)
a(n) is the number of strings of length n defined on {0, 1, 2, 3} that contain one 1 and any number of 0's, or two 2's and any number of 0's, or three 3's and any number of 0's. For example, a(6) = 41 since the strings are the 20 permutations of 333000, the 15 permutations of 220000 and the 6 permutations of 100000. - Enrique Navarrete, Jun 18 2025

Examples

			G.f. = x + 3*x^2 + 7*x^3 + 14*x^4 + 25*x^5 + 41*x^6 + 63*x^7 + 92*x^8 + ... - _Michael Somos_, Dec 29 2019

References

  • W. Magnus, A. Karrass and D. Solitar, Combinatorial Group Theory, Wiley, 1966, see p. 380.

Links

Crossrefs

Cf. A051576, A055795, A006552. Differences give A000217 + 1 or A000124.
1/12*t*(n^3-n)+n for t = 2, 4, 6, ... gives A004006, A006527, A006003, A005900, A004068, A000578, A004126, A000447, A004188, A004466, A004467, A007588, A062025, A063521, A063522, A063523.
Cf. A000292, A001477, A007310, A128834, A144329, A228074.

Programs

Formula

G.f.: x*(1-x+x^2)/(1-x)^4.
E.g.f.: x*(1 + x/2 + x^2/6) * exp(x).
a(-n) = -a(n).
a(n) = binomial(n+2,n-1) - binomial(n,n-2). - Zerinvary Lajos, May 11 2006
Euler transform of length 6 sequence [3, 1, 1, 0, 0, -1]. - Michael Somos, May 04 2007
Starting (1, 3, 7, 14, ...) = binomial transform of [1, 2, 2, 1, 0, 0, 0, ...]. - Gary W. Adamson, Apr 24 2008
a(0)=0, a(1)=1, a(2)=3, a(3)=7, a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4). - Harvey P. Dale, Aug 21 2011
a(n+1) = A000292(n) + n + 1. - Reinhard Zumkeller, Mar 31 2012
a(n) = 2*a(n-1) + (n-1) - a(n-2) with a(0) = 0, a(1) = 1. - Richard R. Forberg, Jan 23 2014
a(n) = Sum_{i=1..n} binomial(n-2i,2). - Wesley Ivan Hurt, Nov 18 2017
a(n) = n + Sum_{k=0..n} k*(n-k). - Gionata Neri, May 19 2018
a(n) = Sum_{k=0..n-1} A000124(k). - Torlach Rush, Aug 05 2018
G.f.: ((1 - x^5)/(1 - x)^5 - 1)/5. - Michael Somos, Dec 29 2019
G.f.: g(f(x)), where g is g.f. of A001477 and f is g.f. of A128834. - Oboifeng Dira, Jun 21 2020
Sum_{n>0} 1/a(n) = 3*(2*gamma + polygamma(0, 1-i*sqrt(5)) + polygamma(0, 1+i*sqrt(5)))/5 = 1.6787729555834452106286261834348972248... where i denotes the imaginary unit. - Stefano Spezia, Aug 31 2023

A001924 Apply partial sum operator twice to Fibonacci numbers.

Original entry on oeis.org

0, 1, 3, 7, 14, 26, 46, 79, 133, 221, 364, 596, 972, 1581, 2567, 4163, 6746, 10926, 17690, 28635, 46345, 75001, 121368, 196392, 317784, 514201, 832011, 1346239, 2178278, 3524546, 5702854, 9227431, 14930317, 24157781, 39088132, 63245948, 102334116, 165580101
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Leading coefficients in certain rook polynomials (for n>=2; see p. 18 of the Riordan paper). - Emeric Deutsch, Mar 08 2004
(1, 3, 7, 14, ...) = row sums of triangle A141289. - Gary W. Adamson, Jun 22 2008
a(n) is the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is at most 2. See example below. Generally, the o.g.f. for the number of nonempty subsets of {1,2,...,n} such that the difference of successive elements is <= k is: x/((1-x)*(1-2*x+x^(k+1))). Cf. A000217 the case for k=1, A001477 the case for k=0 (counts singleton subsets). - Geoffrey Critzer, Feb 17 2012
-Fibonacci(n-2) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, Dec 31 2012
a(n) is the number of bit strings of length n+1 with the pattern 00 and without the pattern 011, see example. - John M. Campbell, Feb 10 2013
From Jianing Song, Apr 28 2025: (Start)
For n >= 2, a(n-2) is the number of subsets of {1,2,...,n} with 2 or more elements that contain no consecutive elements (i.e., such that the difference of successive elements is at least 2). Note that the number of such subsets with k elements is binomial(n+1-k,k), and Sum_{k=2..floor((n+1)/2)} binomial(n+1-k,k) = F(n+2) - binomial(n+1,0) - binomial(n,1) = F(n+2) - (n+1).
If subsets of {1,2,...,n} are required to contain no consecutive elements module n, then the result is A023548(n-3). (End)

Examples

			a(5) = 26 because there are 31 nonempty subsets of {1,2,3,4,5} but 5 of these have successive elements that differ by 3 or more: {1,4}, {1,5}, {2,5}, {1,2,5}, {1,4,5}. - _Geoffrey Critzer_, Feb 17 2012
From _John M. Campbell_, Feb 10 2013: (Start)
There are a(5) = 26 bit strings with the pattern 00 and without the pattern 011 of length 5+1:
   000000, 000001, 000010, 000100, 000101, 001000,
   001001, 001010, 010000, 010001, 010010, 010100,
   100000, 100001, 100010, 100100, 100101, 101000, 101001,
   110000, 110001, 110010, 110100, 111000, 111001, 111100.
(End)

References

  • J. Riordan, Discordant permutations, Scripta Math., 20 (1954), 14-23.
  • 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. A000045, A023548, A001891, A133640, A141289.
Right-hand column 4 of triangle A011794.
Cf. A014162, A039834, A077880, A122595, A129696.
Cf. A065220.

Programs

  • GAP
    List([0..40], n-> Fibonacci(n+4) -n-3); # G. C. Greubel, Jul 08 2019
  • Haskell
    a001924 n = a001924_list !! n
a001924_list = drop 3 $ zipWith (-) (tail a000045_list) [0..]
-- Reinhard Zumkeller, Nov 17 2013
  • Magma
    [Fibonacci(n+4)-(n+3): n in [0..40]]; // Vincenzo Librandi, Jun 23 2016
  • Maple
    A001924:=-1/(z**2+z-1)/(z-1)**2; # Conjectured by Simon Plouffe in his 1992 dissertation.
##
a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <1|-1|-2|3>>^n.
         <<0, 1, 3, 7>>)[1, 1]:
seq(a(n), n=0..40);  # Alois P. Heinz, Oct 05 2012
  • Mathematica
    a[n_]:= Fibonacci[n+4] -3-n; Array[a, 40, 0]  (* Robert G. Wilson v *)
LinearRecurrence[{3,-2,-1,1},{0,1,3,7},40] (* Harvey P. Dale, Jan 24 2015 *)
Nest[Accumulate,Fibonacci[Range[0,40]],2] (* Harvey P. Dale, Jun 15 2016 *)
  • PARI
    a(n)=fibonacci(n+4)-n-3 \\ Charles R Greathouse IV, Feb 24 2011
  • Sage
    [fibonacci(n+4) -n-3 for n in (0..40)] # G. C. Greubel, Jul 08 2019

Formula

From Wolfdieter Lang: (Start)
G.f.: x/((1-x-x^2)*(1-x)^2).
Convolution of natural numbers n >= 1 with Fibonacci numbers F(k).
a(n) = Fibonacci(n+4) - (3+n). (End)
From Henry Bottomley, Jan 03 2003: (Start)
a(n) = a(n-1) + a(n-2) + n = a(n-1) + A000071(n+2).
a(n) = A001891(n) - a(n-1) = n + A001891(n-1).
a(n) = A065220(n+4) + 1 = A000126(n+1) - 1. (End)
a(n) = Sum_{k=0..n} Sum_{i=0..k} Fibonacci(i). - Benoit Cloitre, Jan 26 2003
a(n) = (sqrt(5)/2 + 1/2)^n*(7*sqrt(5)/10 + 3/2) + (3/2 - 7*sqrt(5)/10)*(sqrt(5)/2 - 1/2)^n*(-1)^n - n - 3. - Paul Barry, Mar 26 2003
a(n) = Sum_{k=0..n} Fibonacci(k)*(n-k). - Benoit Cloitre, Jun 07 2004
A107909(a(n)) = A000225(n) = 2^n - 1. - Reinhard Zumkeller, May 28 2005
a(n) - a(n-1) = A101220(1,1,n). - Ross La Haye, May 31 2006
F(n) + a(n-3) = A133640(n). - Gary W. Adamson, Sep 19 2007
a(n) = A077880(-3-n) = 2*a(n-1) - a(n-3) + 1. - Michael Somos, Dec 31 2012
INVERT transform is A122595. PSUM transform is A014162. PSUMSIGN transform is A129696. BINOMIAL transform of A039834 with 0,1 prepended is this sequence. - Michael Somos, Dec 31 2012
a(n) = A228074(n+1,3) for n > 1. - Reinhard Zumkeller, Aug 15 2013
a(n) = Sum_{k=0..n} Sum_{i=0..n} i * C(n-k,k-i). - Wesley Ivan Hurt, Sep 21 2017
E.g.f.: exp(x/2)*(15*cosh(sqrt(5)*x/2) + 7*sqrt(5)*sinh(sqrt(5)*x/2))/5 - exp(x)*(3 + x). - Stefano Spezia, Jun 25 2022

Extensions

Description improved by N. J. A. Sloane, Jan 01 1997

A037027 Skew Fibonacci-Pascal triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 3, 5, 3, 1, 5, 10, 9, 4, 1, 8, 20, 22, 14, 5, 1, 13, 38, 51, 40, 20, 6, 1, 21, 71, 111, 105, 65, 27, 7, 1, 34, 130, 233, 256, 190, 98, 35, 8, 1, 55, 235, 474, 594, 511, 315, 140, 44, 9, 1, 89, 420, 942, 1324, 1295, 924, 490, 192, 54, 10, 1, 144, 744, 1836
Offset: 0

Views

Author

Floor van Lamoen, Jan 01 1999

Keywords

Comments

T(n,k) is the number of lattice paths from (0,0) to (n,k) using steps (0,1), (1,0), (2,0). - Joerg Arndt, Jun 30 2011
T(n,k) is the number of lattice paths of length n, starting from the origin and ending at (n,k), using horizontal steps H=(1,0), up steps U=(1,1) and down steps D=(1,-1), never containing UUU, DD, HD. For instance, for n=4 and k=2, we have the paths; HHUU, HUHU, HUUH, UHHU, UHUH, UUHH, UUDU, UDUU, UUUD. - Emanuele Munarini, Mar 15 2011
Row sums form Pell numbers A000129, T(n,0) forms Fibonacci numbers A000045, T(n,1) forms A001629. T(n+k,n-k) is polynomial sequence of degree k.
T(n,k) gives a convolved Fibonacci sequence (A001629, A001872, etc.).
As a Riordan array, this is (1/(1-x-x^2),x/(1-x-x^2)). An interesting factorization is (1/(1-x^2),x/(1-x^2))*(1/(1-x),x/(1-x)) [abs(A049310) times A007318]. Diagonal sums are the Jacobsthal numbers A001045(n+1). - Paul Barry, Jul 28 2005
T(n,k) = T'(n+1,k+1), T' given by [0, 1, 1, -1, 0, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 19 2005
Equals A049310 * A007318 as infinite lower triangular matrices. - Gary W. Adamson, Oct 28 2007
This triangle may also be obtained from the coefficients of the Morgan-Voyce polynomials defined by: Mv(x, n) = (x + 1)*Mv(x, n - 1) + Mv(x, n - 2). - Roger L. Bagula, Apr 09 2008
Row sums are A000129. - Roger L. Bagula, Apr 09 2008
Absolute value of coefficients of the characteristic polynomial of tridiagonal matrices with 1's along the main diagonal, and i's along the superdiagonal and the subdiagonal (where i=sqrt(-1), see Mathematica program). - John M. Campbell, Aug 23 2011
A037027 is jointly generated with A122075 as an array of coefficients of polynomials v(n,x): initially, u(1,x)=v(1,x)=1; for n>1, u(n,x)=u(n-1,x)+(x+1)*v(n-1)x and v(n,x)=u(n-1,x)+x*v(n-1,x). See the Mathematica section at A122075. - Clark Kimberling, Mar 05 2012
For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013
Row n, for n>=0, shows the coefficients of the polynomial u(n) = c(0) + c(1)*x + ... + c(n)*x^n which is the denominator of the n-th convergent of the continued fraction [x+1, x+1, x+1, ...]; see A230000. - Clark Kimberling, Nov 13 2013
T(n,k) is the number of ternary words of length n having k letters 2 and avoiding a runs of odd length for the letter 0. - Milan Janjic, Jan 14 2017
Let T(m, n, k) be an m-bonacci Pascal's triangle, where T(m, n, 0) gives the values of F(m, n), the n-th m-bonacci number, and T(m, n, k) gives the values for the k-th convolution of F(m, n). Then the classic Pascal triangle is T(1, n, k) and this sequence is T(2, n, k). T(m, n, k) is the number of compositions of n using only the positive integers 1, 1' and 2 through m, with the part 1' used exactly k times. G.f. for k-th column of T(m, n, k): x/(1 - x - x^2 - ... - x^m)^k. The row sum for T(m, n, k) is the number of compositions of n using only the positive integers 1, 1' and 2 through m. G.f. for row sum of T(m, n, k): 1/(1 - 2x - x^2 - ... - x^m). - Gregory L. Simay, Jul 24 2021

Examples

			Ratio of row polynomials R(3)/R(2) = (3 + 5*x + 3*x^2 + x^3)/(2 + 2*x + x^2) = [1+x; 1+x, 1+x].
Triangle begins:
                                 1;
                              1,    1;
                           2,    2,    1;
                        3,    5,    3,    1;
                     5,   10,    9,    4,    1;
                  8,   20,   22,   14,    5,    1;
              13,   38,   51,   40,   20,    6,    1;
           21,   71,  111,  105,   65,   27,    7,    1;
        34,  130,  233,  256,  190,   98,   35,    8,    1;
     55,  235,  474,  594,  511,  315,  140,   44,    9,    1;
  89,  420,  942, 1324, 1295,  924,  490,  192,   54,   10,    1;

Links

Crossrefs

A038112(n) = T(2n, n). A038137 is reflected version. Maximal row entries: A038149.
Diagonal differences are in A055830. Vertical sums are in A091186.
Cf. A007318, A049310, A000129, A155161, A122542, A059283, A228196, A228576.
Some other Fibonacci-Pascal triangles: A027926, A036355, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

Programs

  • Haskell
    a037027 n k = a037027_tabl !! n !! k
a037027_row n = a037027_tabl !! n
a037027_tabl = [1] : [1,1] : f [1] [1,1] where
   f xs ys = ys' : f ys ys' where
     ys' = zipWith3 (\u v w -> u + v + w) (ys ++ [0]) (xs ++ [0,0]) ([0] ++ ys)
-- Reinhard Zumkeller, Jul 07 2012
  • Maple
    T := (n,k) -> `if`(n=0,1,binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [-n], -4)): seq(seq(simplify(T(n,k)), k=0..n), n=0..10); # Peter Luschny, Apr 25 2016
# Uses function PMatrix from A357368. Adds a row above and a column to the left.
PMatrix(10, n -> combinat:-fibonacci(n)); # Peter Luschny, Oct 07 2022
  • Mathematica
    Mv[x, -1] = 0; Mv[x, 0] = 1; Mv[x, 1] = 1 + x; Mv[x_, n_] := Mv[x, n] = ExpandAll[(x + 1)*Mv[x, n - 1] + Mv[x, n - 2]]; Table[ CoefficientList[ Mv[x, n], x], {n, 0, 10}] // Flatten (* Roger L. Bagula, Apr 09 2008 *)
Abs[Flatten[Table[CoefficientList[CharacteristicPolynomial[Array[KroneckerDelta[#1,#2]+KroneckerDelta[#1,#2+1]*I+KroneckerDelta[#1,#2-1]*I&,{n,n}],x],x],{n,1,20}]]] (* John M. Campbell, Aug 23 2011 *)
T[n_, k_] := Binomial[n, k] Hypergeometric2F1[(k-n)/2, (k-n+1)/2, -n, -4];
Table[T[n, k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 16 2019, after Peter Luschny *)
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, if( n==0 && k==0, 1, T(n-1, k) + T(n-1, k-1) + T(n-2, k)))}; /* Michael Somos, Sep 29 2003 */
  • PARI
    T(n,k)=if(nPaul D. Hanna, Feb 27 2004

Formula

T(n, m) = T'(n-1, m) + T'(n-2, m) + T'(n-1, m-1), where T'(n, m) = T(n, m) for n >= 0 and 0< = m <= n and T'(n, m) = 0 otherwise.
G.f.: 1/(1 - y - y*z - y^2).
G.f. for k-th column: x/(1-x-x^2)^k.
T(n, m) = Sum_{k=0..n-m} binomial(m+k, m)*binomial(k, n-k-m), n >= m >= 0, otherwise 0. - Wolfdieter Lang, Jun 17 2002
T(n, m) = ((n-m+1)*T(n, m-1) + 2*(n+m)*T(n-1, m-1))/(5*m), n >= m >= 1; T(n, 0)= A000045(n+1); T(n, m)= 0 if n < m. - Wolfdieter Lang, Apr 12 2000
Chebyshev coefficient triangle (abs(A049310)) times Pascal's triangle (A007318) as product of lower triangular matrices. T(n, k) = Sum_{j=0..n} binomial((n+j)/2, j)*(1+(-1)^(n+j))*binomial(j, k)/2. - Paul Barry, Dec 22 2004
Let R(n) = n-th row polynomial in x, with R(0)=1, then R(n+1)/R(n) equals the continued fraction [1+x;1+x, ...(1+x) occurring (n+1) times ..., 1+x] for n >= 0. - Paul D. Hanna, Feb 27 2004
T(n,k) = Sum_{j=0..n} binomial(n-j,j)*binomial(n-2*j,k); in Egorychev notation, T(n,k) = res_w(1-w-w^2)^(-k-1)*w^(-n+k+1). - Paul Barry, Sep 13 2006
Sum_{k=0..n} T(n,k)*x^k = A000045(n+1), A000129(n+1), A006190(n+1), A001076(n+1), A052918(n), A005668(n+1), A054413(n), A041025(n), A099371(n+1), A041041(n), A049666(n+1), A041061(n), A140455(n+1), A041085(n), A154597(n+1), A041113(n) for x = 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 respectively. - Philippe Deléham, Nov 29 2009
T((m+1)*n+r-1, m*n+r-1)*r/(m*n+r) = Sum_{k=1..n} k/n*T((m+1)*n-k-1, m*n-1)*(r+k,r), n >= m > 1.
T(n-1,m-1) = (m/n)*Sum_{k=1..n-m+1} k*A000045(k)*T(n-k-1,m-2), n >= m > 1. - Vladimir Kruchinin, Mar 17 2011
T(n,k) = binomial(n,k)*hypergeom([(k-n)/2, (k-n+1)/2], [-n], -4) for n >= 1. - Peter Luschny, Apr 25 2016

Extensions

Examples from Paul D. Hanna, Feb 27 2004

A027926 Triangular array T read by rows: T(n,0) = T(n,2n) = 1 for n >= 0; T(n,1) = 1 for n >= 1; T(n,k) = T(n-1,k-2) + T(n-1,k-1) for k = 2..2n-1, n >= 2.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 1, 2, 3, 4, 3, 1, 1, 1, 2, 3, 5, 7, 7, 4, 1, 1, 1, 2, 3, 5, 8, 12, 14, 11, 5, 1, 1, 1, 2, 3, 5, 8, 13, 20, 26, 25, 16, 6, 1, 1, 1, 2, 3, 5, 8, 13, 21, 33, 46, 51, 41, 22, 7, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 54, 79, 97, 92, 63, 29, 8, 1
Offset: 0

Views

Author

Clark Kimberling

Keywords

Comments

T(n,k) = number of strings s(0),...,s(n) such that s(0)=0, s(n)=n-k and for 1<=i<=n, s(i)=s(i-1)+d, with d in {0,1,2} if i=0, in {0,2} if s(i)=2i, in {0,1,2} if s(i)=2i-1, in {0,1} if 0<=s(i)<=2i-2.
Can be seen as concatenation of triangles A104763 and A105809, with identifying column of Fibonacci numbers, see example. - Reinhard Zumkeller, Aug 15 2013

Examples

			.   0:                           1
.   1:                        1  1   1
.   2:                     1  1  2   2   1
.   3:                  1  1  2  3   4   3   1
.   4:               1  1  2  3  5   7   7   4   1
.   5:            1  1  2  3  5  8  12  14  11   5   1
.   6:          1 1  2  3  5  8 13  20  26  25  16   6   1
.   7:        1 1 2  3  5  8 13 21  33  46  51  41  22   7   1
.   8:      1 1 2 3  5  8 13 21 34  54  79  97  92  63  29   8  1
.   9:    1 1 2 3 5  8 13 21 34 55  88 133 176 189 155  92  37  9  1
.  10:  1 1 2 3 5 8 13 21 34 55 89 143 221 309 365 344 247 129 46 10  1
.
.   1:                           1
.   2:                        1  1
.   3:                     1  1  2
.   4:                  1  1  2  3
.   5:               1  1  2  3  5      columns = A000045, > 0
.   6:            1  1  2  3  5  8     +---------+
.   7:          1 1  2  3  5  8 13     | A104763 |
.   8:        1 1 2  3  5  8 13 21     +---------+
.   9:      1 1 2 3  5  8 13 21 34
.  10:    1 1 2 3 5  8 13 21 34 55
.  11:  1 1 2 3 5 8 13 21 34 55 89
.
.   0:                           1
.   1:                           1   1                +---------+
.   2:                           2   2   1            | A105809 |
.   3:                           3   4   3   1        +---------+
.   4:                           5   7   7   4   1
.   5:                           8  12  14  11   5   1
.   6:                          13  20  26  25  16   6   1
.   7:                          21  33  46  51  41  22   7   1
.   8:                          34  54  79  97  92  63  29   8  1
.   9:                          55  88 133 176 189 155  92  37  9  1
.  10:                          89 143 221 309 365 344 247 129 46 10  1

Links

Crossrefs

Many columns of T are A000045 (Fibonacci sequence), also in T: A001924, A004006, A000071, A000124, A014162, A014166, A027927-A027933.
Some other Fibonacci-Pascal triangles: A036355, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

Programs

  • GAP
    Flat(List([0..10], n-> List([0..2*n], k-> Sum([0..Int((2*n-k+1)/2) ], j-> Binomial(n-j, 2*n-k-2*j) )))); # G. C. Greubel, Sep 05 2019
  • Haskell
    a027926 n k = a027926_tabf !! n !! k
a027926_row n = a027926_tabf !! n
a027926_tabf = iterate (\xs -> zipWith (+)
                               ([0] ++ xs ++ [0]) ([1,0] ++ xs)) [1]
-- Variant, cf. example:
a027926_tabf' = zipWith (++) a104763_tabl (map tail a105809_tabl)
-- Reinhard Zumkeller, Aug 15 2013
  • Magma
    [&+[Binomial(n-j, 2*n-k-2*j): j in [0..Floor((2*n-k+1)/2)]]: k in [0..2*n], n in [0..10]]; // G. C. Greubel, Sep 05 2019
  • Maple
    A027926 := proc(n,k)
    add(binomial(n-j,2*n-k-2*j),j=0..(2*n-k+1)/2) ;
end proc: # R. J. Mathar, Apr 11 2016
  • Mathematica
    z = 15; t[n_, 0] := 1; t[n_, k_] := 1 /; k == 2 n; t[n_, 1] := 1;
t[n_, k_] := t[n, k] = t[n - 1, k - 2] + t[n - 1, k - 1];
u = Table[t[n, k], {n, 0, z}, {k, 0, 2 n}];
TableForm[u] (* A027926 array *)
v = Flatten[u] (* A027926 sequence *)
(* Clark Kimberling, Aug 31 2014 *)
Table[Sum[Binomial[n-j, 2*n-k-2*j], {j, 0, Floor[(2*n-k+1)/2]}], {n, 0, 10}, {k, 0, 2*n}]//Flatten (* G. C. Greubel, Sep 05 2019 *)
  • PARI
    {T(n, k) = if( k<0 || k>2*n, 0, if( k<=1 || k==2*n, 1, T(n-1, k-2) + T(n-1, k-1)))}; /* _Michael Somos, Feb 26 1999 */
  • PARI
    {T(n, k) = if( k<0 || k>2*n, 0, sum( j=max(0, k-n), k\2, binomial(k-j, j)))}; /* Michael Somos */
  • Sage
    [[sum(binomial(n-j, 2*n-k-2*j) for j in (0..floor((2*n-k+1)/2))) for k in (0..2*n)] for n in (0..10)] # G. C. Greubel, Sep 05 2019

Formula

T(n, k) = Sum_{j=0..floor((2*n-k+1)/2)} binomial(n-j, 2*n-k-2*j). - Len Smiley, Oct 21 2001

Extensions

Incorporates comments from Michael Somos.
Example extended by Reinhard Zumkeller, Aug 15 2013

A228196 A triangle formed like Pascal's triangle, but with n^2 on the left border and 2^n on the right border instead of 1.

Original entry on oeis.org

0, 1, 2, 4, 3, 4, 9, 7, 7, 8, 16, 16, 14, 15, 16, 25, 32, 30, 29, 31, 32, 36, 57, 62, 59, 60, 63, 64, 49, 93, 119, 121, 119, 123, 127, 128, 64, 142, 212, 240, 240, 242, 250, 255, 256, 81, 206, 354, 452, 480, 482, 492, 505, 511, 512, 100, 287, 560, 806, 932, 962, 974, 997, 1016, 1023, 1024
Offset: 1

Views

Author

Boris Putievskiy, Aug 15 2013

Keywords

Comments

The third row is (n^4 - n^2 + 24*n + 24)/12.
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 04 2013

Examples

			The start of the sequence as a triangular array read by rows:
   0;
   1,  2;
   4,  3,  4;
   9,  7,  7,  8;
  16, 16, 14, 15, 16;
  25, 32, 30, 29, 31, 32;
  36, 57, 62, 59, 60, 63, 64;

Links

Crossrefs

Cf. We denote Pascal-like triangle with L(n) on the left border and R(n) on the right border by (L(n),R(n)). A007318 (1,1), A008949 (1,2^n), A029600 (2,3), A029618 (3,2), A029635 (1,2), A029653 (2,1), A037027 (Fibonacci(n),1), A051601 (n,n) n>=0, A051597 (n,n) n>0, A051666 (n^2,n^2), A071919 (1,0), A074829 (Fibonacci(n), Fibonacci(n)), A074909 (1,n), A093560 (3,1), A093561 (4,1), A093562 (5,1), A093563 (6,1), A093564 (7,1), A093565 (8,1), A093644 (9,1), A093645 (10,1), A095660 (1,3), A095666 (1,4), A096940 (1,5), A096956 (1,6), A106516 (3^n,1), A108561(1,(-1)^n), A132200 (4,4), A134636 (2n+1,2n+1), A137688 (2^n,2^n), A160760 (3^(n-1),1), A164844(1,10^n), A164847 (100^n,1), A164855 (101*100^n,1), A164866 (101^n,1), A172171 (1,9), A172185 (9,11), A172283 (-9,11), A177954 (int(n/2),1), A193820 (1,2^n), A214292 (n,-n), A227074 (4^n,4^n), A227075 (3^n,3^n), A227076 (5^n,5^n), A227550 (n!,n!), A228053 ((-1)^n,(-1)^n), A228074 (Fibonacci(n), n).
Cf. A000290 (row 1), A153056 (row 2), A000079 (column 1), A000225 (column 2), A132753 (column 3), A118885 (row sums of triangle array + 1), A228576 (generalized Pascal's triangle).

Programs

  • GAP
    T:= function(n,k)
    if k=0 then return n^2;
    elif k=n then return 2^n;
    else return T(n-1,k-1) + T(n-1,k);
    fi;
  end;
Flat(List([0..12], n-> List([0..n], k-> T(n,k) ))); # G. C. Greubel, Nov 12 2019
  • Maple
    T:= proc(n, k) option remember;
      if k=0 then n^2
    elif k=n then 2^k
    else T(n-1, k-1) + T(n-1, k)
      fi
    end:
seq(seq(T(n, k), k=0..n), n=0..10); # G. C. Greubel, Nov 12 2019
  • Mathematica
    T[n_, k_]:= T[n, k] = If[k==0, n^2, If[k==n, 2^k, T[n-1, k-1] + T[n-1, k]]]; Table[T[n, k], {n,0,10}, {k,0,n}]//Flatten (* G. C. Greubel, Nov 12 2019 *)
Flatten[Table[Sum[i^2 Binomial[n-1-i, n-k-i], {i,1,n-k}] + Sum[2^i Binomial[n-1-i, k-i], {i,1,k}], {n,0,10}, {k,0,n}]] (* Greg Dresden, Aug 06 2022 *)
  • PARI
    T(n,k) = if(k==0, n^2, if(k==n, 2^k, T(n-1, k-1) + T(n-1, k) )); \\ G. C. Greubel, Nov 12 2019
  • Python
    def funcL(n):
   q = n**2
   return q
def funcR(n):
   q = 2**n
   return q
for n in range (1,9871):
   t=int((math.sqrt(8*n-7) - 1)/ 2)
   i=n-t*(t+1)/2-1
   j=(t*t+3*t+4)/2-n-1
   sum1=0
   sum2=0
   for m1 in range (1,i+1):
      sum1=sum1+funcR(m1)*binomial(i+j-m1-1,i-m1)
   for m2 in range (1,j+1):
      sum2=sum2+funcL(m2)*binomial(i+j-m2-1,j-m2)
   sum=sum1+sum2
  • Sage
    @CachedFunction
def T(n, k):
    if (k==0): return n^2
    elif (k==n): return 2^n
    else: return T(n-1, k-1) + T(n-1, k)
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, Nov 12 2019

Formula

T(n,0) = n^2, n>0; T(0,k) = 2^k; T(n, k) = T(n-1, k-1) + T(n-1, k) for n,k > 0. [corrected by G. C. Greubel, Nov 12 2019]
Closed-form formula for general case. Let L(m) and R(m) be the left border and the right border of Pascal like triangle, respectively. We denote binomial(n,k) by C(n,k).
As table read by antidiagonals T(n,k) = Sum_{m1=1..n} R(m1)*C(n+k-m1-1, n-m1) + Sum_{m2=1..k} L(m2)*C(n+k-m2-1, k-m2); n,k >=0.
As linear sequence a(n) = Sum_{m1=1..i} R(m1)*C(i+j-m1-1, i-m1) + Sum_{m2=1..j} L(m2)*C(i+j-m2-1, j-m2), where i=n-t*(t+1)/2-1, j=(t*t+3*t+4)/2-n-1, t=floor((-1+sqrt(8*n-7))/2); n>0.
Some special cases. If L(m)={b,b,b...} b*A000012, then the second sum takes form b*C(n+k-1,j). If L(m) is {0,b,2b,...} b*A001477, then the second sum takes form b*C(n+k,n-1). Similarly for R(m) and the first sum.
For this sequence L(m)=m^2 and R(m)=2^m.
As table read by antidiagonals T(n,k) = Sum_{m1=1..n} (2^m1)*C(n+k-m1-1, n-m1) + Sum_{m2=1..k} (m2^2)*C(n+k-m2-1, k-m2); n,k >=0.
As linear sequence a(n) = Sum_{m1=1..i} (2^m1)*C(i+j-m1-1, i-m1) + Sum_{m2=1..j} (m2^2)*C(i+j-m2-1, j-m2), where i=n-t*(t+1)/2-1, j=(t*t+3*t+4)/2-n-1, t=floor((-1+sqrt(8*n-7))/2).
As a triangular array read by rows, T(n,k) = Sum_{i=1..n-k} i^2*C(n-1-i, n-k-i) + Sum_{i=1..k} 2^i*C(n-1-i, k-i); n,k >=0. - Greg Dresden, Aug 06 2022

Extensions

Cross-references corrected and extended by Philippe Deléham, Dec 27 2013

A036355 Fibonacci-Pascal triangle read by rows.

Original entry on oeis.org

1, 1, 1, 2, 2, 2, 3, 5, 5, 3, 5, 10, 14, 10, 5, 8, 20, 32, 32, 20, 8, 13, 38, 71, 84, 71, 38, 13, 21, 71, 149, 207, 207, 149, 71, 21, 34, 130, 304, 478, 556, 478, 304, 130, 34, 55, 235, 604, 1060, 1390, 1390, 1060, 604, 235, 55, 89, 420, 1177, 2272, 3310, 3736, 3310, 2272, 1177, 420, 89
Offset: 0

Views

Author

Floor van Lamoen, Dec 28 1998

Keywords

Comments

T(n,k) is the number of lattice paths from (0,0) to (n-k,k) using steps (1,0),(2,0),(0,1),(0,2). - Joerg Arndt, Jun 30 2011, corrected by Greg Dresden, Aug 25 2020
For a closed-form formula for arbitrary left and right borders of Pascal like triangle see A228196. - Boris Putievskiy, Aug 18 2013
For a closed-form formula for generalized Pascal's triangle see A228576. - Boris Putievskiy, Sep 09 2013

Examples

			Triangle begins
   1;
   1,   1;
   2,   2,   2;
   3,   5,   5,    3;
   5,  10,  14,   10,    5;
   8,  20,  32,   32,   20,    8;
  13,  38,  71,   84,   71,   38,   13;
  21,  71, 149,  207,  207,  149,   71,  21;
  34, 130, 304,  478,  556,  478,  304, 130,  34;
  55, 235, 604, 1060, 1390, 1390, 1060, 604, 235, 55;
with indices
  T(0,0);
  T(1,0),  T(1,1);
  T(2,0),  T(2,1),  T(2,2);
  T(3,0),  T(3,1),  T(3,2),  T(3,3);
  T(4,0),  T(4,1),  T(4,2),  T(4,3),  T(4,4);
For example, T(4,2) = 14 and there are 14 lattice paths from (0,0) to (4-2,2) = (2,2) using steps (1,0),(2,0),(0,1),(0,2). - _Greg Dresden_, Aug 25 2020

Links

Crossrefs

Row sums form sequence A002605. T(n, 0) forms the Fibonacci sequence (A000045). T(n, 1) forms sequence A001629.
Derived sequences: A036681, A036682, A036683, A036684, A036692 (central terms).
Cf. A007318, A051159, A091533, A228196, A228576.
Some other Fibonacci-Pascal triangles: A027926, A037027, A074829, A105809, A109906, A111006, A114197, A162741, A228074.

Programs

  • Haskell
    a036355 n k = a036355_tabl !! n !! k
a036355_row n = a036355_tabl !! n
a036355_tabl = [1] : f [1] [1,1] where
   f us vs = vs : f vs (zipWith (+)
                       (zipWith (+) ([0,0] ++ us) (us ++ [0,0]))
                       (zipWith (+) ([0] ++ vs) (vs ++ [0])))
-- Reinhard Zumkeller, Apr 23 2013
  • Mathematica
    nmax = 11; t[n_, m_] := t[n, m] = tp[n-1, m-1] + tp[n-2, m-2] + tp[n-1, m] + tp[n-2, m]; tp[n_, m_] /; 0 <= m <= n && n >= 0 := t[n, m]; tp[n_, m_] = 0; t[0, 0] = 1; Flatten[ Table[t[n, m], {n, 0, nmax}, {m, 0, n}]] (* Jean-François Alcover, Nov 09 2011, after formula *)
  • PARI
    /* same as in A092566 but use */
steps=[[1,0], [2,0], [0,1], [0,2]];
/* Joerg Arndt, Jun 30 2011 */

Formula

T(n, m) = T'(n-1, m-1)+T'(n-2, m-2)+T'(n-1, m)+T'(n-2, m), where T'(n, m) = T(n, m) if 0<=m<=n and n >= 0 and T'(n, m)=0 otherwise. Initial term T(0, 0)=1.
G.f.: 1/(1-(1+y)*x-(1+y^2)*x^2). - Vladeta Jovovic, Oct 11 2003
Showing 1-10 of 34 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.