This site is supported by donations to The OEIS Foundation.

# Binomial coefficients

A binomial coefficient ${\displaystyle \scriptstyle {\binom {n}{k}}\,}$ tells us how many ways there are of picking ${\displaystyle \scriptstyle k\,}$ elements out of a set of ${\displaystyle \scriptstyle n\,}$ elements, without regard to order. For example, to pick 3 numbers from the a set of 5 numbers ({1, 2, 3, 4, 5} for this example), there are ${\displaystyle \scriptstyle {\binom {5}{3}}\,=\,10\,}$ ways: {1, 2, 3}, {1, 2, 4}, {1, 2, 5}, {1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5} (presented here in order just to show we have not overlooked any).

The formula involves factorials

${\displaystyle {\binom {n}{k}}:={\frac {n!}{k!\,(n-k)!}}\,}$

but there is an easier way if we don't mind computing some smaller binomial coefficients first.

Of course ${\displaystyle \scriptstyle {\binom {n}{0}}\,=\,{\binom {n}{n}}\,=\,1\,}$ (the empty set in the former case, the complete set in the latter) and ${\displaystyle \scriptstyle {\binom {n}{1}}\,=\,{\binom {n}{n-1}}\,=\,n\,}$ (picking just one element each time in the former, leaving out precisely one element each time in the latter), suggesting a symmetry that might become more apparent in a tabular arrangement.

## Pascal's triangle and binomial coefficients

Pascal's triangle is a table of binomial coefficients, i.e. the coefficients of the expanded binomial

${\displaystyle (1+x)^{n}=\sum _{d=0}^{n}{\binom {n}{d}}\,x^{d}:=\sum _{d=0}^{n}{\frac {n!}{d!\,(n-d)!}}\,x^{d}=\sum _{d=0}^{n}T(n,d)\,x^{d},\quad n\geq 0,\,}$[1]

which is the generating function for the ${\displaystyle \scriptstyle n\,}$th row (finite sequence) of Pascal's triangle.

## Individuals of generation Math error: Invalid format. after Math error: Invalid format. population doublings

The binomial coefficients Math error: Invalid format. give the number of individuals of the Math error: Invalid format. th generation after Math error: Invalid format. population doublings. For each doubling of population, each individual's clone has it's generation index incremented by 1, and thus goes to the next row. Just tally up each row from 0 to Math error: Invalid format. to get the binomial coefficients.

       0   1       3               7                              15                                                              31
0: O | . | .   . | .   .   .   . | .   .   .   .   .   .   .   . | .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . |

1:   | O | O   . | O   .   .   . | O   .   .   .   .   .   .   . | O   .   .   .   .   .   .   .   .   .   .   .   .   .   .   . |

2:   |   |     O |     O   O   . |     O   O   .   O   .   .   . |     O   O   .   O   .   .   .   O   .   .   .   .   .   .   . |

3:   |   |       |             O |             O       O   O   . |             O       O   O   .       O   O   .   O   .   .   . |

4:   |   |       |               |                             O |                             O               O       O   O   . |

5:   |   |       |               |                               |                                                             O |


This is a fractal process: to get the pattern from 0 to Math error: Invalid format. , append a shifted down (by one row) copy of the pattern from 0 to Math error: Invalid format. to the right of the pattern from 0 to Math error: Invalid format. .

(...)

(...)

## Sums of binomial coefficients

${\displaystyle \sum _{k=0}^{d}{\binom {n}{k}},\quad n\geq 0.}$    (Where ${\displaystyle d}$ is the degree of the uniquely determined polynomial of degree ${\displaystyle d}$ passing through points ${\displaystyle (k,2^{k}),\,k=0..d.}$)

${\displaystyle d\,}$ Sequence A-number
0 {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...} A000012
1 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, ...} A000027
2 {1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, ...} A000124
3 {1, 2, 4, 8, 15, 26, 42, 64, 93, 130, 176, 232, 299, 378, 470, 576, 697, 834, 988, 1160, 1351, 1562, 1794, 2048, 2325, 2626, 2952, 3304, 3683, 4090, 4526, 4992, 5489, ...} A000125
4 {1, 2, 4, 8, 16, 31, 57, 99, 163, 256, 386, 562, 794, 1093, 1471, 1941, 2517, 3214, 4048, 5036, 6196, 7547, 9109, 10903, 12951, 15276, 17902, 20854, 24158, 27841, ...} A000127
5 {1, 2, 4, 8, 16, 32, 63, 120, 219, 382, 638, 1024, 1586, 2380, 3473, 4944, 6885, 9402, 12616, 16664, 21700, 27896, 35443, 44552, 55455, 68406, 83682, 101584, 122438, ...} A006261
6 {1, 2, 4, 8, 16, 32, 64, 127, 247, 466, 848, 1486, 2510, 4096, 6476, 9949, 14893, 21778, 31180, 43796, 60460, 82160, 110056, 145499, 190051, 245506, 313912, 397594, ...} A008859
7 {1, 2, 4, 8, 16, 32, 64, 128, 255, 502, 968, 1816, 3302, 5812, 9908, 16384, 26333, 41226, 63004, 94184, 137980, 198440, 280600, 390656, 536155, 726206, 971712, 1285624, ...} A008860
8 {1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1013, 1981, 3797, 7099, 12911, 22819, 39203, 65536, 106762, 169766, 263950, 401930, 600370, 880970, 1271626, 1807781, 2533987, ...} A008861
9 {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1023, 2036, 4017, 7814, 14913, 27824, 50643, 89846, 155382, 262144, 431910, 695860, 1097790, 1698160, 2579130, 3850756, 5658537, ...} A008862
10 {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2047, 4083, 8100, 15914, 30827, 58651, 109294, 199140, 354522, 616666, 1048576, 1744436, 2842226, 4540386, 7119516, ...} A008863
11 {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4095, 8178, 16278, 32192, 63019, 121670, 230964, 430104, 784626, 1401292, 2449868, 4194304, 7036530, 11576916, ...} A219531
12 {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8191, 16369, 32647, 64839, 127858, 249528, 480492, 910596, 1695222, 3096514, 5546382, 9740686, 16777216, ...} A219615

### Generating functions for sums of binomial coefficients

A000012 Sum C(n, k), k = 0..0, n ≥ 0. (1, n ≥ 0.) Maximal number of pieces formed when "slicing a point" with n cuts. (Since you can't slice a point, you're always left with a point!)

O.g.f.: ${\displaystyle 1/(1-x)}$.

A000027 Sum C(n, k), k = 0..1, n ≥ 0. (n + 1, n ≥ 0.) (Note that A000027 has offset 1: n, n ≥ 1.) Maximal number of pieces formed when slicing a string with n cuts, i.e. n + 1 pieces.

O.g.f.: ${\displaystyle 1/(1-x)^{2}}$. (With offset 1, O.g.f.: x/(1-x)^2)

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

O.g.f.: ${\displaystyle (1-x+x^{2})/(1-x)^{3}}$.

A000125 Sum C(n, k), k = 0..3, n ≥ 0. Cake numbers: maximal number of pieces resulting from n planar cuts through a cube (or cake): C(n+1, 3) + n + 1.

O.g.f.: ${\displaystyle (1-2x+2x^{2})/(1-x)^{4}}$.

A000127 Sum C(n, k), k = 0..4, n ≥ 0. Maximal number of regions obtained by joining n points around a circle by straight lines, i.e. n(n-1)/2 cuts. Also number of regions in 4-space formed by n-1 hyperplanes.

O.g.f.: ${\displaystyle (1-3x+4x^{2}-2x^{3}+x^{4})/(1-x)^{5}}$.

A006261 Sum C(n, k), k = 0..5, n ≥ 0. Maximal number of regions in 5-space formed by n-1 4-D hyperplanes?

O.g.f.: ${\displaystyle (1-4x+7x^{2}-6x^{3}+3x^{4})/(1-x)^{6}}$.

A008859 Sum C(n, k), k = 0..6, n ≥ 0. Maximal number of regions in 6-space formed by n-1 5-D hyperplanes?

O.g.f.: ${\displaystyle (1-5x+11x^{2}-13x^{3}+9x^{4}-3x^{5}+x^{6})/(1-x)^{7}}$.

A008860 Sum C(n, k), k = 0..7, n ≥ 0. Maximal number of regions in 7-space formed by n-1 6-D hyperplanes?

O.g.f.: ${\displaystyle (1-6x+16x^{2}-24x^{3}+22x^{4}-12x^{5}+4x^{6})/(1-x)^{8}}$.

A008861 Sum C(n, k), k = 0..8, n ≥ 0. Maximal number of regions in 8-space formed by n-1 7-D hyperplanes?

O.g.f.: ${\displaystyle (1-7x+22x^{2}-40x^{3}+46x^{4}-34x^{5}+16x^{6}-4x^{7}+x^{8})/(1-x)^{9}}$.

A008862 Sum C(n, k), k = 0..9, n ≥ 0. Maximal number of regions in 9-space formed by n-1 8-D hyperplanes?

O.g.f.: ${\displaystyle (1-8x+29x^{2}-62x^{3}+86x^{4}-80x^{5}+50x^{6}-20x^{7}+5x^{8})/(1-x)^{10}}$.

A008863 Sum C(n, k), k = 0..10, n ≥ 0. Maximal number of regions in 10-space formed by n-1 9-D hyperplanes?

O.g.f.: ${\displaystyle (1-9x+37x^{2}-91x^{3}+148x^{4}-166x^{5}+130x^{6}-70x^{7}+25x^{8}-5x^{9}+x^{10})/(1-x)^{11}}$.

A219531 Sum C(n, k), k = 0..11, n ≥ 0. Maximal number of regions in 11-space formed by n-1 10-D hyperplanes?

O.g.f.: ${\displaystyle (1-10x+46x^{2}-128x^{3}+239x^{4}-314x^{5}+296x^{6}-200x^{7}+95x^{8}-30x^{9}+6x^{10})/(1-x)^{12}}$.

A219615 Sum C(n, k), k = 0..12, n ≥ 0. Maximal number of regions in 12-space formed by n-1 11-D hyperplanes?

O.g.f.: ${\displaystyle (1-11x+56x^{2}-174x^{3}+367x^{4}-553x^{5}+610x^{6}-496x^{7}+295x^{8}-125x^{9}+36x^{10}-6x^{11}+x^{12})/(1-x)^{13}}$.

#### Triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients

 ${\displaystyle \scriptstyle d\,}$ = 0 1 1 1 0 2 1 1 1 3 1 2 2 0 4 1 3 4 2 1 5 1 4 7 6 3 0 6 1 5 11 13 9 3 1 7 1 6 16 24 22 12 4 0 8 1 7 22 40 46 34 16 4 1 9 1 8 29 62 86 80 50 20 5 0 10 1 9 37 91 148 166 130 70 25 5 1 11 1 10 46 128 239 314 296 200 95 30 6 0 12 1 11 56 174 367 553 610 496 295 125 36 6 1 ${\displaystyle \scriptstyle k\,}$ = 0 1 2 3 4 5 6 7 8 9 10 11 12

##### Rows of triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients

The rows gives the infinite sequence of finite sequences

{ {1}, {1, 0}, {1, 1, 1}, {1, 2, 2, 0}, {1, 3, 4, 2, 1}, {1, 4, 7, 6, 3, 0}, {1, 5, 11, 13, 9, 3, 1}, {1, 6, 16, 24, 22, 12, 4, 0}, {1, 7, 22, 40, 46, 34, 16, 4, 1}, {1, 8, 29, 62, 86, 80, 50, 20, 5, 0}, ...}

whose concatenation gives

A059259 Triangle read by rows giving coefficient T(i,j) of x^i y^j in 1/(1-x-x*y-y^2) = 1/((1+y)(1-x-y)) for (i,j) = (0,0), (1,0), (0,1), (2,0), (1,1), (0,2), ...

{1, 1, 0, 1, 1, 1, 1, 2, 2, 0, 1, 3, 4, 2, 1, 1, 4, 7, 6, 3, 0, 1, 5, 11, 13, 9, 3, 1, 1, 6, 16, 24, 22, 12, 4, 0, 1, 7, 22, 40, 46, 34, 16, 4, 1, 1, 8, 29, 62, 86, 80, 50, 20, 5, 0, 1, 9, 37, 91, 148, 166, 130, 70, 25, 5, 1, ...}

The row sums are A001045(n+1), n ≥ 0.

{1, 1, 3, 5, 11, 21, 43, 85, 171, 341, 683, 1365, 2731, 5461, 10923, 21845, 43691, 87381, 174763, 349525, 699051, 1398101, 2796203, 5592405, 11184811, 22369621, 44739243, 89478485, ...}
${\displaystyle \sum _{k=0}^{d}c(n,k)={\frac {2^{n+1}-(-1)^{n+1}}{3}},\quad d\geq 0.}$

The row alternating sign sums are A000012(n), n ≥ 0.

${\displaystyle \sum _{k=0}^{d}(-1)^{k}\,c(n,k)=1,\quad d\geq 0.}$
##### Columns of triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients

k = 0: A000012(n), n ≥ 1. Maximal number of pieces formed when "slicing a point" with n cuts. (Since you can't slice a point, you're always left with a point!)

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...}

k = 1: A000027(n), n ≥ 1. Maximal number of pieces formed when slicing a string with n cuts, i.e. n + 1 pieces.

{2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, ...}

k = 2: A000124(n), n ≥ 1. Maximal number of pieces formed when slicing a pancake with n cuts.

{2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, ...}

k = 3: A003600 Maximal number of pieces obtained by slicing a torus (or a bagel) with n cuts: (n^3 + 3 n^2 + 8 n)/6, n ≥ 1. (Both the bagel and the torus are solid!)

{2, 6, 13, 24, 40, 62, 91, 128, 174, 230, 297, 376, 468, 574, 695, 832, 986, 1158, 1349, 1560, 1792, 2046, 2323, 2624, 2950, 3302, 3681, 4088, 4524, 4990, 5487, 6016, 6578, ...}

k = 4: A223718(n), n ≥ 1. Maximal number of pieces obtained by slicing a... ?

{3, 9, 22, 46, 86, 148, 239, 367, 541, ...}

k = 5: A??????(n), n ≥ 1. Maximal number of pieces obtained by slicing a... ?

{3, 12, 34, 80, 166, 314, 553, 920, ...}