Editing Binomial coefficient (section)

== Computing the value of binomial coefficients ==
Several methods exist to compute the value of <math>\tbinom{n}{k}</math> without actually expanding a binomial power or counting {{mvar|k}}-combinations.

=== Recursive formula ===
One method uses the [[recursion|recursive]], purely additive formula
<math display="block"> \binom nk = \binom{n-1}{k-1} + \binom{n-1}k</math> for all integers <math>n,k</math> such that <math>1 \le k < n,</math>
with boundary values
<math display="block">\binom n0 = \binom nn = 1</math>
for all integers {{math|1=''n'' ≥ 0}}.

The formula follows from considering the set {{math|{{mset|1, 2, 3, ..., ''n''}}}} and counting separately (a) the {{mvar|k}}-element groupings that include a particular set element, say "{{mvar|i}}", in every group (since "{{mvar|i}}" is already chosen to fill one spot in every group, we need only choose {{math|''k'' − 1}} from the remaining {{math|''n'' − 1}}) and (b) all the ''k''-groupings that don't include "{{mvar|i}}"; this enumerates all the possible {{mvar|k}}-combinations of {{mvar|n}} elements. It also follows from tracing the contributions to ''X''<sup>''k''</sup> in {{math|(1 + ''X'')<sup>''n''−1</sup>(1 + ''X'')}}. As there is zero {{math|''X''<sup>''n''+1</sup>}} or {{math|''X''<sup>−1</sup>}} in {{math|(1 + ''X'')<sup>''n''</sup>}}, one might extend the definition beyond the above boundaries to include <math>\tbinom nk = 0</math> when either {{math|''k'' > ''n''}} or {{math|''k'' < 0}}. This recursive formula then allows the construction of [[Pascal's triangle]], surrounded by white spaces where the zeros, or the trivial coefficients, would be.

=== Multiplicative formula ===
A more efficient method to compute individual binomial coefficients is given by the formula
<math display="block">\binom nk = \frac{n^{\underline{k}}}{k!} = \frac{n(n-1)(n-2)\cdots(n-(k-1))}{k(k-1)(k-2)\cdots 1} =  \prod_{i=1}^k\frac{ n+1-i}{ i},</math>
where the numerator of the first fraction, <math>n^{\underline{k}}</math>, is a [[falling factorial]].
This formula is easiest to understand for the combinatorial interpretation of binomial coefficients.
The numerator gives the number of ways to select a sequence of {{mvar|k}} distinct objects, retaining the order of selection, from a set of {{mvar|n}} objects. The denominator counts the number of distinct sequences that define the same {{mvar|k}}-combination when order is disregarded. This formula can also be stated in a recursive form. Using the "C" notation from above, <math>C_{n,k} = C_{n, k-1} \cdot (n-k+1) / k</math>, where <math>C_{n,0} = 1</math>. It is readily derived by evaluating <math>C_{n,k} / C_{n, k-1}</math> and can intuitively be understood as starting at the leftmost coefficient of the <math>n</math>-th row of [[Pascal's triangle]], whose value is always <math>1</math>, and recursively computing the next coefficient to its right until the <math>k</math>-th one is reached.

Due to the symmetry of the [[Pascal's triangle|binomial coefficients]] with regard to {{mvar|k}} and {{math|''n'' − ''k''}}, calculation of the above product, as well as the recursive relation, may be optimised by setting its upper limit to the smaller of {{mvar|k}} and {{math|''n'' − ''k''}}.

=== Factorial formula ===
Finally, though computationally unsuitable, there is the compact form, often used in proofs and derivations, which makes repeated use of the familiar [[factorial]] function:
<math display="block"> \binom nk = \frac{n!}{k!\,(n-k)!} \quad \text{for }\ 0\leq k\leq n,</math>
where {{math|''n''!}} denotes the factorial of {{mvar|n}}. This formula follows from the multiplicative formula above by multiplying numerator and denominator by {{math|(''n'' − ''k'')!}}; as a consequence it involves many factors common to numerator and denominator. It is less practical for explicit computation (in the case that {{mvar|k}} is small and {{mvar|n}} is large) unless common factors are first cancelled (in particular since factorial values grow very rapidly). The formula does exhibit a symmetry that is less evident from the multiplicative formula (though it is from the definitions)
{{NumBlk2|:|<math> \binom nk = \binom n{n-k} \quad \text{for }\ 0\leq k\leq n,</math>|1}}
which leads to a more efficient multiplicative computational routine. Using the [[Pochhammer symbol|falling factorial notation]],
<math display="block"> \binom nk =
\begin{cases}
 n^{\underline{k}}/k! & \text{if }\ k \le \frac{n}{2} \\
 n^{\underline{n-k}}/(n-k)! & \text{if }\ k > \frac{n}{2}
\end{cases}.
</math>

=== Generalization and connection to the binomial series ===
{{Main|Binomial series}}
The multiplicative formula allows the definition of binomial coefficients to be extended<ref>See {{Harv|Graham|Knuth|Patashnik|1994}}, which also defines <math>\tbinom n k = 0</math> for <math>k<0</math>. Alternative generalizations, such as to [[#Two real or complex valued arguments|two real or complex valued arguments]] using the [[Gamma function]] assign nonzero values to <math>\tbinom n k</math> for <math>k < 0</math>, but this causes most binomial coefficient identities to fail, and thus is not widely used by the majority of definitions. One such choice of nonzero values leads to the aesthetically pleasing "Pascal windmill" in Hilton, Holton and Pedersen, ''Mathematical reflections: in a room with many mirrors'', Springer, 1997, but causes even [[Pascal's identity]] to fail (at the origin).</ref> by replacing ''n'' by an arbitrary number ''α'' (negative, real, complex) or even an element of any [[commutative ring]] in which all positive integers are invertible:
<math display="block">\binom \alpha k = \frac{\alpha^{\underline k}}{k!} = \frac{\alpha(\alpha-1)(\alpha-2)\cdots(\alpha-k+1)}{k(k-1)(k-2)\cdots 1}
\quad\text{for } k\in\N \text{ and arbitrary } \alpha.
</math>

With this definition one has a generalization of the binomial formula (with one of the variables set to 1), which justifies still calling the <math>\tbinom\alpha k</math> binomial coefficients:
{{NumBlk2|:|<math> (1+X)^\alpha = \sum_{k=0}^\infty {\alpha \choose k} X^k.</math>|2}}

This formula is valid for all complex numbers ''α'' and ''X'' with |''X''|&nbsp;&lt;&nbsp;1. It can also be interpreted as an identity of [[formal power series]] in ''X'', where it actually can serve as definition of arbitrary powers of [[power series]] with constant coefficient equal to&nbsp;1; the point is that with this definition all identities hold that one expects for [[exponentiation]], notably
<math display="block">(1+X)^\alpha(1+X)^\beta=(1+X)^{\alpha+\beta} \quad\text{and}\quad ((1+X)^\alpha)^\beta=(1+X)^{\alpha\beta}.</math>

If ''α'' is a nonnegative integer ''n'', then all terms with {{math|''k'' &gt; ''n''}} are zero,<ref>When <math>\alpha = n</math> is a nonnegative integer, <math>\textstyle \binom{n}{k} = 0</math> for <math>k > n</math> because the <math>(k = n+1)</math>-th factor of the numerator is <math>n - (n+1) + 1 = 0</math>. Thus, the <math>k</math>-th term is a [[Zero-product property|zero product]] for all <math>k \geq n + 1</math>.</ref> and the infinite series becomes a finite sum, thereby recovering the binomial formula. However, for other values of ''α'', including negative integers and rational numbers, the series is really infinite.