Binomial coefficients

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

This article needs more work.

Please help by expanding it!

A binomial coefficient

( ⁿ_k )

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 ( ⁵₃ ) = 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

( ⁿ₀ ) = ( ⁿ_n ) = 1

(the empty set in the former case, the complete set in the latter) and

( ⁿ₁ ) = ( ⁿ_{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.

1 Pascal’s triangle and binomial coefficients
2 Individuals of generation k after n population doublings
3 Good binomial coefficients
4 Exceptional binomial coefficients
5 Sums of binomial coefficients
- 5.1 Generating functions for sums of binomial coefficients
  - 5.1.1 Triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients
    - 5.1.1.1 Rows of triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients
    - 5.1.1.2 Columns of triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients
6 See also
7 Notes
8 External links

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

) x d :=

n

∑

d = 0

n!

d ! (n − d )!

x d =

n

∑

d = 0

T (n, d ) x d, 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

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

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

.

Good binomial coefficients

(...)

Exceptional binomial coefficients

(...)

Sums of binomial coefficients

∑

d

k = 0

( ⁿ_k ) , 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

∑

( ⁿ_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.:

1

1 − x

.

A000027

∑

( ⁿ_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.:

1

(1 − x) 2

.

(With offset 1, O.g.f.:

x

(1 − x) 2

.)

A000124

∑

( ⁿ_k ) , k = 0 .. 9, n ≥ 0. (

n (n − 1)

2

+ n + 1, n ≥ 0.)

Central polygonal numbers (the Lazy Caterer’s sequence):

( ^{n + 1}₂ ) + 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

∑

( ⁿ_k ) , k = 0 .. 3, n ≥ 0.

Cake numbers: maximal number of pieces resulting from

n

planar cuts through a cube (or cake):

( ^{n + 1}₃ ) + n + 1

.

O.g.f.:

(1 − 2 x + 2 x 2 ) / (1 − x) 4.

A000127

∑

( ⁿ_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.:

(1 − 3 x + 4 x 2 − 2 x 3 + x 4 ) / (1 − x) 5.

A006261

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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

∑

( ⁿ_k ) , 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
( ⁿ_k ) , 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

0

1

2

1

3

1

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

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

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

External links

Why is there no explicit formula for the factorial?—StackExchange: Mathematics.

[BinomialCoefficient-1] Weisstein, Eric W., Binomial Coefficient, from MathWorld—A Wolfram Web Resource..

[1]

Binomial coefficients

Contents

Pascal’s triangle and binomial coefficients

Individuals of generation k after n population doublings

Good binomial coefficients

Exceptional binomial coefficients

Sums of binomial coefficients

Generating functions for sums of binomial coefficients

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

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

Columns of triangle of coefficients of numerator polynomial of generating functions for sums of binomial coefficients

See also

Notes

External links

Navigation menu

Views

Personal tools

Navigation

Search

Tools