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 37 results. Next

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

A001109 a(n)^2 is a triangular number: a(n) = 6*a(n-1) - a(n-2) with a(0)=0, a(1)=1.

Original entry on oeis.org

0, 1, 6, 35, 204, 1189, 6930, 40391, 235416, 1372105, 7997214, 46611179, 271669860, 1583407981, 9228778026, 53789260175, 313506783024, 1827251437969, 10650001844790, 62072759630771, 361786555939836, 2108646576008245, 12290092900109634, 71631910824649559, 417501372047787720
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

8*a(n)^2 + 1 = 8*A001110(n) + 1 = A055792(n+1) is a perfect square. - Gregory V. Richardson, Oct 05 2002
For n >= 2, A001108(n) gives exactly the positive integers m such that 1,2,...,m has a perfect median. The sequence of associated perfect medians is the present sequence. Let a_1,...,a_m be an (ordered) sequence of real numbers, then a term a_k is a perfect median if Sum_{j=1..k-1} a_j = Sum_{j=k+1..m} a_j. See Puzzle 1 in MSRI Emissary, Fall 2005. - Asher Auel, Jan 12 2006
(a(n), b(n)) where b(n) = A082291(n) are the integer solutions of the equation 2*binomial(b,a) = binomial(b+2,a). - Klaus Strassburger (strass(AT)ddfi.uni-duesseldorf.de); comment revised by Michael Somos, Apr 07 2003
This sequence gives the values of y in solutions of the Diophantine equation x^2 - 8y^2 = 1. It also gives the values of the product xy where (x,y) satisfies x^2 - 2y^2 = +-1, i.e., a(n) = A001333(n)*A000129(n). a(n) also gives the inradius r of primitive Pythagorean triangles having legs whose lengths are consecutive integers, with corresponding semiperimeter s = a(n+1) = {A001652(n) + A046090(n) + A001653(n)}/2 and area rs = A029549(n) = 6*A029546(n). - Lekraj Beedassy, Apr 23 2003 [edited by Jon E. Schoenfield, May 04 2014]
n such that 8*n^2 = floor(sqrt(8)*n*ceiling(sqrt(8)*n)). - Benoit Cloitre, May 10 2003
For n > 0, ratios a(n+1)/a(n) may be obtained as convergents to continued fraction expansion of 3+sqrt(8): either successive convergents of [6;-6] or odd convergents of [5;1, 4]. - Lekraj Beedassy, Sep 09 2003
a(n+1) + A053141(n) = A001108(n+1). Generating floretion: - 2'i + 2'j - 'k + i' + j' - k' + 2'ii' - 'jj' - 2'kk' + 'ij' + 'ik' + 'ji' + 'jk' - 2'kj' + 2e ("jes" series). - Creighton Dement, Dec 16 2004
Kekulé numbers for certain benzenoids (see the Cyvin-Gutman reference). - Emeric Deutsch, Jun 19 2005
Number of D steps on the line y=x in all Delannoy paths of length n (a Delannoy path of length n is a path from (0,0) to (n,n), consisting of steps E=(1,0), N=(0,1) and D=(1,1)). Example: a(2)=6 because in the 13 (=A001850(2)) Delannoy paths of length 2, namely (DD), (D)NE, (D)EN, NE(D), NENE, NEEN, NDE, NNEE, EN(D), ENNE, ENEN, EDN and EENN, we have altogether six D steps on the line y=x (shown between parentheses). - Emeric Deutsch, Jul 07 2005
Define a T-circle to be a first-quadrant circle with integral radius that is tangent to the x- and y-axes. Such a circle has coordinates equal to its radius. Let C(0) be the T-circle with radius 1. Then for n > 0, define C(n) to be the smallest T-circle that does not intersect C(n-1). C(n) has radius a(n+1). Cf. A001653. - Charlie Marion, Sep 14 2005
Numbers such that there is an m with t(n+m)=2t(m), where t(n) are the triangular numbers A000217. For instance, t(20)=2*t(14)=210, so 6 is in the sequence. - Floor van Lamoen, Oct 13 2005
One half the bisection of the Pell numbers (A000129). - Franklin T. Adams-Watters, Jan 08 2006
Pell trapezoids: for n > 0, a(n) = (A000129(n-1)+A000129(n+1))*A000129(n)/2; see also A084158. - Charlie Marion, Apr 01 2006
Tested for 2 < p < 27: If and only if 2^p - 1 (the Mersenne number M(p)) is prime then M(p) divides a(2^(p-1)). - Kenneth J Ramsey, May 16 2006
If 2^p - 1 is prime then M(p) divides a(2^(p-1)-1). - Kenneth J Ramsey, Jun 08 2006; comment corrected by Robert Israel, Mar 18 2007
If 8*n+5 and 8*n+7 are twin primes then their product divides a(4*n+3). - Kenneth J Ramsey, Jun 08 2006
If p is an odd prime, then if p == 1 or 7 (mod 8), then a((p-1)/2) == 0 (mod p) and a((p+1)/2) == 1 (mod p); if p == 3 or 5 (mod 8), then a((p-1)/2) == 1 (mod p) and a((p+1)/2) == 0 (mod p). Kenneth J Ramsey's comment about twin primes follows from this. - Robert Israel, Mar 18 2007
a(n)*(a(n+b) - a(b-2)) = (a(n+1)+1)*(a(n+b-1) - a(b-1)). This identity also applies to any series a(0) = 0 a(1) = 1 a(n) = b*a(n-1) - a(n-2). - Kenneth J Ramsey, Oct 17 2007
For n < 0, let a(n) = -a(-n). Then (a(n+j) + a(k+j)) * (a(n+b+k+j) - a(b-j-2)) = (a(n+j+1) + a(k+j+1)) * (a(n+b+k+j-1) - a(b-j-1)). - Charlie Marion, Mar 04 2011
Sequence gives y values of the Diophantine equation: 0+1+2+...+x = y^2. If (a,b) and (c,d) are two consecutive solutions of the Diophantine equation: 0+1+2+...+x = y^2 with aMohamed Bouhamida, Aug 29 2009
If (p,q) and (r,s) are two consecutive solutions of the Diophantine equation: 0+1+2+...+x = y^2 with p < r then r = 3*p+4*q+1 and s = 2*p+3*q+1. - Mohamed Bouhamida, Sep 02 2009
a(n)/A002315(n) converges to cos^2(Pi/8) (see A201488). - Gary Detlefs, Nov 25 2009
Binomial transform of A086347. - Johannes W. Meijer, Aug 01 2010
If x=a(n), y=A055997(n+1) and z = x^2+y, then x^4 + y^3 = z^2. - Bruno Berselli, Aug 24 2010
In general, if b(0)=1, b(1)=k and for n > 1, b(n) = 6*b(n-1) - b(n-2), then
for n > 0, b(n) = a(n)*k-a(n-1); e.g.,
for k=2, when b(n) = A038725(n), 2 = 1*2 - 0, 11 = 6*2 - 1, 64 = 35*2 - 6, 373 = 204*2 - 35;
for k=3, when b(n) = A001541(n), 3 = 1*3 - 0, 17 = 6*3 - 1; 99 = 35*3 - 6; 577 = 204*3 - 35;
for k=4, when b(n) = A038723(n), 4 = 1*4 - 0, 23 = 6*4 - 1; 134 = 35*4 - 6; 781 = 204*4 - 35;
for k=5, when b(n) = A001653(n), 5 = 1*5 - 0, 29 = 6*5 - 1; 169 = 35*5 - 6; 985 = 204*5 - 35.
See also A002315, A054488, A038761, A054489, A054490.
- Charlie Marion, Dec 08 2010
See a Wolfdieter Lang comment on A001653 on a sequence of (u,v) values for Pythagorean triples (x,y,z) with x=|u^2-v^2|, y=2*u*v and z=u^2+v^2, with u odd and v even, generated from (u(0)=1,v(0)=2), the triple (3,4,5), by a substitution rule given there. The present a(n) appears there as b(n). The corresponding generated triangles have catheti differing by one length unit. - Wolfdieter Lang, Mar 06 2012
a(n)*a(n+2k) + a(k)^2 and a(n)*a(n+2k+1) + a(k)*a(k+1) are triangular numbers. Generalizes description of sequence. - Charlie Marion, Dec 03 2012
a(n)*a(n+2k) + a(k)^2 is the triangular square A001110(n+k). a(n)*a(n+2k+1) + a(k)*a(k+1) is the triangular oblong A029549(n+k). - Charlie Marion, Dec 05 2012
From Richard R. Forberg, Aug 30 2013: (Start)
The squares of a(n) are the result of applying triangular arithmetic to the squares, using A001333 as the "guide" on what integers to square, as follows:
a(2n)^2 = A001333(2n)^2 * (A001333(2n)^2 - 1)/2;
a(2n+1)^2 = A001333(2n+1)^2 * (A001333(2n+1)^2 + 1)/2. (End)
For n >= 1, a(n) equals the number of 01-avoiding words of length n-1 on alphabet {0,1,...,5}. - Milan Janjic, Jan 25 2015
Panda and Rout call these "balancing numbers" and note that the period of the sequence modulo a prime p is the same as that modulo p^2 when p = 13, 31, 1546463. But these are precisely the p in A238736 such that p^2 divides A000129(p - (2/p)), where (2/p) is a Jacobi symbol. In light of the above observation by Franklin T. Adams-Watters that the present sequence is one half the bisection of the Pell numbers, i.e., a(n) = A000129(2*n)/2, it follows immediately that modulo a fixed prime p, or any power thereof, the period of a(n) is half that of A000129(n). - John Blythe Dobson, Mar 06 2015
The triangular number = square number identity Tri((T(n, 3) - 1)/2) = S(n-1, 6)^2 with Tri, T, and S given in A000217, A053120 and A049310, is the special case k = 1 of the k-family of identities Tri((T(n, 2*k+1) - 1)/2) = Tri(k)*S(n-1, 2*(2*k+1))^2, k >= 0, n >= 0, with S(-1, x) = 0. For k=2 see A108741(n) for S(n-1, 10)^2. This identity boils down to the identities S(n-1, 2*x)^2 = (T(2*n, x) - 1)/(2*(x^2-1)) and 2*T(n, x)^2 - 1 = T(2*n, x) with x = 2*k+1. - Wolfdieter Lang, Feb 01 2016
a(2)=6 is perfect. For n=2*k, k > 0, k not equal to 1, a(n) is a multiple of a(2) and since every multiple (beyond 1) of a perfect number is abundant, then a(n) is abundant. sigma(a(4)) = 504 > 408 = 2*a(4). For n=2*k+1, k > 0, a(n) mod 10 = A000012(n), so a(n) is odd. If a(n) is a prime number, it is deficient; otherwise a(n) has one or two distinct prime factors and is therefore deficient again. So for n=2k+1, k > 0, a(n) is deficient. sigma(a(5)) = 1260 < 2378 = 2*a(5). - Muniru A Asiru, Apr 14 2016
Behera & Panda call these the balancing numbers, and A001541 are the balancers. - Michel Marcus, Nov 07 2017
In general, a second-order linear recurrence with constant coefficients having a signature of (c,d) will be duplicated by a third-order recurrence having a signature of (x,c^2-c*x+d,-d*x+c*d). The formulas of Olivares and Bouhamida in the formula section which have signatures of (7,-7,1) and (5,5,-1), respectively, are specific instances of this general rule for x = 7 and x = 5. - Gary Detlefs, Jan 29 2021
Note that 6 is the largest triangular number in the sequence, because it is proved that 8 and 9 are the largest perfect powers which are consecutive (Catalan's conjecture). 0 and 1 are also in the sequence because they are also perfect powers and 0*1/2 = 0^2 and 8*9/2 = (2*3)^2. - Metin Sariyar, Jul 15 2021

Examples

			G.f. = x + 6*x^2 + 35*x^3 + 204*x^4 + 1189*x^5 + 6930*x^6 + 40391*x^7 + ...
6 is in the sequence since 6^2 = 36 is a triangular number: 36 = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8. - _Michael B. Porter_, Jul 02 2016

References

  • Julio R. Bastida, Quadratic properties of a linearly recurrent sequence. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 163--166, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561042 (81e:10009) - From N. J. A. Sloane, May 30 2012
  • A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, pp. 193, 197.
  • D. M. Burton, The History of Mathematics, McGraw Hill, (1991), p. 213.
  • L. E. Dickson, History of the Theory of Numbers. Carnegie Institute Public. 256, Washington, DC, Vol. 1, 1919; Vol. 2, 1920; Vol. 3, 1923, see vol. 2, p. 10.
  • P. Franklin, E. F. Beckenbach, H. S. M Coxeter, N. H. McCoy, K. Menger, and J. L. Synge, Rings And Ideals, No 8, The Carus Mathematical Monographs, The Mathematical Association of America, (1967), pp. 144-146.
  • A. Patra, G. K. Panda, and T. Khemaratchatakumthorn. "Exact divisibility by powers of the balancing and Lucas-balancing numbers." Fibonacci Quart., 59:1 (2021), 57-64; see B(n).
  • 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 257-258.
  • P.-F. Teilhet, Query 2376, L'Intermédiaire des Mathématiciens, 11 (1904), 138-139. - N. J. A. Sloane, Mar 08 2022

Links

Crossrefs

Cf. A000217, A000290, A001108, A001542, A001653, A001850, A002315, A002965, A278310.
Chebyshev sequence U(n, m): A000027 (m=1), A001353 (m=2), this sequence (m=3), A001090 (m=4), A004189 (m=5), A004191 (m=6), A007655 (m=7), A077412 (m=8), A049660 (m=9), A075843 (m=10), A077421 (m=11), A077423 (m=12), A097309 (m=13), A097311 (m=14), A097313 (m=15), A029548 (m=16), A029547 (m=17), A144128 (m=18), A078987 (m=19), A097316 (m=33).
Cf. A323182.

Programs

  • GAP
    a:=[0,1];; for n in [3..25] do a[n]:=6*a[n-1]-a[n-2]; od; a; # Muniru A Asiru, Dec 18 2018
  • Haskell
    a001109 n = a001109_list !! n :: Integer
a001109_list = 0 : 1 : zipWith (-)
   (map (* 6) $ tail a001109_list) a001109_list
-- Reinhard Zumkeller, Dec 17 2011
  • Magma
    [n le 2 select n-1 else 6*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Jul 25 2015
  • Maple
    a[0]:=1: a[1]:=6: for n from 2 to 26 do a[n]:=6*a[n-1]-a[n-2] od: seq(a[n],n=0..26); # Emeric Deutsch
with (combinat):seq(fibonacci(2*n,2)/2, n=0..20); # Zerinvary Lajos, Apr 20 2008
  • Mathematica
    Transpose[NestList[Flatten[{Rest[#],ListCorrelate[{-1,6},#]}]&, {0,1}, 30]][[1]]  (* Harvey P. Dale, Mar 23 2011 *)
CoefficientList[Series[x/(1-6x+x^2),{x,0,30}],x]  (* Harvey P. Dale, Mar 23 2011 *)
LinearRecurrence[{6, -1}, {0, 1}, 50] (* Vladimir Joseph Stephan Orlovsky, Feb 12 2012 *)
a[ n_]:= ChebyshevU[n-1, 3]; (* Michael Somos, Sep 02 2012 *)
Table[Fibonacci[2n, 2]/2, {n, 0, 20}] (* Vladimir Reshetnikov, Sep 16 2016 *)
TrigExpand@Table[Sinh[2 n ArcCsch[1]]/(2 Sqrt[2]), {n, 0, 10}] (* Federico Provvedi, Feb 01 2021 *)
  • PARI
    {a(n) = imag((3 + quadgen(32))^n)}; /* Michael Somos, Apr 07 2003 */
  • PARI
    {a(n) = subst( poltchebi( abs(n+1)) - 3 * poltchebi( abs(n)), x, 3) / 8}; /* Michael Somos, Apr 07 2003 */
  • PARI
    {a(n) = polchebyshev( n-1, 2, 3)}; /* Michael Somos, Sep 02 2012 */
  • PARI
    is(n)=ispolygonal(n^2,3) \\ Charles R Greathouse IV, Nov 03 2016
  • Sage
    [lucas_number1(n,6,1) for n in range(27)] # Zerinvary Lajos, Jun 25 2008
  • Sage
    [chebyshev_U(n-1,3) for n in (0..20)] # G. C. Greubel, Dec 23 2019

Formula

G.f.: x / (1 - 6*x + x^2). - Simon Plouffe in his 1992 dissertation.
a(n) = S(n-1, 6) = U(n-1, 3) with U(n, x) Chebyshev's polynomials of the second kind. S(-1, x) := 0. Cf. triangle A049310 for S(n, x).
a(n) = sqrt(A001110(n)).
a(n) = A001542(n)/2.
a(n) = sqrt((A001541(n)^2-1)/8) (cf. Richardson comment).
a(n) = 3*a(n-1) + sqrt(8*a(n-1)^2+1). - R. J. Mathar, Oct 09 2000
a(n) = A000129(n)*A001333(n) = A000129(n)*(A000129(n)+A000129(n-1)) = ceiling(A001108(n)/sqrt(2)). - Henry Bottomley, Apr 19 2000
a(n) ~ (1/8)*sqrt(2)*(sqrt(2) + 1)^(2*n). - Joe Keane (jgk(AT)jgk.org), May 15 2002
Limit_{n->oo} a(n)/a(n-1) = 3 + 2*sqrt(2). - Gregory V. Richardson, Oct 05 2002
a(n) = ((3 + 2*sqrt(2))^n - (3 - 2*sqrt(2))^n) / (4*sqrt(2)). - Gregory V. Richardson, Oct 13 2002. Corrected for offset 0, and rewritten. - Wolfdieter Lang, Feb 10 2015
a(2*n) = a(n)*A003499(n). 4*a(n) = A005319(n). - Mario Catalani (mario.catalani(AT)unito.it), Mar 21 2003
a(n) = floor((3+2*sqrt(2))^n/(4*sqrt(2))). - Lekraj Beedassy, Apr 23 2003
a(-n) = -a(n). - Michael Somos, Apr 07 2003
For n >= 1, a(n) = Sum_{k=0..n-1} A001653(k). - Charlie Marion, Jul 01 2003
For n > 0, 4*a(2*n) = A001653(n)^2 - A001653(n-1)^2. - Charlie Marion, Jul 16 2003
For n > 0, a(n) = Sum_{k = 0..n-1}((2*k+1)*A001652(n-1-k)) + A000217(n). - Charlie Marion, Jul 18 2003
a(2*n+1) = a(n+1)^2 - a(n)^2. - Charlie Marion, Jan 12 2004
a(k)*a(2*n+k) = a(n+k)^2 - a(n)^2; e.g., 204*7997214 = 40391^2 - 35^2. - Charlie Marion, Jan 15 2004
For j < n+1, a(k+j)*a(2*n+k-j) - Sum_{i = 0..j-1} a(2*n-(2*i+1)) = a(n+k)^2 - a(n)^2. - Charlie Marion, Jan 18 2004
From Paul Barry, Feb 06 2004: (Start)
a(n) = A000129(2*n)/2;
a(n) = ((1+sqrt(2))^(2*n) - (1-sqrt(2))^(2*n))*sqrt(2)/8;
a(n) = Sum_{i=0..n} Sum_{j=0..n} A000129(i+j)*n!/(i!*j!*(n-i-j)!)/2. (End)
E.g.f.: exp(3*x)*sinh(2*sqrt(2)*x)/(2*sqrt(2)). - Paul Barry, Apr 21 2004
A053141(n+1) + A055997(n+1) = A001541(n+1) + a(n+1). - Creighton Dement, Sep 16 2004
a(n) = Sum_{k=0..n} binomial(2*n, 2*k+1)*2^(k-1). - Paul Barry, Oct 01 2004
a(n) = A001653(n+1) - A038723(n); (a(n)) = chuseq[J]( 'ii' + 'jj' + .5'kk' + 'ij' - 'ji' + 2.5e ), apart from initial term. - Creighton Dement, Nov 19 2004, modified by Davide Colazingari, Jun 24 2016
a(n+1) = Sum_{k=0..n} A001850(k)*A001850(n-k), self convolution of central Delannoy numbers. - Benoit Cloitre, Sep 28 2005
a(n) = 7*(a(n-1) - a(n-2)) + a(n-3), a(1) = 0, a(2) = 1, a(3) = 6, n > 3. Also a(n) = ( (1 + sqrt(2) )^(2*n) - (1 - sqrt(2) )^(2*n) ) / (4*sqrt(2)). - Antonio Alberto Olivares, Oct 23 2003
a(n) = 5*(a(n-1) + a(n-2)) - a(n-3). - Mohamed Bouhamida, Sep 20 2006
Define f(x,s) = s*x + sqrt((s^2-1)*x^2+1); f(0,s)=0. a(n) = f(a(n-1),3), see second formula. - Marcos Carreira, Dec 27 2006
The perfect median m(n) can be expressed in terms of the Pell numbers P() = A000129() by m(n) = P(n + 2) * (P(n + 2) + P(n + 1)) for n >= 0. - Winston A. Richards (ugu(AT)psu.edu), Jun 11 2007
For k = 0..n, a(2*n-k) - a(k) = 2*a(n-k)*A001541(n). Also, a(2*n+1-k) - a(k) = A002315(n-k)*A001653(n). - Charlie Marion, Jul 18 2007
[A001653(n), a(n)] = [1,4; 1,5]^n * [1,0]. - Gary W. Adamson, Mar 21 2008
a(n) = Sum_{k=0..n-1} 4^k*binomial(n+k,2*k+1). - Paul Barry, Apr 20 2009
a(n+1)^2 - 6*a(n+1)*a(n) + a(n)^2 = 1. - Charlie Marion, Dec 14 2010
a(n) = A002315(m)*A011900(n-m-1) + A001653(m)*A001652(n-m-1) - a(m) = A002315(m)*A053141(n-m-1) + A001653(m)*A046090(n-m-1) + a(m) with m < n; otherwise a(n) = A002315(m)*A053141(m-n) - A001653(m)*A011900(m-n) + a(m) = A002315(m)*A053141(m-n) - A001653(m)*A046090(m-n) - a(m) = (A002315(n) - A001653(n))/2. - Kenneth J Ramsey, Oct 12 2011
16*a(n)^2 + 1 = A056771(n). - James R. Buddenhagen, Dec 09 2011
A010054(A000290(a(n))) = 1. - Reinhard Zumkeller, Dec 17 2011
In general, a(n+k)^2 - A003499(k)*a(n+k)*a(n) + a(n)^2 = a(k)^2. - Charlie Marion, Jan 11 2012
a(n+1) = Sum_{k=0..n} A101950(n,k)*5^k. - Philippe Deléham, Feb 10 2012
PSUM transform of a(n+1) is A053142. PSUMSIGN transform of a(n+1) is A084158. BINOMIAL transform of a(n+1) is A164591. BINOMIAL transform of A086347 is a(n+1). BINOMIAL transform of A057087(n-1). - Michael Somos, May 11 2012
a(n+k) = A001541(k)*a(n) + sqrt(A132592(k)*a(n)^2 + a(k)^2). Generalizes formula dated Oct 09 2000. - Charlie Marion, Nov 27 2012
a(n) + a(n+2*k) = A003499(k)*a(n+k); a(n) + a(n+2*k+1) = A001653(k+1)*A002315(n+k). - Charlie Marion, Nov 29 2012
From Peter Bala, Dec 23 2012: (Start)
Product_{n >= 1} (1 + 1/a(n)) = 1 + sqrt(2).
Product_{n >= 2} (1 - 1/a(n)) = (1/3)*(1 + sqrt(2)). (End)
G.f.: G(0)*x/(2-6*x), where G(k) = 1 + 1/(1 - x*(8*k-9)/( x*(8*k-1) - 3/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 12 2013
G.f.: H(0)*x/2, where H(k) = 1 + 1/( 1 - x*(6-x)/(x*(6-x) + 1/H(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Feb 18 2014
a(n) = (a(n-1)^2 - a(n-3)^2)/a(n-2) + a(n-4) for n > 3. - Patrick J. McNab, Jul 24 2015
a(n-k)*a(n+k) + a(k)^2 = a(n)^2, a(n+k) + a(n-k) = A003499(k)*a(n), for n >= k >= 0. - Alexander Samokrutov, Sep 30 2015
Dirichlet g.f.: (PolyLog(s,3+2*sqrt(2)) - PolyLog(s,3-2*sqrt(2)))/(4*sqrt(2)). - Ilya Gutkovskiy, Jun 27 2016
4*a(n)^2 - 1 = A278310(n) for n > 0. - Bruno Berselli, Nov 24 2016
From Klaus Purath, Jan 18 2020: (Start)
a(n) = (a(n-3) + a(n+3))/198.
a(n) = Sum_{i=1..n} A001653(i), n>=1.
a(n) = sinh( 2 * n * arccsch(1) ) / ( 2 * sqrt(2) ). - Federico Provvedi, Feb 01 2021
(End)
a(n) = A002965(2*n)*A002965(2*n+1). - Jon E. Schoenfield, Jan 08 2022
a(n) = A002965(4*n)/2. - Gerry Martens, Jul 14 2023
a(n) = Sum_{k = 0..n-1} (-1)^(n+k+1)*binomial(n+k, 2*k+1)*8^k. - Peter Bala, Jul 17 2023

Extensions

Additional comments from Wolfdieter Lang, Feb 10 2000
Duplication of a formula removed by Wolfdieter Lang, Feb 10 2015

A026729 Square array of binomial coefficients T(n,k) = binomial(n,k), n >= 0, k >= 0, read by downward antidiagonals.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 2, 1, 0, 0, 1, 3, 1, 0, 0, 0, 3, 4, 1, 0, 0, 0, 1, 6, 5, 1, 0, 0, 0, 0, 4, 10, 6, 1, 0, 0, 0, 0, 1, 10, 15, 7, 1, 0, 0, 0, 0, 0, 5, 20, 21, 8, 1, 0, 0, 0, 0, 0, 1, 15, 35, 28, 9, 1, 0, 0, 0, 0, 0, 0, 6, 35, 56, 36, 10, 1, 0, 0, 0, 0, 0, 0, 1, 21, 70, 84, 45, 11, 1, 0, 0, 0, 0
Offset: 0

Views

Author

N. J. A. Sloane, Jan 19 2003

Keywords

Comments

The signed triangular matrix T(n,k)*(-1)^(n-k) is the inverse matrix of the triangular Catalan convolution matrix A106566(n,k), n=k>=0, with A106566(n,k) = 0 if nPhilippe Deléham, Aug 01 2005
As a number triangle: unsigned version of A109466. - Philippe Deléham, Oct 26 2008
A063967*A130595 as infinite lower triangular matrices. - Philippe Deléham, Dec 11 2008
Modulo 2, this sequence becomes A106344. - Philippe Deléham, Dec 18 2008
Let {a_(k,i)}, k>=1, i=0,...,k, be the k-th antidiagonal of the array. Then s_k(n) = Sum_{i=0..k}a_(k,i)* binomial(n,k) is the n-th element of the k-th column of A111808. For example, s_1(n) = binomial(n,1) = n is the first column of A111808 for n>1, s_2(n) = binomial(n,1) + binomial(n,2) is the second column of A111808 for n>1, etc. Therefore, in cases k=3,4,5,6,7,8, s_k(n) is A005581(n), A005712(n), A000574(n), A005714(n), A005715(n), A005716(n), respectively. Besides, s_k(n+5) = A064054(n). - Vladimir Shevelev and Peter J. C. Moses, Jun 22 2012
As a triangle, T(n,k) = binomial(k,n-k). - Peter Bala, Nov 27 2015
For all n >= 0, k >= 0, the k-th homology group of the n-torus H_k(T^n) is the free abelian group of rank T(n,k) = binomial(n,k). See the Math Stack Exchange link below. - Jianing Song, Mar 13 2023

Examples

			Array begins
  1 0 0 0 0 0 ...
  1 1 0 0 0 0 ...
  1 2 1 0 0 0 ...
  1 3 3 1 0 0 ...
  1 4 6 4 1 0 ...
As a triangle, this begins
  1
  0 1
  0 1 1
  0 0 2 1
  0 0 1 3 1
  0 0 0 3 4 1
  0 0 0 1 6 5 1
  ...
Production array is
  0    1
  0    1   1
  0   -1   1   1
  0    2  -1   1  1
  0   -5   2  -1  1  1
  0   14  -5   2 -1  1  1
  0  -42  14  -5  2 -1  1  1
  0  132 -42  14 -5  2 -1  1  1
  0 -429 132 -42 14 -5  2 -1  1  1
  ... (Cf. A000108)

Links

Crossrefs

The official entry for Pascal's triangle is A007318. See also A052553 (the same array read by upward antidiagonals).
Cf. A030528 (subtriangle for 1<=k<=n).
Cf. A109466, A102426.

Programs

  • GAP
    nmax:=15;; T:=List([0..nmax],n->List([0..nmax],k->Binomial(n,k)));;
b:=List([2..nmax],n->OrderedPartitions(n,2));;
a:=Flat(List([1..Length(b)],i->List([1..Length(b[i])],j->T[b[i][j][1]][b[i][j][2]]))); # Muniru A Asiru, Jul 17 2018
  • Magma
    /* As triangle: */ [[Binomial(k, n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Nov 29 2015
  • Maple
    seq(seq(binomial(k,n-k),k=0..n),n=0..12); # Peter Luschny, May 31 2014
  • Mathematica
    Table[Binomial[k, n - k], {n, 0, 12}, {k, 0, n}] // Flatten (* Michael De Vlieger, Nov 28 2015 *)

Formula

As a number triangle, this is defined by T(n,0) = 0^n, T(0,k) = 0^k, T(n,k) = T(n-1,k-1) + Sum_{j, j>=0} (-1)^j*T(n-1,k+j)*A000108(j) for n>0 and k>0. - Philippe Deléham, Nov 07 2005
As a triangle read by rows, it is [0, 1, -1, 0, 0, 0, 0, 0, 0, ...] DELTA [1, 0, 0, 0, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 22 2006
As a number triangle, this is defined by T(n, k) = Sum_{i=0..n} (-1)^(n+i)*binomial(n, i)*binomial(i+k, i-k) and is the Riordan array ( 1, x*(1+x) ). The row sums of this triangle are F(n+1). - Paul Barry, Jun 21 2004
Sum_{k=0..n} x^k*T(n,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 n=0,1,2,3,4,5,6,7,8,9,10. - Philippe Deléham, Oct 16 2006
T(n,k) = A109466(n,k)*(-1)^(n-k). - Philippe Deléham, Dec 11 2008
G.f. for the triangular interpretation: -1/(-1+x*y+x^2*y). - R. J. Mathar, Aug 11 2015
For T(0,0) = 0, the triangle below has the o.g.f. G(x,t) = [t*x(1+x)]/[1-t*x(1+x)]. See A109466 for a signed version and inverse, A030528 for reverse and A102426 for a shifted version. - Tom Copeland, Jan 19 2016

A057088 Scaled Chebyshev U-polynomials evaluated at i*sqrt(5)/2. Generalized Fibonacci sequence.

Original entry on oeis.org

1, 5, 30, 175, 1025, 6000, 35125, 205625, 1203750, 7046875, 41253125, 241500000, 1413765625, 8276328125, 48450468750, 283633984375, 1660422265625, 9720281250000, 56903517578125, 333118994140625, 1950112558593750, 11416157763671875, 66831351611328125, 391237546875000000
Offset: 0

Views

Author

Wolfdieter Lang, Aug 11 2000

Keywords

Comments

a(n) gives the length of the word obtained after n steps with the substitution rule 0->11111, 1->111110, starting from 0. The number of 1's and 0's of this word is 5*a(n-1) and 5*a(n-2), resp.
a(n) / a(n-1) converges to (5 + (3 * sqrt(5))) / 2 as n approaches infinity. (5 + (3 * sqrt(5))) / 2 can also be written as phi^2 + (2 * phi), phi^3 + phi, phi + sqrt(5) + 2, (3 * phi) + 1, (3 * phi^2) - 2, phi^4 - 1 and (5 + (3 * (L(n) / F(n)))) / 2, where L(n) is the n-th Lucas number and F(n) is the n-th Fibonacci number as n approaches infinity. - Ross La Haye, Aug 18 2003, on another version
Pisano period lengths: 1, 3, 3, 6, 1, 3, 24, 12, 9, 3, 10, 6, 56, 24, 3, 24,288, 9, 18, 6, ... - R. J. Mathar, Aug 10 2012

Links

Crossrefs

Cf. A001076, A006190, A007482, A015520, A015521, A015523, A015524, A015525, A015528, A015529, A015530, A015531, A015532, A015533, A015534, A015535, A015536, A015537, A015443, A015447, A030195, A053404, A057087, A083858, A085939, A090017, A091914, A099012, A180222, A180226.

Programs

  • Magma
    I:=[1, 5]; [n le 2 select I[n] else 5*Self(n-1) + 5*Self(n-2): n in [0..30]]; // G. C. Greubel, Jan 16 2018
  • Maple
    a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=5*a[n-1]+5*a[n-2]od: seq(a[n], n=1..33); # Zerinvary Lajos, Dec 14 2008
  • Mathematica
    LinearRecurrence[{5,5}, {1,5}, 30] (* G. C. Greubel, Jan 16 2018 *)
  • PARI
    x='x+O('x^30); Vec(1/(1 - 5*x - 5*x^2)) \\ G. C. Greubel, Jan 16 2018
  • Sage
    [lucas_number1(n,5,-5) for n in range(1, 22)] # Zerinvary Lajos, Apr 24 2009

Formula

a(n) = 5*(a(n-1) + a(n-2)), a(-1)=0, a(0)=1.
a(n) = S(n, i*sqrt(5))*(-i*sqrt(5))^n with S(n, x) := U(n, x/2), Chebyshev's polynomials of the 2nd kind, A049310.
G.f.: 1/(1 - 5*x - 5*x^2).
a(n) = (1/3)*Sum_{k=0..n} binomial(n, k)*Fibonacci(k)*3^k. - Benoit Cloitre, Oct 25 2003
a(n) = ((5 + 3*sqrt(5))/2)^n(1/2 + sqrt(5)/6) + (1/2 - sqrt(5)/6)((5 - 3*sqrt(5))/2)^n. - Paul Barry, Sep 22 2004
(a(n)) appears to be given by the floretion - 0.75'i - 0.5'j + 'k - 0.75i' + 0.5j' + 0.5k' + 1.75'ii' - 1.25'jj' + 1.75'kk' - 'ij' - 0.5'ji' - 0.75'jk' - 0.75'kj' - 1.25e ("jes"). - Creighton Dement, Nov 28 2004
a(n) = Sum_{k=0..n} 4^k*A063967(n,k). - Philippe Deléham, Nov 03 2006
G.f.: G(0)/(2-5*x), where G(k)= 1 + 1/(1 - x*(9*k-5)/(x*(9*k+4) - 2/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 17 2013
From Ehren Metcalfe, Nov 18 2017: (Start)
With F(n) = A000045(n), L(n) = A000032(n), beta = (1-sqrt(5))/2:
a(2*n-1) = 5^n*F(4*n)/3 = (5^(n-1/2)*L(4*n) - 2*5^(n-1/2)*beta^(4*n))/3.
a(2*n) = 5^n*L(4*n+2)/3 = (5^(n+1/2)*F(4*n+2) + 2*5^n*beta^(4*n+2))/3.
a(n) = round 5^((n+1)/2)*F(2*(n+1))/3.
a(n) = round 5^(n/2)*L(2*(n+1))/3. (End)

A086347 On a 3 X 3 board, number of n-move routes of chess king ending in a given side square.

Original entry on oeis.org

1, 5, 24, 116, 560, 2704, 13056, 63040, 304384, 1469696, 7096320, 34264064, 165441536, 798822400, 3857055744, 18623512576, 89922273280, 434183143424, 2096421666816, 10122419240960, 48875363631104, 235991131488256, 1139465980477440, 5501828447862784
Offset: 0

Views

Author

Zak Seidov, Jul 17 2003

Keywords

Comments

Number of aa-avoiding words of length n on alphabet {a,b,c,d,e}. - Tanya Khovanova, Jan 11 2007
Binomial transform of A164589 and second binomial transform of A096886. [Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]
From Johannes W. Meijer, Aug 01 2010: (Start)
The a(n) represent the number of n-move paths of a chess king on a 3 X 3 board that end or start in a given side square m (m = 2, 4, 6, 8).
Inverse binomial transform of A001109 (without the leading 0).
(End)
Number of independent vertex subsets of the graph obtained by attaching two pendant edges to each vertex of the path graph P_n (see A235116). Example: a(1)=5; indeed, P_1 is the one-vertex graph and after attaching two pendant vertices we obtain the path graph ABC; the independent vertex subsets are: empty, {A}, {B}, {C}, and {A,C}.
Number of simple paths from corner to diagonally opposite corner on a 2 X n grid with king moves allowed. - Andrew Howroyd, Nov 06 2019
Number of 4-compositions of n+1 restricted to parts 1 and 2 (and allowed zeros); see Hopkins & Ouvry reference. - Brian Hopkins, Aug 16 2020

Examples

			a(3) = 116 = 5^3 - 9 (aaa, aab, aac, aad, aae, baa, caa, daa, eaa). [Al Hakanson (hawkuu(AT)gmail.com), Aug 17 2009]

Links

Crossrefs

Row 2 of A329118.
Row sums of A235113.
Cf. A086346, A086348.
Cf. A028859.
Cf. A126473. - Johannes W. Meijer, Aug 01 2010

Programs

  • Maple
    with(LinearAlgebra): nmax:=19; m:=2; A[5]:= [1,1,1,1,0,1,1,1,1]: A:=Matrix([[0,1,0,1,1,0,0,0,0],[1,0,1,1,1,1,0,0,0],[0,1,0,0,1,1,0,0,0],[1,1,0,0,1,0,1,1,0],A[5],[0,1,1,0,1,0,0,1,1],[0,0,0,1,1,0,0,1,0],[0,0,0,1,1,1,1,0,1],[0,0,0,0,1,1,0,1,0]]): for n from 0 to nmax do B(n):=A^n: a(n):= add(B(n)[m,k],k=1..9): od: seq(a(n), n=0..nmax); # Johannes W. Meijer, Aug 01 2010
# second Maple program:
a:= n-> (<<0|1>, <4|4>>^n. <<1, 5>>)[1,1]:
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 12 2022
  • Mathematica
    Table[(Sqrt[2]/32)((2+Sqrt[8])^(n+2)-(2-Sqrt[8])^(n+2)), {n, 0, 19}]

Formula

a(n) = (sqrt(2)/32)*((2+sqrt(8))^(n+2)-(2-sqrt(8))^(n+2)).
From Ralf Stephan, Feb 01 2004: (Start)
G.f.: (1+x)/(1-4*x-4*x^2).
a(n) = A057087(n) + A057087(n-1). (End)
a(n) = 4*a(n-1) + 4*a(n-2). - Tanya Khovanova, Jan 11 2007
Limit_{k->oo} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2). - Johannes W. Meijer, Aug 01 2010
E.g.f.: exp(2*x)*(4*cosh(2*sqrt(2)*x) + 3*sqrt(2)*sinh(2*sqrt(2)*x))/4. - Stefano Spezia, Mar 17 2025

Extensions

Offset changed and edited by Johannes W. Meijer, Jul 15 2010

A214992 Power ceiling-floor sequence of (golden ratio)^4.

Original entry on oeis.org

7, 47, 323, 2213, 15169, 103969, 712615, 4884335, 33477731, 229459781, 1572740737, 10779725377, 73885336903, 506417632943, 3471038093699, 23790849022949, 163064905066945, 1117663486445665, 7660579500052711
Offset: 0

Views

Author

Clark Kimberling, Nov 08 2012, Jan 24 2013

Keywords

Comments

Let f = floor and c = ceiling. For x > 1, define four sequences as functions of x, as follows:
p1(0) = f(x), p1(n) = f(x*p1(n-1));
p2(0) = f(x), p2(n) = c(x*p2(n-1)) if n is odd and p2(n) = f(x*p1(n-1)) if n is even;
p3(0) = c(x), p3(n) = f(x*p3(n-1)) if n is odd and p3(n) = c(x*p3(n-1)) if n is even;
p4(0) = c(x), p4(n) = c(x*p4(n-1)).
The present sequence is given by a(n) = p3(n).
Following the terminology at A214986, call the four sequences power floor, power floor-ceiling, power ceiling-floor, and power ceiling sequences. In the table below, a sequence is identified with an A-numbered sequence if they appear to agree except possibly for initial terms. Notation: S(t)=sqrt(t), r = (1+S(5))/2 = golden ratio, and Limit = limit of p3(n)/p2(n).
x ......p1..... p2..... p3..... p4.......Limit
r.......A000045 A000045 A000045 A000045..r
r^2.....A001519 A001654 A061646 A001906..-1+S(5)
r^3.....A024551 A001076 A015448 A049652..-1+S(5)
r^4.....A049685 A157335 A214992 A004187..-19+9*S(5)
r^5.....A214993 A049666 A015457 A214994...(-9+5*S(5))/2
r^6.....A007805 A156085 A214995 A049660..-151+68*S(5)
1+S(2)..A024537 A000129 A001333 A048739..S(2)
2+S(2)..A007052 A214996 A214997 A007070..(1+S(2))/2
1+S(3)..A057960 A002605 A028859 A077846..(1+S(3))/2
2+S(3)..A001835 A109437 A214998 A001353..-4+3*S(3)
S(5)....A214999 A215091 A218982 A218983..1.26879683...
2+S(5)..A024551 A001076 A015448 A049652..-1+S(5)
2+S(6)..A218984 A090017 A123347 A218985..S(3/2)
2+S(7)..A218986 A015530 A126473 A218987..(1+S(7))/3
2+S(8)..A218988 A057087 A086347 A218989..(1+S(2))/2
3+S(8)..A001653 A084158 A218990 A001109..-13+10*S(2)
3+S(10).A218991 A005668 A015451 A218992..-2+S(10)
...
Properties of p1, p2, p3, p4:
(1) If x > 2, the terms of p2 and p3 interlace: p2(0) < p3(0) < p2(1) < p3(1) < p2(2) < p3(2)... Also, p1(n) <= p2(n) <= p3(n) <= p4(n) <= p1(n+1) for all x>0 and n>=0.
(2) If x > 2, the limits L(x) = limit(p/x^n) exist for the four functions p(x), and L1(x) <= L2(x) <= L3(x) <= L4 (x). See the Mathematica programs for plots of the four functions; one of them also occurs in the Odlyzko and Wilf article, along with a discussion of the special case x = 3/2.
(3) Suppose that x = u + sqrt(v) where v is a nonsquare positive integer. If u = f(x) or u = c(x), then p1, p2, p3, p4 are linear recurrence sequences. Is this true for sequences p1, p2, p3, p4 obtained from x = (u + sqrt(v))^q for every positive integer q?
(4) Suppose that x is a Pisot-Vijayaraghavan number. Must p1, p2, p3, p4 then be linearly recurrent? If x is also a quadratic irrational b + c*sqrt(d), must the four limits L(x) be in the field Q(sqrt(d))?
(5) The Odlyzko and Wilf article (page 239) raises three interesting questions about the power ceiling function; it appears that they remain open.

Examples

			a(0) = ceiling(r) = 7, where r = ((1+sqrt(5))/2)^4 = 6.8...; a(1) = floor(7*r) = 47; a(2) = ceiling(47) = 323.

Links

Crossrefs

Cf. A001622, A214986, A049685, A157335, A004187.

Programs

  • Mathematica
    (* Program 1.  A214992 and related sequences *)
x = GoldenRatio^4; z = 30; (* z = # terms in sequences *)
z1 = 100; (* z1 = # digits in approximations *)
f[x_] := Floor[x]; c[x_] := Ceiling[x];
p1[0] = f[x]; p2[0] = f[x]; p3[0] = c[x]; p4[0] = c[x];
p1[n_] := f[x*p1[n - 1]]
p2[n_] := If[Mod[n, 2] == 1, c[x*p2[n - 1]], f[x*p2[n - 1]]]
p3[n_] := If[Mod[n, 2] == 1, f[x*p3[n - 1]], c[x*p3[n - 1]]]
p4[n_] := c[x*p4[n - 1]]
Table[p1[n], {n, 0, z}]  (* A049685 *)
Table[p2[n], {n, 0, z}]  (* A157335 *)
Table[p3[n], {n, 0, z}]  (* A214992 *)
Table[p4[n], {n, 0, z}]  (* A004187 *)
Table[p4[n] - p1[n], {n, 0, z}]  (* A004187 *)
Table[p3[n] - p2[n], {n, 0, z}]  (* A098305 *)
(* Program 2.  Plot of power floor and power ceiling functions, p1(x) and p4(x) *)
f[x_] := f[x] = Floor[x]; c[x_] := c[x] = Ceiling[x];
p1[x_, 0] := f[x]; p1[x_, n_] := f[x*p1[x, n - 1]];
p4[x_, 0] := c[x]; p4[x_, n_] := c[x*p4[x, n - 1]];
Plot[Evaluate[{p1[x, 10]/x^10, p4[x, 10]/x^10}], {x, 2, 3}, PlotRange -> {0, 4}]
(* Program 3. Plot of power floor-ceiling and power ceiling-floor functions, p2(x) and p3(x) *)
f[x_] := f[x] = Floor[x]; c[x_] := c[x] = Ceiling[x];
p2[x_, 0] := f[x]; p3[x_, 0] := c[x];
p2[x_, n_] := If[Mod[n, 2] == 1, c[x*p2[x, n - 1]], f[x*p2[x, n - 1]]]
p3[x_, n_] := If[Mod[n, 2] == 1, f[x*p3[x, n - 1]], c[x*p3[x, n - 1]]]
Plot[Evaluate[{p2[x, 10]/x^10, p3[x, 10]/x^10}], {x, 2, 3}, PlotRange -> {0, 4}]

Formula

a(n) = floor(r*a(n-1)) if n is odd and a(n) = ceiling(r*a(n-1)) if n is even, where a(0) = ceiling(r), r = (golden ratio)^4 = (7 + sqrt(5))/2.
a(n) = 6*a(n-1) + 6*a(n-2) - a(n-3).
G.f.: (7 + 5*x - x^2)/((1 + x)*(1 - 7*x + x^2)).
a(n) = (10*(-2)^n+(10+3*sqrt(5))*(7-3*sqrt(5))^(n+2)+(10-3*sqrt(5))*(7+3*sqrt(5))^(n+2))/(90*2^n). - Bruno Berselli, Nov 14 2012
a(n) = 7*A157335(n) + 5*A157335(n-1) - A157335(n-2). - R. J. Mathar, Feb 05 2020
E.g.f.: exp(-x)*(5 + 2*exp(9*x/2)*(155*cosh(3*sqrt(5)*x/2) + 69*sqrt(5)*sinh(3*sqrt(5)*x/2)))/45. - Stefano Spezia, Oct 28 2024

A063967 Triangle read by rows, T(n,k) = T(n-1,k) + T(n-2,k) + T(n-1,k-1) + T(n-2,k-1) and T(0,0) = 1.

Original entry on oeis.org

1, 1, 1, 2, 3, 1, 3, 7, 5, 1, 5, 15, 16, 7, 1, 8, 30, 43, 29, 9, 1, 13, 58, 104, 95, 46, 11, 1, 21, 109, 235, 271, 179, 67, 13, 1, 34, 201, 506, 705, 591, 303, 92, 15, 1, 55, 365, 1051, 1717, 1746, 1140, 475, 121, 17, 1, 89, 655, 2123, 3979, 4759, 3780, 2010, 703, 154, 19, 1
Offset: 0

Views

Author

Henry Bottomley, Sep 05 2001

Keywords

Examples

			T(3,1) = T(2,1) + T(1,1) + T(2,0) + T(1,0) = 3 + 1 + 2 + 1 = 7.
Triangle begins:
   1,
   1,   1,
   2,   3,   1,
   3,   7,   5,   1,
   5,  15,  16,   7,   1,
   8,  30,  43,  29,   9,   1,
  13,  58, 104,  95,  46,  11,  1,
  21, 109, 235, 271, 179,  67, 13,  1,
  34, 201, 506, 705, 591, 303, 92, 15, 1

Links

Crossrefs

Row sums are A002605.
Columns include: A000045(n+1), A023610(n-1).
Main diagonal: A000012, a(n, n-1) = A005408(n-1).
Matrix inverse: A091698, matrix square: A091700.
Cf. A321620.
Sum_{k=0..n} x^k*T(n,k) is (-1)^n*A057086(n) (x=-11), (-1)^n*A057085(n+1) (x=-10), (-1)^n*A057084(n) (x=-9), (-1)^n*A030240(n) (x=-8), (-1)^n*A030192(n) (x=-7), (-1)^n*A030191(n) (x=-6), (-1)^n*A001787(n+1) (x=-5), A000748(n) (x=-4), A108520(n) (x=-3), A049347(n) (x=-2), A000007(n) (x=-1), A000045(n) (x=0), A002605(n) (x=1), A030195(n+1) (x=2), A057087(n) (x=3), A057088(n) (x=4), A057089(n) (x=5), A057090(n) (x=6), A057091(n) (x=7), A057092(n) (x=8), A057093(n) (x=9). - Philippe Deléham, Nov 03 2006

Programs

  • Haskell
    a063967_tabl = [1] : [1,1] : f [1] [1,1] where
   f us vs = ws : f vs ws where
     ws = zipWith (+) ([0] ++ us ++ [0]) $
          zipWith (+) (us ++ [0,0]) $ zipWith (+) ([0] ++ vs) (vs ++ [0])
-- Reinhard Zumkeller, Apr 17 2013
  • Mathematica
    T[n_, k_] := Sum[Binomial[j, n - j]*Binomial[j, k], {j, 0, n}]; Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Oct 11 2017, after Paul Barry *)
(* Function RiordanSquare defined in A321620. *)
RiordanSquare[1/(1 - x - x^2), 11] // Flatten (* Peter Luschny, Nov 27 2018 *)

Formula

G.f.: 1/(1-x*(1+x)*(1+y)). - Vladeta Jovovic, Oct 11 2003
Riordan array (1/(1-x-x^2), x(1+x)/(1-x-x^2)). The inverse of the signed version (1/(1+x-x^2),x(1-x)/(1+x-x^2)) is abs(A091698). - Paul Barry, Jun 10 2005
T(n, k) = Sum_{j=0..n} C(j, n-j)C(j, k). - Paul Barry, Nov 09 2005
Diagonal sums are A002478. - Paul Barry, Nov 09 2005
A026729*A007318 as infinite lower triangular matrices. - Philippe Deléham, Dec 11 2008
Central coefficients T(2*n,n) are A137644. - Paul Barry, Apr 15 2010
Product of Riordan arrays (1, x(1+x))*(1/(1-x), x/(1-x)), that is, A026729*A007318. - Paul Barry, Mar 14 2011
Triangle T(n,k), read by rows, given by (1,1,-1,0,0,0,0,0,0,0,...) DELTA (1,0,0,0,0,0,0,0,0,0,...) where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 12 2011

A057089 Scaled Chebyshev U-polynomials evaluated at i*sqrt(6)/2. Generalized Fibonacci sequence.

Original entry on oeis.org

1, 6, 42, 288, 1980, 13608, 93528, 642816, 4418064, 30365280, 208700064, 1434392064, 9858552768, 67757668992, 465697330560, 3200729997312, 21998563967232, 151195763787264, 1039165966526976, 7142170381885440
Offset: 0

Views

Author

Wolfdieter Lang, Aug 11 2000

Keywords

Comments

a(n) gives the length of the word obtained after n steps with the substitution rule 0->1^6, 1->(1^6)0, starting from 0. The number of 1's and 0's of this word is 6*a(n-1) and 6*a(n-2), resp.

Links

Crossrefs

Cf. A001076, A006190, A007482, A015520, A015521, A015523, A015524, A015525, A015528, A015529, A015530, A015531, A015532, A015533, A015534, A015535, A015536, A015537, A015440, A015441, A015443, A015444, A015445, A015447, A015548, A030195, A053404, A057087, A057088, A083858, A085939, A090017, A091914, A099012, A135030, A135032, A180222, A180226, A180250.

Programs

Formula

a(n) = 6*a(n-1) + 6*a(n-2); a(0)=1, a(1)=6.
a(n) = S(n, i*sqrt(6))*(-i*sqrt(6))^n with S(n, x) := U(n, x/2), Chebyshev's polynomials of the 2nd kind, A049310.
G.f.: 1/(1-6*x-6*x^2).
a(n) = Sum_{k=0..n} 5^k*A063967(n,k). - Philippe Deléham, Nov 03 2006

A015537 Expansion of x/(1 - 5*x - 4*x^2).

Original entry on oeis.org

0, 1, 5, 29, 165, 941, 5365, 30589, 174405, 994381, 5669525, 32325149, 184303845, 1050819821, 5991314485, 34159851709, 194764516485, 1110461989261, 6331368012245, 36098688018269, 205818912140325, 1173489312774701, 6690722212434805
Offset: 0

Views

Author

Olivier Gérard

Keywords

Comments

First differences give A122690(n) = {1, 4, 24, 136, 776, 4424, 25224, ...}. Partial sums of a(n) are {0, 1, 6, 35, 200, ...} = (A123270(n) - 1)/8. - Alexander Adamchuk, Nov 03 2006
For n >= 2, a(n) equals the permanent of the (n-1) X (n-1) tridiagonal matrix with 5's along the main diagonal, and 2's along the superdiagonal and the subdiagonal. - John M. Campbell, Jul 19 2011
Pisano period lengths: 1, 1, 8, 1, 4, 8, 48, 1, 24, 4, 40, 8, 42, 48, 8, 2, 72, 24, 360, 4, ... - R. J. Mathar, Aug 10 2012

Links

Crossrefs

Cf. A001076, A006190, A007482, A015520, A015521, A015523, A015524, A015525, A015528, A015529, A015530, A015531, A015532, A015533, A015534, A015535, A015536, A015443, A015447, A030195, A053404, A057087, A083858, A085939, A090017, A091914, A099012, A122690, A123270, A180222, A180226.

Programs

  • GAP
    a:=[0,1];; for n in [3..30] do a[n]:=5*a[n-1]+4*a[n-2]; od; a; # G. C. Greubel, Dec 26 2019
  • Magma
    [n le 2 select n-1 else 5*Self(n-1)+4*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Nov 12 2012
  • Maple
    seq( simplify((2/I)^(n-1)*ChebyshevU(n-1, 5*I/4)), n=0..20); # G. C. Greubel, Dec 26 2019
  • Mathematica
    LinearRecurrence[{5,4}, {0,1}, 30] (* Vincenzo Librandi, Nov 12 2012 *)
Table[2^(n-1)*Fibonacci[n, 5/2], {n, 0, 30}] (* G. C. Greubel, Dec 26 2019 *)
  • PARI
    x='x+O('x^30); concat([0], Vec(x/(1-5*x-4*x^2))) \\ G. C. Greubel, Jan 01 2018
  • Sage
    [lucas_number1(n,5,-4) for n in range(0, 22)] # Zerinvary Lajos, Apr 24 2009

Formula

a(n) = 5*a(n-1) + 4*a(n-2).
a(n) = Sum_{k=0..floor((n-1)/2)} C(n-k-1, k)*4^k*5^(n-2*k-1). - Paul Barry, Apr 23 2005
a(n) = Sum_{k=0..(n-1)} A122690(k). - Alexander Adamchuk, Nov 03 2006
a(n) = 2^(n-1)*Fibonacci(n, 5/2) = (2/i)^(n-1)*ChebyshevU(n-1, 5*i/4). - G. C. Greubel, Dec 26 2019

A084128 a(n) = 4*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.

Original entry on oeis.org

1, 2, 12, 56, 272, 1312, 6336, 30592, 147712, 713216, 3443712, 16627712, 80285696, 387653632, 1871757312, 9037643776, 43637604352, 210700992512, 1017354387456, 4912221519872, 23718303629312, 114522100596736, 552961616904192, 2669934870003712
Offset: 0

Views

Author

Paul Barry, May 16 2003

Keywords

Comments

Original name was: Generalized Fibonacci sequence.
Binomial transform of A084058.

Links

Crossrefs

Cf. A001333 A001541, A002203, A057087, A084058, A084128, A201730.
Appears in A086346, A086347 and A086348. - Johannes W. Meijer, Aug 01 2010

Programs

  • Magma
    [2^(n-1)*Evaluate(DicksonFirst(n,-1), 2): n in [0..40]]; // G. C. Greubel, Oct 13 2022
  • Maple
    a:=proc(n) option remember; if n=0 then 1 elif n=1 then 2 else
4*a(n-1)+4*a(n-2); fi; end: seq(a(n), n=0..40); # Wesley Ivan Hurt, Jan 31 2017
a := n -> (2*I)^n*ChebyshevT(n, -I):
seq(simplify(a(n)), n = 0..23); # Peter Luschny, Dec 03 2023
  • Mathematica
    CoefficientList[Series[(2 z - 1)/(4 z^2 + 4 z - 1), {z, 0, 100}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 01 2011 *)
Table[2^(n-1) LucasL[n, 2], {n, 0, 20}] (* Vladimir Reshetnikov, Oct 07 2016 *)
LinearRecurrence[{4,4},{1,2},30] (* Harvey P. Dale, Mar 01 2018 *)
  • PARI
    a(n)=if(n<0,0,polsym(4+4*x-x^2,n)[n+1]/2)
  • Sage
    [lucas_number2(n,4,-4)/2 for n in range(0, 23)] # Zerinvary Lajos, May 14 2009

Formula

a(n) = 2^n * A001333(n).
G.f.: (1-2*x)/(1-4*x-4*x^2).
a(n) = 4*a(n-1) + 4*a(n-2), a(0)=1, a(1)=2.
a(n) = (2 + 2*sqrt(2))^n/2 + (2 - 2*sqrt(2))^n/2.
E.g.f.: exp(2*x)*cosh(2*x*sqrt(2)).
From Johannes W. Meijer, Aug 01 2010: (Start)
Lim_{k->infinity} a(n+k)/a(k) = A084128(n) + 2*A057087(n-1)*sqrt(2).
Lim_{n->infinity} A084128(n)/A057087(n-1) = sqrt(2). (End)
a(n) = Sum_{k=0..n} A201730(n,k)*7^k. - Philippe Deléham, Dec 06 2011
G.f.: G(0)/2, where G(k)= 1 + 1/(1 - x*(4*k-2)/(x*(4*k+2) - 1/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 27 2013
a(n) = 2^(n-1)*A002203(n). - Vladimir Reshetnikov, Oct 07 2016
Showing 1-10 of 37 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.