Namespaces
Variants
Actions

Difference between revisions of "Binomial coefficients"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
(One intermediate revision by one other user not shown)
Line 1: Line 1:
The coefficients at the powers of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164101.png" /> in the decomposition of the [[Newton binomial|Newton binomial]] <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164102.png" />. The binomial coefficients are denoted by
+
<!--
 +
b0164101.png
 +
$#A+1 = 27 n = 0
 +
$#C+1 = 27 : ~/encyclopedia/old_files/data/B016/B.0106410 Binomial coefficients
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164103.png" /></td> </tr></table>
+
{{TEX|auto}}
 +
{{TEX|done}}
  
or by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164104.png" />, and are given by
+
The coefficients at the powers of  $  z $
 +
in the decomposition of the [[Newton binomial|Newton binomial]]  $  {(1 + z) }  ^ {N} $.  
 +
The binomial coefficients are denoted by
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164105.png" /></td> <td valign="top" style="width:5%;text-align:right;">(1)</td></tr></table>
+
$$
 +
\left ( \begin{array}{c}
 +
N \\
 +
n
 +
\end{array}
 +
  \right )
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164106.png" /></td> </tr></table>
+
or by  $  C _ {N} ^ { n } $,
 +
and are given by
  
The first-mentioned notation is due to L. Euler; the notation <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164107.png" /> appeared in the 19th century, and is probably connected with the interpretation of the binomial coefficients <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164108.png" /> as the number of distinguishable non-ordered combinations (cf. [[Combination|Combination]]) from <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b0164109.png" /> different objects with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641010.png" /> objects in each combination. Binomial coefficients are most conveniently written as numbers in the arithmetical triangle, or [[Pascal triangle|Pascal triangle]], the construction of which is based on the following property of binomial coefficients:
+
$$ \tag{1 }
 +
\left (
 +
\begin{array}{c}
 +
N \\
 +
n
 +
\end{array}
 +
\
 +
\right ) = C _ {N} ^ { n }  = \
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641011.png" /></td> <td valign="top" style="width:5%;text-align:right;">(2)</td></tr></table>
+
\frac{N! }{n! (N-n)! }
 +
=
 +
$$
 +
 
 +
$$
 +
= \
 +
 
 +
\frac{N (N - 1) \dots (N - n + 1) }{n! }
 +
,\  0 \leq  n \leq  N.
 +
$$
 +
 
 +
The first-mentioned notation is due to L. Euler; the notation  $  C _ {N} ^ { n } $
 +
appeared in the 19th century, and is probably connected with the interpretation of the binomial coefficients  $  C _ {N} ^ {n  } $
 +
as the number of distinguishable non-ordered combinations (cf. [[Combination|Combination]]) from  $  N $
 +
different objects with  $  n $
 +
objects in each combination. Binomial coefficients are most conveniently written as numbers in the arithmetical triangle, or [[Pascal triangle|Pascal triangle]], the construction of which is based on the following property of binomial coefficients:
 +
 
 +
$$ \tag{2 }
 +
\left ( \begin{array}{c}
 +
N \\
 +
n
 +
\end{array}
 +
  \right ) + \left ( \begin{array}{c}
 +
N \\
 +
n+1
 +
\end{array}
 +
  \right )  = \
 +
\left ( \begin{array}{c}
 +
N+1 \\
 +
n+1
 +
\end{array}
 +
  \right ) .
 +
$$
  
 
Binomial coefficients, as well as the arithmetical triangle, were known concepts to the mathematicians of antiquity, in more or less developed forms. B. Pascal (l665) conducted a detailed study of binomial coefficients. The binomial coefficients are also connected by many useful relationships other than (2), for example:
 
Binomial coefficients, as well as the arithmetical triangle, were known concepts to the mathematicians of antiquity, in more or less developed forms. B. Pascal (l665) conducted a detailed study of binomial coefficients. The binomial coefficients are also connected by many useful relationships other than (2), for example:
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641012.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3a)</td></tr></table>
+
$$ \tag{3a }
 +
\left ( \begin{array}{c}
 +
N \\
 +
n
 +
\end{array}
 +
  \right )  = \left ( \begin{array}{c}
 +
N \\
 +
N-n
 +
\end{array}
 +
  \right ) ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641013.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3b)</td></tr></table>
+
$$ \tag{3b }
 +
\left ( \begin{array}{c}
 +
N \\
 +
n
 +
\end{array}
 +
  \right )  = \sum _ {k = 0 } ^ { n }
 +
\left ( \begin{array}{c}
 +
m \\
 +
k
 +
\end{array}
 +
  \right ) \left ( \begin{array}{c}
 +
N-m \\
 +
n-k
 +
\end{array}
 +
  \right ) ,\ \
 +
n \leq  m \leq  N - n;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641014.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3c)</td></tr></table>
+
$$ \tag{3c }
 +
\sum _ {k = 0 } ^ { N }  (-1)  ^ {k}
 +
k  ^ {m} \left ( \begin{array}{c}
 +
N \\
 +
k
 +
\end{array}
 +
  \right )  = 0,\ \
 +
m = 0 \dots N - 1 ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641015.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3d)</td></tr></table>
+
$$ \tag{3d }
 +
\sum _ {k = 0 } ^ { N }
 +
\left ( \begin{array}{c}
 +
n \\
 +
k
 +
\end{array}
 +
  \right )  ^ {2}  = \left ( \begin{array}{c}
 +
2n \\
 +
n
 +
\end{array}
 +
  \right ) ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641016.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3e)</td></tr></table>
+
$$ \tag{3e }
 +
\sum _ {k = 0 } ^ { N }
 +
\left ( \begin{array}{c}
 +
N \\
 +
k
 +
\end{array}
 +
  \right ) k (k - 1) \dots (k - r + 1) =
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641017.png" /></td> </tr></table>
+
$$
 +
= \
 +
N (N - 1) \dots (N - r + 1) \cdot 2 ^ {N - r } ;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641018.png" /></td> <td valign="top" style="width:5%;text-align:right;">(3f)</td></tr></table>
+
$$ \tag{3f }
 +
\sum _ {k = 0 } ^ { N }
 +
(-1)  ^ {k} \left ( \begin{array}{c}
 +
N \\
 +
k
 +
\end{array}
 +
  \right ) k (k-1) \dots
 +
(k - r + 1) =  0 .
 +
$$
  
 
In particular, (3a)–(3f) yields
 
In particular, (3a)–(3f) yields
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641019.png" /></td> <td valign="top" style="width:5%;text-align:right;">(4)</td></tr></table>
+
$$ \tag{4 }
 +
\left .
  
The use of the [[Stirling formula|Stirling formula]] yields approximate expressions for binomial coefficients. Thus, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641020.png" /> is much larger than <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641021.png" />:
+
\begin{array}{l}
 +
\sum _ {k = 0 } ^ { N }
 +
\left ( \begin{array}{c}
 +
N \\
 +
k
 +
\end{array}
 +
  \right )  = 2  ^ {N} ;  \\
 +
\sum _ {k = 0 } ^ { N }
 +
(-1)  ^ {k} \left ( \begin{array}{c}
 +
N \\
 +
k
 +
\end{array}
 +
  \right )  = 0. \\
 +
\end{array}
 +
\
 +
\right \}
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641022.png" /></td> </tr></table>
+
The use of the [[Stirling formula|Stirling formula]] yields approximate expressions for binomial coefficients. Thus, if  $  N $
 +
is much larger than  $  n $:
  
In the case of a complex number <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641023.png" />, binomial coefficients are generalized according to the formula
+
$$
 +
\left ( \begin{array}{c}
 +
N \\
 +
n
 +
\end{array}
 +
  \right )  \sim 
 +
\frac{N  ^ {n} }{n! }
 +
.
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641024.png" /></td> </tr></table>
+
In the case of a complex number  $  \alpha $,
 +
binomial coefficients are generalized according to the formula
 +
 
 +
$$
 +
\left (
 +
\begin{array}{c}
 +
\alpha \\
 +
n
 +
\end{array}
 +
\
 +
\right )  = \
 +
 
 +
\frac{\alpha ( \alpha - 1) \dots ( \alpha - n + 1) }{n! }
 +
,\ \
 +
n > 0; \ \
 +
\left (
 +
\begin{array}{c}
 +
\alpha \\
 +
0  
 +
\end{array}
 +
\
 +
\right )  = 1.
 +
$$
  
 
In this generalization, some of the relations (2)–(4) are preserved, but usually in a modified form. For instance,
 
In this generalization, some of the relations (2)–(4) are preserved, but usually in a modified form. For instance,
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641025.png" /></td> </tr></table>
+
$$
 +
\left (
 +
\begin{array}{c}
 +
\alpha \\
 +
n
 +
\end{array}
 +
\
 +
\right ) + \left (
 +
\begin{array}{c}
 +
\alpha \\
 +
n + 1
 +
\end{array}
 +
\
 +
\right )  = \left (
 +
\begin{array}{c}
 +
{\alpha + 1 } \\
 +
{n + 1 }
 +
\end{array}
 +
\
 +
\right ) ;
 +
$$
 +
 
 +
$$
 +
\sum _ {k = 0 } ^ { {+ }  \infty } \left ( \begin{array}{c}
 +
\alpha \\
 +
k
 +
\end{array}
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641026.png" /></td> </tr></table>
+
\right )  = 2  ^  \alpha  ,\  \mathop{\rm Re}  \alpha > -1;
 +
$$
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/b/b016/b016410/b01641027.png" /></td> </tr></table>
+
$$
 +
\sum _ {k = 0 } ^ { {+ }  \infty } (-1)  ^ {k} \left ( \begin{array}{c}
 +
\alpha \\
 +
k
 +
\end{array}
 +
  \right )  = 0,\  \mathop{\rm Re}  \alpha > 0.
 +
$$
  
 
For tables of binomial coefficients see [[#References|[2]]], [[#References|[3]]].
 
For tables of binomial coefficients see [[#References|[2]]], [[#References|[3]]].
  
 
====References====
 
====References====
<table><TR><TD valign="top">[1]</TD> <TD valign="top">  G.A. Korn,  T.M. Korn,  "Mathematical handbook for scientists and engineers" , McGraw-Hill  (1968)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top">  L.N. Bol'shev,  N.V. Smirnov,  "Tables of mathematical statistics" , ''Libr. math. tables'' , '''46''' , Nauka  (1983)  (In Russian)  (Processed by L.S. Bark and E.S. Kedrova)</TD></TR><TR><TD valign="top">[3]</TD> <TD valign="top"> , ''Table of binomial coefficients'' , Cambridge, Mass.  (1954)</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[1]</TD> <TD valign="top">  G.A. Korn,  T.M. Korn,  "Mathematical handbook for scientists and engineers" , McGraw-Hill  (1968) {{ZBL|0177.29301}}</TD></TR>
 +
<TR><TD valign="top">[2]</TD> <TD valign="top">  L.N. Bol'shev,  N.V. Smirnov,  "Tables of mathematical statistics" , ''Libr. math. tables'' , '''46''' , Nauka  (1983)  (In Russian)  (Processed by L.S. Bark and E.S. Kedrova) {{ZBL|0529.62099}}</TD></TR>
 +
<TR><TD valign="top">[3]</TD> <TD valign="top"> J.C.P. Miller (ed.) "Table of binomial coefficients". Royal Society Mathematical Tables '''3''' Cambridge University Press (1954) {{ZBL|0059.11301}}</TD></TR>
 +
</table>

Latest revision as of 10:59, 29 May 2020


The coefficients at the powers of $ z $ in the decomposition of the Newton binomial $ {(1 + z) } ^ {N} $. The binomial coefficients are denoted by

$$ \left ( \begin{array}{c} N \\ n \end{array} \right ) $$

or by $ C _ {N} ^ { n } $, and are given by

$$ \tag{1 } \left ( \begin{array}{c} N \\ n \end{array} \ \right ) = C _ {N} ^ { n } = \ \frac{N! }{n! (N-n)! } = $$

$$ = \ \frac{N (N - 1) \dots (N - n + 1) }{n! } ,\ 0 \leq n \leq N. $$

The first-mentioned notation is due to L. Euler; the notation $ C _ {N} ^ { n } $ appeared in the 19th century, and is probably connected with the interpretation of the binomial coefficients $ C _ {N} ^ {n } $ as the number of distinguishable non-ordered combinations (cf. Combination) from $ N $ different objects with $ n $ objects in each combination. Binomial coefficients are most conveniently written as numbers in the arithmetical triangle, or Pascal triangle, the construction of which is based on the following property of binomial coefficients:

$$ \tag{2 } \left ( \begin{array}{c} N \\ n \end{array} \right ) + \left ( \begin{array}{c} N \\ n+1 \end{array} \right ) = \ \left ( \begin{array}{c} N+1 \\ n+1 \end{array} \right ) . $$

Binomial coefficients, as well as the arithmetical triangle, were known concepts to the mathematicians of antiquity, in more or less developed forms. B. Pascal (l665) conducted a detailed study of binomial coefficients. The binomial coefficients are also connected by many useful relationships other than (2), for example:

$$ \tag{3a } \left ( \begin{array}{c} N \\ n \end{array} \right ) = \left ( \begin{array}{c} N \\ N-n \end{array} \right ) ; $$

$$ \tag{3b } \left ( \begin{array}{c} N \\ n \end{array} \right ) = \sum _ {k = 0 } ^ { n } \left ( \begin{array}{c} m \\ k \end{array} \right ) \left ( \begin{array}{c} N-m \\ n-k \end{array} \right ) ,\ \ n \leq m \leq N - n; $$

$$ \tag{3c } \sum _ {k = 0 } ^ { N } (-1) ^ {k} k ^ {m} \left ( \begin{array}{c} N \\ k \end{array} \right ) = 0,\ \ m = 0 \dots N - 1 ; $$

$$ \tag{3d } \sum _ {k = 0 } ^ { N } \left ( \begin{array}{c} n \\ k \end{array} \right ) ^ {2} = \left ( \begin{array}{c} 2n \\ n \end{array} \right ) ; $$

$$ \tag{3e } \sum _ {k = 0 } ^ { N } \left ( \begin{array}{c} N \\ k \end{array} \right ) k (k - 1) \dots (k - r + 1) = $$

$$ = \ N (N - 1) \dots (N - r + 1) \cdot 2 ^ {N - r } ; $$

$$ \tag{3f } \sum _ {k = 0 } ^ { N } (-1) ^ {k} \left ( \begin{array}{c} N \\ k \end{array} \right ) k (k-1) \dots (k - r + 1) = 0 . $$

In particular, (3a)–(3f) yields

$$ \tag{4 } \left . \begin{array}{l} \sum _ {k = 0 } ^ { N } \left ( \begin{array}{c} N \\ k \end{array} \right ) = 2 ^ {N} ; \\ \sum _ {k = 0 } ^ { N } (-1) ^ {k} \left ( \begin{array}{c} N \\ k \end{array} \right ) = 0. \\ \end{array} \ \right \} $$

The use of the Stirling formula yields approximate expressions for binomial coefficients. Thus, if $ N $ is much larger than $ n $:

$$ \left ( \begin{array}{c} N \\ n \end{array} \right ) \sim \frac{N ^ {n} }{n! } . $$

In the case of a complex number $ \alpha $, binomial coefficients are generalized according to the formula

$$ \left ( \begin{array}{c} \alpha \\ n \end{array} \ \right ) = \ \frac{\alpha ( \alpha - 1) \dots ( \alpha - n + 1) }{n! } ,\ \ n > 0; \ \ \left ( \begin{array}{c} \alpha \\ 0 \end{array} \ \right ) = 1. $$

In this generalization, some of the relations (2)–(4) are preserved, but usually in a modified form. For instance,

$$ \left ( \begin{array}{c} \alpha \\ n \end{array} \ \right ) + \left ( \begin{array}{c} \alpha \\ n + 1 \end{array} \ \right ) = \left ( \begin{array}{c} {\alpha + 1 } \\ {n + 1 } \end{array} \ \right ) ; $$

$$ \sum _ {k = 0 } ^ { {+ } \infty } \left ( \begin{array}{c} \alpha \\ k \end{array} \right ) = 2 ^ \alpha ,\ \mathop{\rm Re} \alpha > -1; $$

$$ \sum _ {k = 0 } ^ { {+ } \infty } (-1) ^ {k} \left ( \begin{array}{c} \alpha \\ k \end{array} \right ) = 0,\ \mathop{\rm Re} \alpha > 0. $$

For tables of binomial coefficients see [2], [3].

References

[1] G.A. Korn, T.M. Korn, "Mathematical handbook for scientists and engineers" , McGraw-Hill (1968) Zbl 0177.29301
[2] L.N. Bol'shev, N.V. Smirnov, "Tables of mathematical statistics" , Libr. math. tables , 46 , Nauka (1983) (In Russian) (Processed by L.S. Bark and E.S. Kedrova) Zbl 0529.62099
[3] J.C.P. Miller (ed.) "Table of binomial coefficients". Royal Society Mathematical Tables 3 Cambridge University Press (1954) Zbl 0059.11301
How to Cite This Entry:
Binomial coefficients. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Binomial_coefficients&oldid=18917
This article was adapted from an original article by E.D. Solomentsev (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article