This site is supported by donations to The OEIS Foundation.

# Binomial coefficients

(Redirected from Binomial coefficient)
Jump to: navigation, search

This article page is a stub, please help by expanding it.

This article needs more work.

Please help by expanding it!

A binomial coefficient
 (  nk  )
tells us how many ways there are of picking
 k
elements out of a set of
 n
elements, without regard to order. For example, to pick 3 numbers from a set of 5 numbers ({1, 2, 3, 4, 5} for this example), there are (  53  ) = 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

(
 n k
) :=
 n! k !  (n − k )!
,

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

Of course
 (  n0  )  = (  nn  )  = 1
(the empty set in the former case, the complete set in the latter) and
 (  n1  )  = (  nn  −  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,[1] i.e. the coefficients of the expanded binomial

(1 + x)n  =
 n ∑ d  = 0

(
 n d
) xd   :=
 n ∑ d  = 0

 n! d !  (n − d  )!
xd  =
 n ∑ d  = 0

T  (n, d  ) xd, n ≥ 0,

which is the generating function for the
 n
th row (finite sequence) of Pascal’s triangle.

## Individuals of generation k after n population doublings

The binomial coefficients
 (  nk  )
give the number of individuals of the
 k
th generation after
 n
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
 2 n  −  1
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
 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
.

(...)

(...)

## Sums of binomial coefficients

 d

 k  = 0
(  nk  ), n   ≥   0.
(Where
 d
is the degree of the uniquely determined polynomial of degree
 d
passing through points
 (k, 2 k), k = 0 .. d
.)

 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
 ∑
(  nk  ), 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.:
 1 1  −  x
.
A000027
 ∑
(  nk  ), 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.:
 1 (1  −  x) 2
.
(With offset 1, O.g.f.:
 x (1  −  x) 2
.)
A000124
 ∑
(  nk  ), k = 0 .. 9, n   ≥   0. (
 n  (n  −  1) 2
+ n + 1, n   ≥   0.)
Central polygonal numbers (the Lazy Caterer’s sequence):
 (  n + 12  )  + 1
; or, maximal number of pieces formed when slicing a pancake with
 n
cuts.
O.g.f.:
 1  −  x + x 2 (1  −  x) 3
.
A000125
 ∑
(  nk  ), k = 0 .. 3, n   ≥   0.
Cake numbers: maximal number of pieces resulting from
 n
planar cuts through a cube (or cake):
 (  n + 13  )  + n + 1
.
O.g.f.:
 1  −  2 x + 2 x 2 (1  −  x) 4
.
A000127
 ∑
(  nk  ), 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.:
 1  −  3 x + 4 x 2  −  2 x 3 + x 4 (1  −  x) 5
.
A006261
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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
 ∑
(  nk  ), 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

Coefficients
 c (d, k )
of numerator polynomial of o.g.f.
 d

 k  = 0
c (d, k ) ( − x)k
(1  −  x)d +1
for
 d

 k  = 0
(  nk  ), n   ≥   0
.
 c (d, 0) = 1; c (d, d ) = (d + 1) mod 2; c (d, k ) = c (d  −  1, k  −  1) + c (d  −  1, k ), 0 < k < d.

 d

 d

 k  = 0
T  (d, k)

0   1
1
1   1 0
1
2   1 1 1
3
3   1 2 2 0
5
4   1 3 4 2 1
11
5 1 4 7 6 3 0
21
6   1 5 11 13 9 3 1
43
7   1 6 16 24 22 12 4 0
85
8   1 7 22 40 46 34 16 4 1
171
9   1 8 29 62 86 80 50 20 5 0
341
10 1 9 37 91 148 166 130 70 25 5 1
683
11   1 10 46 128 239 314 296 200 95 30 6 0
1365
12   1 11 56 174 367 553 610 496 295 125 36 6 1
2731

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, ...}

 d ∑ k  = 0

(
 n k
)  =
 2 n +1 − (−1)  n +1 3
, d ≥ 0.

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

 d ∑ k  = 0

(−1)k (
 n k
)  =  1, d ≥ 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, ...}

## Notes

1. Weisstein, Eric W., Binomial Coefficient, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/BinomialCoefficient.html].