A001787 -id:A001787 - cp's OEIS frontend

A000079 Powers of 2: a(n) = 2^n.

1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592

Offset: 0

N. J. A. Sloane

2^0 = 1 is the only odd power of 2.
Number of subsets of an n-set.
There are 2^(n-1) compositions (ordered partitions) of n (see for example Riordan). This is the unlabeled analog of the preferential labelings sequence A000670.
This is also the number of weakly unimodal permutations of 1..n + 1, that is, permutations with exactly one local maximum. E.g., a(4) = 16: 12345, 12354, 12453, 12543, 13452, 13542, 14532 and 15432 and their reversals. - Jon Perry, Jul 27 2003 [Proof: see next line! See also A087783.]
Proof: n must appear somewhere and there are 2^(n-1) possible choices for the subset that precedes it. These must appear in increasing order and the rest must follow n in decreasing order. QED. - N. J. A. Sloane, Oct 26 2003
a(n+1) is the smallest number that is not the sum of any number of (distinct) earlier terms.
Same as Pisot sequences E(1, 2), L(1, 2), P(1, 2), T(1, 2). See A008776 for definitions of Pisot sequences.
With initial 1 omitted, same as Pisot sequences E(2, 4), L(2, 4), P(2, 4), T(2, 4). - David W. Wilson
Not the sum of two or more consecutive numbers. - Lekraj Beedassy, May 14 2004
Least deficient or near-perfect numbers (i.e., n such that sigma(n) = A000203(n) = 2n - 1). - Lekraj Beedassy, Jun 03 2004. [Comment from Max Alekseyev, Jan 26 2005: All the powers of 2 are least deficient numbers but it is not known if there exists a least deficient number that is not a power of 2.]
Almost-perfect numbers referred to as least deficient or slightly defective (Singh 1997) numbers. Does "near-perfect numbers" refer to both almost-perfect numbers (sigma(n) = 2n - 1) and quasi-perfect numbers (sigma(n) = 2n + 1)? There are no known quasi-perfect or least abundant or slightly excessive (Singh 1997) numbers.
The sum of the numbers in the n-th row of Pascal's triangle; the sum of the coefficients of x in the expansion of (x+1)^n.
The Collatz conjecture (the hailstone sequence will eventually reach the number 1, regardless of which positive integer is chosen initially) may be restated as (the hailstone sequence will eventually reach a power of 2, regardless of which positive integer is chosen initially).
The only hailstone sequence which doesn't rebound (except "on the ground"). - Alexandre Wajnberg, Jan 29 2005
With p(n) as the number of integer partitions of n, p(i) is the number of parts of the i-th partition of n, d(i) is the number of different parts of the i-th partition of n, m(i,j) is the multiplicity of the j-th part of the i-th partition of n, one has: a(n) = Sum_{i = 1..p(n)} (p(i)! / (Product_{j=1..d(i)} m(i,j)!)). - Thomas Wieder, May 18 2005
The number of binary relations on an n-element set that are both symmetric and antisymmetric. Also the number of binary relations on an n-element set that are symmetric, antisymmetric and transitive.
The first differences are the sequence itself. - Alexandre Wajnberg and Eric Angelini, Sep 07 2005
a(n) is the largest number with shortest addition chain involving n additions. - David W. Wilson, Apr 23 2006
Beginning with a(1) = 0, numbers not equal to the sum of previous distinct natural numbers. - Giovanni Teofilatto, Aug 06 2006
For n >= 1, a(n) is equal to the number of functions f:{1, 2, ..., n} -> {1, 2} such that for a fixed x in {1, 2, ..., n} and a fixed y in {1, 2} we have f(x) != y. - Aleksandar M. Janjic and Milan Janjic, Mar 27 2007
Let P(A) be the power set of an n-element set A. Then a(n) is the number of pairs of elements {x,y} of P(A) for which x = y. - Ross La Haye, Jan 09 2008
a(n) is the number of permutations on [n+1] such that every initial segment is an interval of integers. Example: a(3) counts 1234, 2134, 2314, 2341, 3214, 3241, 3421, 4321. The map "p -> ascents of p" is a bijection from these permutations to subsets of [n]. An ascent of a permutation p is a position i such that p(i) < p(i+1). The permutations shown map to 123, 23, 13, 12, 3, 2, 1 and the empty set respectively. - David Callan, Jul 25 2008
2^(n-1) is the largest number having n divisors (in the sense of A077569); A005179(n) is the smallest. - T. D. Noe, Sep 02 2008
a(n) appears to match the number of divisors of the modified primorials (excluding 2, 3 and 5). Very limited range examined, PARI example shown. - Bill McEachen, Oct 29 2008
Successive k such that phi(k)/k = 1/2, where phi is Euler's totient function. - Artur Jasinski, Nov 07 2008
A classical transform consists (for general a(n)) in swapping a(2n) and a(2n+1); examples for Jacobsthal A001045 and successive differences: A092808, A094359, A140505. a(n) = A000079 leads to 2, 1, 8, 4, 32, 16, ... = A135520. - Paul Curtz, Jan 05 2009
This is also the (L)-sieve transform of {2, 4, 6, 8, ..., 2n, ...} = A005843. (See A152009 for the definition of the (L)-sieve transform.) - John W. Layman, Jan 23 2009
a(n) = a(n-1)-th even natural number (A005843) for n > 1. - Jaroslav Krizek, Apr 25 2009
For n >= 0, a(n) is the number of leaves in a complete binary tree of height n. For n > 0, a(n) is the number of nodes in an n-cube. - K.V.Iyer, May 04 2009
Permutations of n+1 elements where no element is more than one position right of its original place. For example, there are 4 such permutations of three elements: 123, 132, 213, and 312. The 8 such permutations of four elements are 1234, 1243, 1324, 1423, 2134, 2143, 3124, and 4123. - Joerg Arndt, Jun 24 2009
Catalan transform of A099087. - R. J. Mathar, Jun 29 2009
a(n) written in base 2: 1,10,100,1000,10000,..., i.e., (n+1) times 1, n times 0 (A011557(n)). - Jaroslav Krizek, Aug 02 2009
Or, phi(n) is equal to the number of perfect partitions of n. - Juri-Stepan Gerasimov, Oct 10 2009
These are the 2-smooth numbers, positive integers with no prime factors greater than 2. - Michael B. Porter, Oct 04 2009
A064614(a(n)) = A000244(n) and A064614(m) < A000244(n) for m < a(n). - Reinhard Zumkeller, Feb 08 2010
a(n) is the largest number m such that the number of steps of iterations of {r - (largest divisor d < r)} needed to reach 1 starting at r = m is equal to n. Example (a(5) = 32): 32 - 16 = 16; 16 - 8 = 8; 8 - 4 = 4; 4 - 2 = 2; 2 - 1 = 1; number 32 has 5 steps and is the largest such number. See A105017, A064097, A175125. - Jaroslav Krizek, Feb 15 2010
a(n) is the smallest proper multiple of a(n-1). - Dominick Cancilla, Aug 09 2010
The powers-of-2 triangle T(n, k), n >= 0 and 0 <= k <= n, begins with: {1}; {2, 4}; {8, 16, 32}; {64, 128, 256, 512}; ... . The first left hand diagonal T(n, 0) = A006125(n + 1), the first right hand diagonal T(n, n) = A036442(n + 1) and the center diagonal T(2*n, n) = A053765(n + 1). Some triangle sums, see A180662, are: Row1(n) = A122743(n), Row2(n) = A181174(n), Fi1(n) = A181175(n), Fi2(2*n) = A181175(2*n) and Fi2(2*n + 1) = 2*A181175(2*n + 1). - Johannes W. Meijer, Oct 10 2010
Records in the number of prime factors. - Juri-Stepan Gerasimov, Mar 12 2011
Row sums of A152538. - Gary W. Adamson, Dec 10 2008
A078719(a(n)) = 1; A006667(a(n)) = 0. - Reinhard Zumkeller, Oct 08 2011
The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=1, a(n) equals the number of 2-colored compositions of n such that no adjacent parts have the same color. - Milan Janjic, Nov 17 2011
Equals A001405 convolved with its right-shifted variant: (1 + 2x + 4x^2 + ...) = (1 + x + 2x^2 + 3x^3 + 6x^4 + 10x^5 + ...) * (1 + x + x^2 + 2x^3 + 3x^4 + 6x^5 + ...). - Gary W. Adamson, Nov 23 2011
The number of odd-sized subsets of an n+1-set. For example, there are 2^3 odd-sized subsets of {1, 2, 3, 4}, namely {1}, {2}, {3}, {4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, and {2, 3, 4}. Also, note that 2^n = Sum_{k=1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
a(n) is the number of 1's in any row of Pascal's triangle (mod 2) whose row number has exactly n 1's in its binary expansion (see A007318 and A047999). (The result of putting together A001316 and A000120.) - Marcus Jaiclin, Jan 31 2012
A204455(k) = 1 if and only if k is in this sequence. - Wolfdieter Lang, Feb 04 2012
For n>=1 apparently the number of distinct finite languages over a unary alphabet, whose minimum regular expression has alphabetic width n (verified up to n=17), see the Gruber/Lee/Shallit link. - Hermann Gruber, May 09 2012
First differences of A000225. - Omar E. Pol, Feb 19 2013
This is the lexicographically earliest sequence which contains no arithmetic progression of length 3. - Daniel E. Frohardt, Apr 03 2013
a(n-2) is the number of bipartitions of {1..n} (i.e., set partitions into two parts) such that 1 and 2 are not in the same subset. - Jon Perry, May 19 2013
Numbers n such that the n-th cyclotomic polynomial has a root mod 2; numbers n such that the n-th cyclotomic polynomial has an even number of odd coefficients. - Eric M. Schmidt, Jul 31 2013
More is known now about non-power-of-2 "Almost Perfect Numbers" as described in Dagal. - Jonathan Vos Post, Sep 01 2013
Number of symmetric Ferrers diagrams that fit into an n X n box. - Graham H. Hawkes, Oct 18 2013
Numbers n such that sigma(2n) = 2n + sigma(n). - Jahangeer Kholdi, Nov 23 2013
a(1), ..., a(floor(n/2)) are all values of permanent on set of square (0,1)-matrices of order n>=2 with row and column sums 2. - Vladimir Shevelev, Nov 26 2013
Numbers whose base-2 expansion has exactly one bit set to 1, and thus has base-2 sum of digits equal to one. - Stanislav Sykora, Nov 29 2013
A072219(a(n)) = 1. - Reinhard Zumkeller, Feb 20 2014
a(n) is the largest number k such that (k^n-2)/(k-2) is an integer (for n > 1); (k^a(n)+1)/(k+1) is never an integer (for k > 1 and n > 0). - Derek Orr, May 22 2014
If x = A083420(n), y = a(n+1) and z = A087289(n), then x^2 + 2*y^2 = z^2. - Vincenzo Librandi, Jun 09 2014
The mini-sequence b(n) = least number k > 0 such that 2^k ends in n identical digits is given by {1, 18, 39}. The repeating digits are {2, 4, 8} respectively. Note that these are consecutive powers of 2 (2^1, 2^2, 2^3), and these are the only powers of 2 (2^k, k > 0) that are only one digit. Further, this sequence is finite. The number of n-digit endings for a power of 2 with n or more digits id 4*5^(n-1). Thus, for b(4) to exist, one only needs to check exponents up to 4*5^3 = 500. Since b(4) does not exist, it is clear that no other number will exist. - Derek Orr, Jun 14 2014
The least number k > 0 such that 2^k ends in n consecutive decreasing digits is a 3-number sequence given by {1, 5, 25}. The consecutive decreasing digits are {2, 32, 432}. There are 100 different 3-digit endings for 2^k. There are no k-values such that 2^k ends in '987', '876', '765', '654', '543', '321', or '210'. The k-values for which 2^k ends in '432' are given by 25 mod 100. For k = 25 + 100*x, the digit immediately before the run of '432' is {4, 6, 8, 0, 2, 4, 6, 8, 0, 2, ...} for x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...}, respectively. Thus, we see the digit before '432' will never be a 5. So, this sequence is complete. - Derek Orr, Jul 03 2014
a(n) is the number of permutations of length n avoiding both 231 and 321 in the classical sense which are breadth-first search reading words of increasing unary-binary trees. For more details, see the entry for permutations avoiding 231 at A245898. - Manda Riehl, Aug 05 2014
Numbers n such that sigma(n) = sigma(2n) - phi(4n). - Farideh Firoozbakht, Aug 14 2014
This is a B_2 sequence: for i < j, differences a(j) - a(i) are all distinct. Here 2*a(n) < a(n+1) + 1, so a(n) - a(0) < a(n+1) - a(n). - Thomas Ordowski, Sep 23 2014
a(n) counts n-walks (closed) on the graph G(1-vertex; 1-loop, 1-loop). - David Neil McGrath, Dec 11 2014
a(n-1) counts walks (closed) on the graph G(1-vertex; 1-loop, 2-loop, 3-loop, 4-loop, ...). - David Neil McGrath, Jan 01 2015
b(0) = 4; b(n+1) is the smallest number not in the sequence such that b(n+1) - Prod_{i=0..n} b(i) divides b(n+1) - Sum_{i=0..n} b(i). Then b(n) = a(n) for n > 2. - Derek Orr, Jan 15 2015
a(n) counts the permutations of length n+2 whose first element is 2 such that the permutation has exactly one descent. - Ran Pan, Apr 17 2015
a(0)-a(30) appear, with a(26)-a(30) in error, in tablet M 08613 (see CDLI link) from the Old Babylonian period (c. 1900-1600 BC). - Charles R Greathouse IV, Sep 03 2015
Subsequence of A028982 (the squares or twice squares sequence). - Timothy L. Tiffin, Jul 18 2016
A000120(a(n)) = 1. A000265(a(n)) = 1. A000593(a(n)) = 1. - Juri-Stepan Gerasimov, Aug 16 2016
Number of monotone maps f : [0..n] -> [0..n] which are order-increasing (i <= f(i)) and idempotent (f(f(i)) = f(i)). In other words, monads on the n-th ordinal (seen as a posetal category). Any monad f determines a subset of [0..n] that contains n, by considering its set of monad algebras = fixed points { i | f(i) = i }. Conversely, any subset S of [0..n] containing n determines a monad on [0..n], by the function i |-> min { j | i <= j, j in S }. - Noam Zeilberger, Dec 11 2016
Consider n points lying on a circle. Then for n>=2 a(n-2) gives the number of ways to connect two adjacent points with nonintersecting chords. - Anton Zakharov, Dec 31 2016
Satisfies Benford's law [Diaconis, 1977; Berger-Hill, 2017] - N. J. A. Sloane, Feb 07 2017
Also the number of independent vertex sets and vertex covers in the n-empty graph. - Eric W. Weisstein, Sep 21 2017
Also the number of maximum cliques in the n-halved cube graph for n > 4. - Eric W. Weisstein, Dec 04 2017
Number of pairs of compositions of n corresponding to a seaweed algebra of index n-1. - Nick Mayers, Jun 25 2018
The multiplicative group of integers modulo a(n) is cyclic if and only if n = 0, 1, 2. For n >= 3, it is a product of two cyclic groups. - Jianing Song, Jun 27 2018
k^n is the determinant of n X n matrix M_(i, j) = binomial(k + i + j - 2, j) - binomial(i+j-2, j), in this case k=2. - Tony Foster III, May 12 2019
Solutions to the equation Phi(2n + 2*Phi(2n)) = 2n. - M. Farrokhi D. G., Jan 03 2020
a(n-1) is the number of subsets of {1,2,...,n} which have an element that is the size of the set. For example, for n = 4, a(3) = 8 and the subsets are {1}, {1,2}, {2,3}, {2,4}, {1,2,3}, {1,3,4}, {2,3,4}, {1,2,3,4}. - Enrique Navarrete, Nov 21 2020
a(n) is the number of self-inverse (n+1)-order permutations with 231-avoiding. E.g., a(3) = 8: [1234, 1243, 1324, 1432, 2134, 2143, 3214, 4321]. - Yuchun Ji, Feb 26 2021
For any fixed k > 0, a(n) is the number of ways to tile a strip of length n+1 with tiles of length 1, 2, ... k, where the tile of length k can be black or white, with the restriction that the first tile cannot be black. - Greg Dresden and Bora Bursalı, Aug 31 2023

			There are 2^3 = 8 subsets of a 3-element set {1,2,3}, namely { -, 1, 2, 3, 12, 13, 23, 123 }.

Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), p. 1016.
Mohammad K. Azarian, A Generalization of the Climbing Stairs Problem, Mathematics and Computer Education Journal, Vol. 31, No. 1, pp. 24-28, Winter 1997.
John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 73, 84.
Jan Gullberg, Mathematics from the Birth of Numbers, W. W. Norton & Co., NY & London, 1997, §4.5 Logarithms and §8.1 Terminology, pp. 150, 264.
Paul J. Nahin, An Imaginary Tale: The Story of sqrt(-1), Princeton University Press, Princeton, NJ. 1998, pp. 69-70.
Alfred S. Posamentier, Math Charmers, Tantalizing Tidbits for the Mind, Prometheus Books, NY, 2003, page 273.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
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).
V. E. Tarakanov, Combinatorial problems on binary matrices, Combin. Analysis, MSU, 5 (1980), 4-15. (Russian)
James J. Tattersall, Elementary Number Theory in Nine Chapters, Cambridge University Press, 1999, page 141.
S. Wolfram, A New Kind of Science, Wolfram Media, 2002; p. 55.

N. J. A. Sloane, Table of n, 2^n for n = 0..1000
Milton Abramowitz and Irene A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Juan S. Auli and Sergi Elizalde, Wilf equivalences between vincular patterns in inversion sequences, arXiv:2003.11533 [math.CO], 2020.
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
Jonathan Beagley and Lara Pudwell, Colorful Tilings and Permutations, Journal of Integer Sequences, Vol. 24 (2021), Article 21.10.4.
Arno Berger and Theodore P. Hill, What is Benford's Law?, Notices, Amer. Math. Soc., 64:2 (2017), 132-134.
Tobias Boege and Thomas Kahle, Construction Methods for Gaussoids, arXiv:1902.11260 [math.CO], 2019.
Anicius Manlius Severinus Boethius, De arithmetica, Book 1, section 9.
Henry Bottomley, Illustration of initial terms
Douglas Butler, Powers of Two up to 2^222
Peter J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Peter J. Cameron, Notes on Counting, Peter Cameron's Blog, 15/05/2017.
CDLI, M 08613.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
V. Coll, M. Hyatt, C. Magnant, and H. Wang, Meander graphs and Frobenius seaweed Lie algebras II, Journal of Generalized Lie Theory and Applications 9 (1) (2015) 227.
M. Coons and H. Winning, Powers of Two Modulo Powers of Three, J. Int. Seq. 18 (2015) # 15.6.1.
Keneth Adrian P. Dagal and Jose Arnaldo B. Dris, A Criterion for Almost Perfect Numbers in Terms of the Abundancy Index, arXiv:1308.6767v1 [math.NT], Aug 14 2013.
V. Dergachev and A. Kirillov, Index of Lie algebras of seaweed type, J. Lie Theory 10 (2) (2000) 331-343.
Persi Diaconis, The distribution of leading digits and uniform distribution mod 1, Ann. Probability, 5, 1977, 72--81.
Kenneth Edwards and Michael A. Allen, New combinatorial interpretations of the Fibonacci numbers squared, golden rectangle numbers, and Jacobsthal numbers using two types of tile, J. Int. Seq. 24 (2021) Article 21.3.8.
David Eppstein, Making Change in 2048, arXiv:1804.07396 [cs.DM], 2018.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 18
Joël Gay and Vincent Pilaud, The weak order on Weyl posets, arXiv:1804.06572 [math.CO], 2018.
Daniele A. Gewurz and Francesca Merola, Sequences realized as Parker vectors of oligomorphic permutation groups, J. Integer Seqs., Vol. 6, 2003.
Hermann Gruber, Jonathan Lee and Jeffrey Shallit, Enumerating regular expressions and their languages, arXiv:1204.4982v1 [cs.FL], 2012.
R. K. Guy, Letter to N. J. A. Sloane
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 6
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 68
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 72
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 267
Marcus Jaiclin, et al. Pascal's Triangle, Mod 2,3,5
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
J. W. Layman, The Hankel Transform and Some of its Properties, J. Integer Sequences, 4 (2001), #01.1.5.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, 184 (1893), 835-901.
Victor Meally, Comparison of several sequences given in Motzkin's paper "Sorting numbers for cylinders...", letter to N. J. A. Sloane, N. D.
Augustine O. Munagi, Integer Compositions and Higher-Order Conjugation, J. Int. Seq., Vol. 21 (2018), Article 18.8.5.
R. Ondrejka, Exact values of 2^n, n=1(1)4000, Math. Comp., 23 (1969), 456.
Permutation Pattern Avoidance Library (PermPAL), Av(012_021)
G. Pfeiffer, Counting Transitive Relations, Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.
Robert Price, Comments on A000079 concerning Elementary Cellular Automata, Feb 26 2016.
Shingo Saito, Tatsushi Tanaka, and Noriko Wakabayashi, Combinatorial Remarks on the Cyclic Sum Formula for Multiple Zeta Values, J. Int. Seq. 14 (2011) # 11.2.4, Table 1.
Michael Z. Spivey and Laura L. Steil, The k-Binomial Transforms and the Hankel Transform, Journal of Integer Sequences, Vol. 9 (2006), Article 06.1.1.
J. Tanton, A Dozen Questions about the Powers of Two, Math Horizons, Vol. 8, pp. 5-10, September 2001.
G. Villemin's Almanac of Numbers, Puissances de 2
Sage Weil, 1058 powers of two
Eric Weisstein's World of Mathematics, Abundance
Eric Weisstein's World of Mathematics, Binomial Sums
Eric Weisstein's World of Mathematics, Binomial Transform
Eric Weisstein's World of Mathematics, Hailstone Number (Collatz Problem)
Eric Weisstein's World of Mathematics, Composition
Eric Weisstein's World of Mathematics, Elementary Cellular Automaton
Eric Weisstein's World of Mathematics, Empty Graph
Eric Weisstein's World of Mathematics, Erf
Eric Weisstein's World of Mathematics, Fractional Part
Eric Weisstein's World of Mathematics, Halved Cube Graph
Eric Weisstein's World of Mathematics, Hypercube
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Least Deficient Number
Eric Weisstein's World of Mathematics, Maximum Clique
Eric Weisstein's World of Mathematics, PowerFractional Parts
Eric Weisstein's World of Mathematics, Subset
Eric Weisstein's World of Mathematics, Vertex Cover
Wikipedia, Almost perfect number
S. Wolfram, A New Kind of Science
Index entries for sequences related to binary expansion of n
Index to Elementary Cellular Automata
Index entries for sequences related to cellular automata
Index entries for "core" sequences
Index to divisibility sequences
Index entries for related partition-counting sequences
Index entries for linear recurrences with constant coefficients, signature (2).
Index entries for sequences related to Benford's law

Cf. A000225, A038754, A133464, A140730, A037124, A001787, A001788, A001789, A003472, A054849, A002409, A054851, A140325, A140354, A000041, A152537, A001405, A007318, A000120, A000265, A000593, A001227, A077020, A077021.
This is the Hankel transform (see A001906 for the definition) of A000984, A002426, A026375, A026387, A026569, A026585, A026671 and A032351. - John W. Layman, Jul 31 2000
Euler transform of A001037, A209406 (multisets), inverse binomial transform of A000244, binomial transform of A000012.
Complement of A057716.
Boustrophedon transforms: A000734, A000752.
Range of values of A006519, A007875, A011782, A030001, A034444, A037445, A053644, and A054243.
Cf. A018900, A014311, A014312, A014313, A023688, A023689, A023690, A023691 (sum of 2, ..., 9 distinct powers of 2).
Cf. A090129.
The following are parallel families: A000079 (2^n), A004094 (2^n reversed), A028909 (2^n sorted up), A028910 (2^n sorted down), A036447 (double and reverse), A057615 (double and sort up), A263451 (double and sort down); A000244 (3^n), A004167 (3^n reversed), A321540 (3^n sorted up), A321539 (3^n sorted down), A163632 (triple and reverse), A321542 (triple and sort up), A321541 (triple and sort down).

a000079 = (2 ^)
a000079_list = iterate (* 2) 1
-- Reinhard Zumkeller, Jan 22 2014, Mar 05 2012, Dec 29 2011

[2^n: n in [0..40]]; // Vincenzo Librandi, Feb 17 2014

[n le 2 select n else 5*Self(n-1)-6*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Feb 17 2014

A000079 := n->2^n; [ seq(2^n,n=0..50) ];
isA000079 := proc(n)
    local fs;
    fs := numtheory[factorset](n) ;
    if n = 1 then
        true ;
    elif nops(fs) <> 1 then
        false;
    elif op(1,fs) = 2 then
        true;
    else
        false ;
    end if;
end proc: # R. J. Mathar, Jan 09 2017

Table[2^n, {n, 0, 50}]
2^Range[0, 50] (* Wesley Ivan Hurt, Jun 14 2014 *)
LinearRecurrence[{2}, {2}, {0, 20}] (* Eric W. Weisstein, Sep 21 2017 *)
CoefficientList[Series[1/(1 - 2 x), {x, 0, 20}], x] (* Eric W. Weisstein, Sep 21 2017 *)
NestList[2# &, 1, 40] (* Harvey P. Dale, Oct 07 2019 *)

A000079(n):=2^n$ makelist(A000079(n),n,0,30); /* Martin Ettl, Nov 05 2012 */

A000079(n)=2^n \\ Edited by M. F. Hasler, Aug 27 2014

unimodal(n)=local(x,d,um,umc); umc=0; for (c=0,n!-1, x=numtoperm(n,c); d=0; um=1; for (j=2,n,if (x[j]x[j-1] && d==1,um=0); if (um==0,break)); if (um==1,print(x)); umc+=um); umc

def a(n): return 1<Michael S. Branicky, Jul 28 2022

def is_powerof2(n) -> bool: return n and (n & (n - 1)) == 0  # Peter Luschny, Apr 10 2025

(List.fill(20)(2: BigInt)).scanLeft(1: BigInt)( * ) // Alonso del Arte, Jan 16 2020

(define (A000079 n) (expt 2 n)) ;; Antti Karttunen, Mar 21 2017

a(n) = 2^n.
a(0) = 1; a(n) = 2*a(n-1).
G.f.: 1/(1 - 2*x).
E.g.f.: exp(2*x).
a(n)= Sum_{k = 0..n} binomial(n, k).
a(n) is the number of occurrences of n in A000523. a(n) = A001045(n) + A001045(n+1). a(n) = 1 + Sum_{k = 0..(n - 1)} a(k). The Hankel transform of this sequence gives A000007 = [1, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Feb 25 2004
n such that phi(n) = n/2, for n > 1, where phi is Euler's totient (A000010). - Lekraj Beedassy, Sep 07 2004
a(n + 1) = a(n) XOR 3*a(n) where XOR is the binary exclusive OR operator. - Philippe Deléham, Jun 19 2005
a(n) = StirlingS2(n + 1, 2) + 1. - Ross La Haye, Jan 09 2008
a(n+2) = 6a(n+1) - 8a(n), n = 1, 2, 3, ... with a(1) = 1, a(2) = 2. - Yosu Yurramendi, Aug 06 2008
a(n) = ka(n-1) + (4 - 2k)a(n-2) for any integer k and n > 1, with a(0) = 1, a(1) = 2. - Jaume Oliver Lafont, Dec 05 2008
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i <= l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. - Thomas Wieder, Feb 25 2009
a(0) = 1, a(1) = 2; a(n) = a(n-1)^2/a(n-2), n >= 2. - Jaume Oliver Lafont, Sep 22 2009
a(n) = A173786(n, n)/2 = A173787(n + 1, n). - Reinhard Zumkeller, Feb 28 2010
If p[i] = i - 1 and if A is the 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-1) = det A. - Milan Janjic, May 02 2010
If p[i] = Fibonacci(i-2) and if A is the 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 >= 2, a(n-2) = det A. - Milan Janjic, May 08 2010
The sum of reciprocals, 1/1 + 1/2 + 1/4 + 1/8 + ... + 1/(2^n) + ... = 2. - Mohammad K. Azarian, Dec 29 2010
a(n) = 2*A001045(n) + A078008(n) = 3*A001045(n) + (-1)^n. - Paul Barry, Feb 20 2003
a(n) = A118654(n, 2).
a(n) = A140740(n+1, 1).
a(n) = A131577(n) + A011782(n) = A024495(n) + A131708(n) + A024493(n) = A000749(n) + A038503(n) + A038504(n) + A038505(n) = A139761(n) + A139748(n) + A139714(n) + A133476(n) + A139398(n). - Paul Curtz, Jul 25 2011
a(n) = row sums of A007318. - Susanne Wienand, Oct 21 2011
a(n) = Hypergeometric([-n], [], -1). - Peter Luschny, Nov 01 2011
G.f.: A(x) = B(x)/x, B(x) satisfies B(B(x)) = x/(1 - x)^2. - Vladimir Kruchinin, Nov 10 2011
a(n) = Sum_{k = 0..n} A201730(n, k)*(-1)^k. - Philippe Deléham, Dec 06 2011
2^n = Sum_{k = 1..floor((n+1)/2)} C(n+1, 2k-1). - Dennis P. Walsh, Dec 15 2011
A209229(a(n)) = 1. - Reinhard Zumkeller, Mar 07 2012
A001227(a(n)) = 1. - Reinhard Zumkeller, May 01 2012
Sum_{n >= 1} mobius(n)/a(n) = 0.1020113348178103647430363939318... - R. J. Mathar, Aug 12 2012
E.g.f.: 1 + 2*x/(U(0) - x) where U(k) = 6*k + 1 + x^2/(6*k+3 + x^2/(6*k + 5 + x^2/U(k+1) )); (continued fraction, 3-step). - Sergei N. Gladkovskii, Dec 04 2012
a(n) = det(|s(i+2,j)|, 1 <= i,j <= n), where s(n,k) are Stirling numbers of the first kind. - Mircea Merca, Apr 04 2013
a(n) = det(|ps(i+1,j)|, 1 <= i,j <= n), where ps(n,k) are Legendre-Stirling numbers of the first kind (A129467). - Mircea Merca, Apr 06 2013
G.f.: W(0), where W(k) = 1 + 2*x*(k+1)/(1 - 2*x*(k+1)/( 2*x*(k+2) + 1/W(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 28 2013
a(n-1) = Sum_{t_1 + 2*t_2 + ... + n*t_n = n} multinomial(t_1 + t_2 + ... + t_n; t_1, t_2, ..., t_n). - Mircea Merca, Dec 06 2013
Construct the power matrix T(n,j) = [A^*j]*[S^*(j-1)] where A(n)=(1,1,1,...) and S(n)=(0,1,0,0,...) (where * is convolution operation). Then a(n-1) = Sum_{j=1..n} T(n,j). - David Neil McGrath, Jan 01 2015
a(n) = A000005(A002110(n)). - Ivan N. Ianakiev, May 23 2016
From Ilya Gutkovskiy, Jul 18 2016: (Start)
Exponential convolution of A000012 with themselves.
a(n) = Sum_{k=0..n} A011782(k).
Sum_{n>=0} a(n)/n! = exp(2) = A072334.
Sum_{n>=0} (-1)^n*a(n)/n! = exp(-2) = A092553. (End)
G.f.: (r(x) * r(x^2) * r(x^4) * r(x^8) * ...) where r(x) = A090129(x) = (1 + 2x + 2x^2 + 4x^3 + 8x^4 + ...). - Gary W. Adamson, Sep 13 2016
a(n) = A000045(n + 1) + A000045(n) + Sum_{k = 0..n - 2} A000045(k + 1)*2^(n - 2 - k). - Melvin Peralta, Dec 22 2017
a(n) = 7*A077020(n)^2 + A077021(n)^2, n>=3. - Ralf Steiner, Aug 08 2021
a(n)= n + 1 + Sum_{k=3..n+1} (2*k-5)*J(n+2-k), where Jacobsthal number J(n) = A001045(n). - Michael A. Allen, Jan 12 2022
Integral_{x=0..Pi} cos(x)^n*cos(n*x) dx = Pi/a(n) (see Nahin, pp. 69-70). - Stefano Spezia, May 17 2023

Clarified a comment T. D. Noe, Aug 30 2009
Edited by Daniel Forgues, May 12 2010
Incorrect comment deleted by Matthew Vandermast, May 17 2014
Comment corrected to match offset by Geoffrey Critzer, Nov 28 2014

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

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

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

			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

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.

N. J. A. Sloane, First 141 rows of Pascal's triangle, formatted as a simple linear sequence: (n, a(n)), n=0..10152.
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
Tewodros Amdeberhan, Moa Apagodu, and Doron Zeilberger, Wilf's "Snake Oil" Method Proves an Identity in The Motzkin Triangle, arXiv:1507.07660 [math.CO], 2015.
Said Amrouche and Hacène Belbachir, Asymmetric extension of Pascal-Dellanoy triangles, arXiv:2001.11665 [math.CO], 2020.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Vol. 332, No. 6 (2014), pp. 45-54.
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 38 (2012), pp. 1871-1876.
Mohammad K. Azarian, Fibonacci Identities as Binomial Sums II, International Journal of Contemporary Mathematical Sciences, Vol. 7, No. 42 (2012), pp. 2053-2059.
Amulya Kumar Bag, Binomial theorem in ancient India, Indian Journal of History of Science, Vol. 1 (1966), pp. 68-74.
Armen G. Bagdasaryan and Ovidiu Bagdasar, On some results concerning generalized arithmetic triangles, Electronic Notes in Discrete Mathematics, Vol. 67 (2018), pp. 71-77.
Peter Bala, A combinatorial interpretation for the binomial coefficients, 2013.
Cyril Banderier and Donatella Merlini, Lattice paths with an infinite set of jumps, Proceedings of the 14th International Conference on Formal Power Series and Algebraic Combinatorics, Melbourne, Australia. 2002.
J. Fernando Barbero G., Jesús Salas, and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
Paul Barry, On Integer-Sequence-Based Constructions of Generalized Pascal Triangles, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.4.
Paul Barry, Symmetric Third-Order Recurring Sequences, Chebyshev Polynomials, and Riordan Arrays , JIS, Vol. 12 (2009) Article 09.8.6.
Paul Barry, Eulerian polynomials as moments, via exponential Riordan arrays, arXiv:1105.3043 [math.CO], 2011.
Paul Barry, Combinatorial polynomials as moments, Hankel transforms and exponential Riordan arrays, arXiv:1105.3044 [math.CO], 2011.
Paul Barry, On the Central Coefficients of Bell Matrices, J. Int. Seq., Vol. 14 (2011) Article 11.4.3, example 2.
Paul Barry, Riordan-Bernstein Polynomials, Hankel Transforms and Somos Sequences, Journal of Integer Sequences, Vol. 15 (2012), Article 12.8.2.
Paul Barry, On the Central Coefficients of Riordan Matrices, Journal of Integer Sequences, Vol. 16 (2013), Article 13.5.1.
Paul Barry, A Note on a Family of Generalized Pascal Matrices Defined by Riordan Arrays, Journal of Integer Sequences, Vol. 16 (2013), Article 13.5.4.
Paul Barry, On the Inverses of a Family of Pascal-Like Matrices Defined by Riordan Arrays, Journal of Integer Sequences, Vol. 16 (2013), Article 13.5.6.
Paul Barry, On the Connection Coefficients of the Chebyshev-Boubaker polynomials, The Scientific World Journal, Vol. 2013 (2013), Article ID 657806, 10 pages.
Paul Barry, General Eulerian Polynomials as Moments Using Exponential Riordan Arrays, Journal of Integer Sequences, Vol. 16 (2013), Article 13.9.6.
Paul Barry, Riordan arrays, generalized Narayana triangles, and series reversion, Linear Algebra and its Applications, Vol. 491 (2016), pp. 343-385.
Paul Barry, The Gamma-Vectors of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1804.05027 [math.CO], 2018.
Paul Barry, On the f-Matrices of Pascal-like Triangles Defined by Riordan Arrays, arXiv:1805.02274 [math.CO], 2018.
Paul Barry, The Central Coefficients of a Family of Pascal-like Triangles and Colored Lattice Paths, J. Int. Seq., Vol. 22 (2019), Article 19.1.3.
Paul Barry, On the halves of a Riordan array and their antecedents, arXiv:1906.06373 [math.CO], 2019.
Paul Barry, On the r-shifted central triangles of a Riordan array, arXiv:1906.01328 [math.CO], 2019.
Paul Barry, Generalized Catalan Numbers Associated with a Family of Pascal-like Triangles, J. Int. Seq., Vol. 22 (2019), Article 19.5.8.
Paul Barry, A Note on Riordan Arrays with Catalan Halves, arXiv:1912.01124 [math.CO], 2019.
Paul Barry, Chebyshev moments and Riordan involutions, arXiv:1912.11845 [math.CO], 2019.
Paul Barry, Characterizations of the Borel triangle and Borel polynomials, arXiv:2001.08799 [math.CO], 2020.
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
Paul Barry, Extensions of Riordan Arrays and Their Applications, Mathematics (2025) Vol. 13, No. 2, 242. See p. 13.
Paul Barry, Notes on Riordan arrays and lattice paths, arXiv:2504.09719 [math.CO], 2025. See p. 2.
Paul Barry and Aoife Hennessy, Four-term Recurrences, Orthogonal Polynomials and Riordan Arrays, Journal of Integer Sequences, Vol. 15 (2012), Article 12.4.2.
Jonathan W. Bober, Factorial ratios, hypergeometric series, and a family of step functions, arXiv:0709.1977v1 [math.NT], J. London Math. Soc. (2), Vol. 79 (2009), pp. 422-444.
Boris A. Bondarenko, Generalized Pascal Triangles and Pyramids, English translation published by Fibonacci Association, Santa Clara Univ., Santa Clara, CA, 1993; see p. 4.
Michael Bukata, Ryan Kulwicki, Nicholas Lewandowski, Lara Pudwell, Jacob Roth and Teresa Wheeland, Distributions of Statistics over Pattern-Avoiding Permutations, arXiv preprint arXiv:1812.07112 [math.CO], 2018.
Douglas Butler, Pascal's Triangle.
Isabel Cação, Helmuth R. Malonek, Maria Irene Falcão, and Graça Tomaz, Intrinsic Properties of a Non-Symmetric Number Triangle, J. Int. Seq., Vol. 26 (2023), Article 23.4.8.
Naiomi T. Cameron and Asamoah Nkwanta, On Some (Pseudo) Involutions in the Riordan Group, Journal of Integer Sequences, Vol. 8 (2005), Article 05.3.7.
Dario T. de Castro, p-adic Order of Positive Integers via Binomial Coefficients, INTEGERS, Electronic J. of Combinatorial Number Theory, Vol. 22, Paper A61, 2022.
Ji Young Choi, Digit Sums Generalizing Binomial Coefficients, J. Int. Seq., Vol. 22 (2019), Article 19.8.3.
Cristian Cobeli and Alexandru Zaharescu, Promenade around Pascal Triangle - Number Motives, Bull. Math. Soc. Sci. Math. Roumanie, Tome 56(104) No. 1 (2013), pp. 73-98.
CombOS - Combinatorial Object Server, Generate combinations.
J. H. Conway and N. J. A. Sloane, Low-dimensional lattices. VII Coordination sequences, Proc. R. Soc. Lond. A, Vo. 453, No. 1966 (1997), pp. 2369-2389.
Tom Copeland, Infinigens, the Pascal Triangle, and the Witt and Virasoro Algebras.
Persi Diaconis, The distribution of leading digits and uniform distribution mod 1, Ann. Probability, Vol. 5 (1977), pp. 72-81.
Karl Dilcher and Kenneth B. Stolarsky, A Pascal-Type Triangle Characterizing Twin Primes, The American Mathematical Monthly, Vol. 112, No. 8 (Oct 2005), pp. 673-681.
Tomislav Došlic and Darko Veljan, Logarithmic behavior of some combinatorial sequences, Discrete Math., Vol. 308, No. 11 (2008), pp. 2182-2212. MR2404544 (2009j:05019).
Steffen Eger, Some Elementary Congruences for the Number of Weighted Integer Compositions, J. Int. Seq., Vol. 18 (2015), Article 15.4.1.
Leonhard Euler, On the expansion of the power of any polynomial (1+x+x^2+x^3+x^4+etc.)^n, arXiv:math/0505425 [math.HO], 2005. See also The Euler Archive, item E709.
Jackson Evoniuk, Steven Klee, and Van Magnan, Enumerating Minimal Length Lattice Paths, J. Int. Seq., Vol. 21 (2018), Article 18.3.6.
A. Farina, S. Giompapa, A. Graziano, A. Liburdi, M. Ravanelli, and F. Zirilli, Tartaglia-Pascal's triangle: a historical perspective with applications, Signal, Image and Video Processing, Vol. 7, No. 1 (January 2013), pp. 173-188.
Steven Finch, Pascal Sebah, and Zai-Qiao Bai, Odd Entries in Pascal's Trinomial Triangle, arXiv:0802.2654 [math.NT], 2008.
David Fowler, The binomial coefficient function, Amer. Math. Monthly, Vol. 103, No. 1 (1996), pp. 1-17.
Shishuo Fu and Yaling Wang, Bijective recurrences concerning two Schröder triangles, arXiv:1908.03912 [math.CO], 2019.
Tom Halverson and Theodore N. Jacobson, Set-partition tableaux and representations of diagram algebras, arXiv:1808.08118 [math.RT], 2018.
T. Han and S. Kitaev, Joint distributions of statistics over permutations avoiding two patterns of length 3, arXiv:2311.02974 [math.CO], 2023
Brady Haran and Casandra Monroe, Pascal's Triangle, Numberphile video (2017).
Tian-Xiao He and Renzo Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math., Vol. 309, No. 12 (2009), pp. 3962-3974.
Nick Hobson, Python program for A007318.
V. E. Hoggatt, Jr. and Marjorie Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., Vol. 14, No. 5 (1976), pp. 395-405.
Matthew Hubbard and Tom Roby, Pascal's Triangle From Top to Bottom. [archived page]
Charles Jordan, Calculus of Finite Differences (p. 65).
Subhash Kak, The golden mean and the physics of aesthetics, in: B. Yadav and M. Mohan (eds.), Ancient Indian Leaps into Mathematics, Birkhäuser, Boston, MA, 2009, pp. 111-119; arXiv preprint, arXiv:physics/0411195 [physics.hist-ph], 2004.
Petro Kolosov, Polynomial identities involving Pascal's triangle rows, 2022.
Wolfdieter Lang, On generalizations of Stirling number triangles, J. Integer Seq., Vol. 3 (2000), Article 00.2.4.
Eitan Y. Levine, GCD formula proof.
Meng Li and Ron Goldman, Limits of sums for binomial and Eulerian numbers and their associated distributions, Discrete mathematics, Vol. 343, No. 7 (2020), 111870.
P. A. MacMahon, Memoir on the Theory of the Compositions of Numbers, Phil. Trans. Royal Soc. London A, Vol. 184 (1893), pp. 835-901.
Mathforum, Pascal's Triangle
Carl McTague, On the Greatest Common Divisor of C(q*n,n), C(q*n,2*n), ...C(q*n,q*n-q), arXiv:1510.06696 [math.CO], 2015.
D. Merlini, R. Sprugnoli, and M. C. Verri, An algebra for proper generating trees, in: D. Gardy and A. Mokkadem (eds.), Mathematics and Computer Science, Trends in Mathematics, Birkhäuser, Basel, 2000, pp. 127-139; alternative link.
Donatella Merlini, Francesca Uncini, and M. Cecilia Verri, A unified approach to the study of general and palindromic compositions, Integers, Vol. 4 (2004), A23, 26 pp.
Ângela Mestre and José Agapito, A Family of Riordan Group Automorphisms, J. Int. Seq., Vol. 22 (2019), Article 19.8.5.
Pierre Remond de Montmort, Essay d'analyse sur les jeux de hazard, Paris: Chez Jacque Quillau, 1708, p. 80.
Yossi Moshe, The density of 0's in recurrence double sequences, J. Number Theory, Vol. 103 (2003), pp. 109-121.
Lili Mu and Sai-nan Zheng, On the Total Positivity of Delannoy-Like Triangles, Journal of Integer Sequences, Vol. 20 (2017), Article 17.1.6.
Abdelkader Necer, Séries formelles et produit de Hadamard, Journal de théorie des nombres de Bordeaux, Vol. 9, No. 2 (1997), pp. 319-335.
Asamoah Nkwanta and Earl R. Barnes, Two Catalan-type Riordan Arrays and their Connections to the Chebyshev Polynomials of the First Kind, Journal of Integer Sequences, Vol. 15 (2012), Article 12.3.3.
Asamoah Nkwanta and Akalu Tefera, Curious Relations and Identities Involving the Catalan Generating Function and Numbers, Journal of Integer Sequences, Vol. 16 (2013), Article 13.9.5.
Mustafa A. A. Obaid, S. Khalid Nauman, Wafaa M. Fakieh, and Claus Michael Ringel, The numbers of support-tilting modules for a Dynkin algebra, 2014.
OEIS Wiki, Binomial coefficients
Richard L. Ollerton and Anthony G. Shannon, Some properties of generalized Pascal squares and triangles, Fib. Q., Vol. 36, No. 2 (1998), pp. 98-109.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003.
Ed Pegg, Jr., Sequence Pictures, Math Games column, Dec 08 2003. [Cached copy, with permission (pdf only)]
Balak Ram, Common factors of n!/(m!(n-m)!), (m = 1, 2, ... n-1), Journal of the Indian Mathematical Club (Madras) 1 (1909), pp. 39-43.
Franck Ramaharo, Statistics on some classes of knot shadows, arXiv:1802.07701 [math.CO], 2018.
Franck Ramaharo, A generating polynomial for the pretzel knot, arXiv:1805.10680 [math.CO], 2018.
Franck Ramaharo, A generating polynomial for the two-bridge knot with Conway's notation C(n,r), arXiv:1902.08989 [math.CO], 2019.
Franck Ramaharo, A bracket polynomial for 2-tangle shadows, arXiv:2002.06672 [math.CO], 2020.
Jack Ramsay, On Arithmetical Triangles, The Pulse of Long Island, June 1965 [Mentions application to design of antenna arrays. Annotated scan.]
Thomas M. Richardson, The Reciprocal Pascal Matrix, arXiv preprint arXiv:1405.6315 [math.CO], 2014.
Yuriy Shablya, Dmitry Kruchinin, and Vladimir Kruchinin, Method for Developing Combinatorial Generation Algorithms Based on AND/OR Trees and Its Application, Mathematics, Vol. 8, No. 6 (2020), 962.
Louis W. Shapiro, Seyoum Getu, Wen-Jin Woan, and Leon C. Woodson, The Riordan group, Discrete Applied Math., Vol. 34 (1991), pp. 229-239.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).
N. J. A. Sloane, Triangle showing silhouette of first 30 rows of Pascal's triangle (after Cobeli and Zaharescu)
N. J. A. Sloane, The OEIS: A Fingerprint File for Mathematics, arXiv:2105.05111 [math.HO], 2021.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 5.
Hermann Stamm-Wilbrandt, Compute C(n+m,...) based on C(n,...) and C(m,...) values animation.
Igor Victorovich Statsenko, On the ordinal numbers of triangles of generalized special numbers, Innovation science No 2-2, State Ufa, Aeterna Publishing House, 2024, pp. 15-19. In Russian.
Christopher Stover and Eric W. Weisstein, Composition. From MathWorld - A Wolfram Web Resource.
Gérard Villemin's Almanach of Numbers, Triangle de Pascal.
Eric Weisstein's World of Mathematics, Pascal's Triangle.
Wikipedia, Pascal's triangle.
Herbert S. Wilf, Generatingfunctionology, 2nd edn., Academic Press, NY, 1994, pp. 12ff.
Ken Williams, Mathforum, Interactive Pascal's Triangle.
Doron Zeilberger, The Combinatorial Astrology of Rabbi Abraham Ibn Ezra, arXiv:math/9809136 [math.CO], 1998.
Chris Zheng and Jeffrey Zheng, Triangular Numbers and Their Inherent Properties, Variant Construction from Theoretical Foundation to Applications, Springer, Singapore, 51-65.
Index entries for triangles and arrays related to Pascal's triangle.
Index entries for "core" sequences.
Index entries for sequences related to Benford's law.

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.

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

Flat(List([0..12],n->List([0..n],k->Binomial(n,k)))); # Stefano Spezia, Dec 22 2018

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

/* 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);
```

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

create_list(binomial(n,k),n,0,12,k,0,n); /* Emanuele Munarini, Mar 11 2011 */

C(n,k)=binomial(n,k) \\ Charles R Greathouse IV, Jun 08 2011

# 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

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

def C(n,k): return Subsets(range(n), k).cardinality() # Ralf Stephan, Jan 21 2014

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, nC(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

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

Showing 1-10 of 421 results. Next

This sequence counts edge-induced connected subgraphs of the n-dimensional hypercube graph, up to automorphisms of the hypercube; A369605 counts vertex-induced such graphs. - Pontus von Brömssen, May 12 2025

Row 3 gives the number of polyforms with n cells on the faces of a rhombic dodecahedron up to rotation and reflection. - Peter Kagey, May 19 2025

cp's OEIS Frontend

A333333 Irregular triangle: T(n,k) gives the number of k-polysticks on edges of the n-cube up to isometries of the n-cube, with 0 <= k <= A001787(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A326914 Number T(n,k) of colored integer partitions of n using all colors of a k-set such that all parts have different color patterns and a pattern for part i has i distinct colors in increasing order; triangle T(n,k), n>=0, min(j:A001787(j)>=n)<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A309509 G.f. satisfies A(A(x)) = F(x), where F(x) is the g.f. for A001787(n) = n*2^(n-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A383799 Irregular triangle: T(n,k) gives the number of k-polysticks on edges of the n-cube up to rotational symmetries of the n-cube, with 0 <= k <= A001787(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A327583 Number T(n,k) of colored compositions of n using all colors of a k-set such that all parts have different color patterns and the patterns for parts i have i distinct colors in increasing order; triangle T(n,k), n>=0, min(j:A001787(j)>=n)<=k<=n, read by rows.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A333418 Irregular triangle: T(n,k) gives the number of ways to 2-color k edges of the n-cube up to rotation and reflection, with 0 <= k <= A001787(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A103175 A001787 written in base 2.

Views

Author

Keywords

Crossrefs

Extensions

A116669 Triangle, rows tend to A001787, number of edges in n-dimensional hypercubes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A000079 Powers of 2: a(n) = 2^n.

Views

Author