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!


(Improve presentation)[1]

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

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

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

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

(1 + x)n  = 
n
d  = 0
  
( nd  ) 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
C (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 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): C(n+1, 2) + 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): C(n+1, 3) + 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.: .
A008859

( nk  ), k = 0 .. 6, n   ≥   0.
Maximal number of regions in 6-space formed by
n  −  1
5-D hyperplanes?
O.g.f.: .
A008860

( nk  ), k = 0 .. 7, n   ≥   0.
Maximal number of regions in 7-space formed by
n  −  1
6-D hyperplanes?
O.g.f.: .
A008861

( nk  ), k = 0 .. 8, n   ≥   0.
Maximal number of regions in 8-space formed by
n  −  1
7-D hyperplanes?
O.g.f.: .
A008862

( nk  ), k = 0 .. 9, n   ≥   0.
Maximal number of regions in 9-space formed by
n  −  1
8-D hyperplanes?
O.g.f.: .
A008863

( nk  ), k = 0 .. 10, n   ≥   0.
Maximal number of regions in 10-space formed by
n  −  1
9-D hyperplanes?
O.g.f.: .
A219531

( nk  ), k = 0 .. 11, n   ≥   0.
Maximal number of regions in 11-space formed by
n  −  1
10-D hyperplanes?
O.g.f.: .
A219615

( nk  ), k = 0 .. 12, n   ≥   0.
Maximal number of regions in 12-space formed by
n  −  1
11-D hyperplanes?
O.g.f.: .

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

The row alternating sign sums are A000012(n), n ≥ 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. Improve presentation.
  2. Weisstein, Eric W., Binomial Coefficient, from MathWorld—A Wolfram Web Resource. [http://mathworld.wolfram.com/BinomialCoefficient.html].