This site is supported by donations to The OEIS Foundation.

Binomial coefficients

From OeisWiki
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 !  (nk )!
  ,

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 !  (nd  )!
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
2n  −  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
2n  −  1
, append a shifted down (by one row) copy of the pattern from 0 to
2n  − 1  −  1
to the right of the pattern from 0 to
2n  − 1  −  1
.

Good binomial coefficients

(...)

Exceptional binomial coefficients

(...)

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 , 2k  ), 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.:
(1 − 4 x + 7 x 2 − 6 x 3 + 3 x 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.:
(1 − 5 x + 11 x 2 − 13 x 3 + 9 x 4 − 3 x 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.:
(1 − 6 x + 16 x 2 − 24 x 3 + 22 x 4 − 12 x 5 + 4 x 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.:
(1 − 7 x + 22 x 2 − 40 x 3 + 46 x 4 − 34 x 5 + 16 x 6 − 4 x 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.:
(1 − 8 x + 29 x 2 − 62 x 3 + 86 x 4 − 80 x 5 + 50 x 6 − 20 x 7 + 5 x 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.:
(1 − 9 x + 37 x 2 − 91 x 3 + 148 x 4 − 166 x 5 + 130 x 6 − 70 x 7 + 25 x 8 − 5 x 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.:
(1 − 10 x + 46 x 2 − 128 x 3 + 239 x 4 − 314 x 5 + 296 x 6 − 200 x 7 + 95 x 8 − 30 x 9 + 6 x 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.:
(1 − 11 x + 56 x 2 − 174 x 3 + 367 x 4 − 553 x 5 + 610 x 6 − 496 x 7 + 295 x 8 − 125 x 9 + 36 x 10 − 6 x 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

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


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
xi y  j
in
1 / (1  −  x  −  xy  −  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
)  = 
2n +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, ...}

See also

Notes

  1. Weisstein, Eric W., Binomial Coefficient, from MathWorld—A Wolfram Web Resource..

External links