Editing Binomial coefficient (section)

== Generalizations ==
=== Generalization to multinomials ===
{{main|Multinomial theorem}}
Binomial coefficients can be generalized to '''multinomial coefficients''' defined to be the number:
: <math>{n\choose k_1,k_2,\ldots,k_r} =\frac{n!}{k_1!k_2!\cdots k_r!}</math>
where
: <math>\sum_{i=1}^rk_i=n.</math>

While the binomial coefficients represent the coefficients of {{math|(''x'' + ''y'')<sup>''n''</sup>}}, the multinomial coefficients
represent the coefficients of the polynomial
: <math>(x_1 + x_2 + \cdots + x_r)^n.</math>
The case ''r'' = 2 gives binomial coefficients:
: <math>{n\choose k_1,k_2}={n\choose k_1, n-k_1}={n\choose k_1}= {n\choose k_2}.</math>

The combinatorial interpretation of multinomial coefficients is distribution of ''n'' distinguishable elements over ''r'' (distinguishable) containers, each containing exactly ''k<sub>i</sub>'' elements, where ''i'' is the index of the container.

Multinomial coefficients have many properties similar to those of binomial coefficients, for example the recurrence relation:
: <math>{n\choose k_1,k_2,\ldots,k_r} ={n-1\choose k_1-1,k_2,\ldots,k_r}+{n-1\choose k_1,k_2-1,\ldots,k_r}+\ldots+{n-1\choose k_1,k_2,\ldots,k_r-1}</math>
and symmetry:
: <math>{n\choose k_1,k_2,\ldots,k_r} ={n\choose k_{\sigma_1},k_{\sigma_2},\ldots,k_{\sigma_r}}</math>
where <math>(\sigma_i)</math> is a [[permutation]] of (1, 2, ..., ''r'').

=== Taylor series ===
Using [[Stirling numbers of the first kind]] the [[Taylor series|series expansion]] around any arbitrarily chosen point <math>z_0</math> is
: <math>\begin{align} {z \choose k} = \frac{1}{k!}\sum_{i=0}^k z^i s_{k,i}&=\sum_{i=0}^k (z- z_0)^i \sum_{j=i}^k {z_0 \choose j-i} \frac{s_{k+i-j,i}}{(k+i-j)!} \\ &=\sum_{i=0}^k (z-z_0)^i \sum_{j=i}^k z_0^{j-i} {j \choose i} \frac{s_{k,j}}{k!}.\end{align}</math>

=== Binomial coefficient with {{math|1=''n'' = 1/2}} ===
The definition of the binomial coefficients can be extended to the case where <math>n</math> is real and <math>k</math> is integer.

In particular, the following identity holds for any non-negative integer <math>k</math>:
: <math>{{1/2}\choose{k}}={{2k}\choose{k}}\frac{(-1)^{k+1}}{2^{2k}(2k-1)}.</math>

This shows up when expanding <math>\sqrt{1+x}</math> into a power series using the Newton binomial series :
: <math>\sqrt{1+x}=\sum_{k\geq 0}{\binom{1/2}{k}}x^k.</math>

=== Products of binomial coefficients ===
One can express the product of two binomial coefficients as a linear combination of binomial coefficients:
: <math>{z \choose m} {z\choose n} = \sum_{k=0}^{\min(m,n)} {m + n - k \choose k, m - k, n - k} {z \choose m + n - k},</math>

where the connection coefficients are [[Multinomial theorem|multinomial coefficients]]. In terms of labelled combinatorial objects, the connection coefficients represent the number of ways to assign {{math|''m'' + ''n'' − ''k''}} labels to a pair of labelled combinatorial objects—of weight ''m'' and ''n'' respectively—that have had their first ''k'' labels identified, or glued together to get a new labelled combinatorial object of weight {{math|''m'' + ''n'' − ''k''}}. (That is, to separate the labels into three portions to apply to the glued part, the unglued part of the first object, and the unglued part of the second object.) In this regard, binomial coefficients are to exponential generating series what [[falling factorial]]s are to ordinary generating series.

The product of all binomial coefficients in the ''n''th row of the Pascal triangle is given by the formula:
: <math>\prod_{k=0}^{n}\binom{n}{k}=\prod_{k=1}^{n}k^{2k-n-1}.</math>

=== Partial fraction decomposition ===
The [[partial fraction decomposition]] of the reciprocal is given by
: <math>\frac{1}{{z \choose n}}= \sum_{i=0}^{n-1} (-1)^{n-1-i} {n \choose i} \frac{n-i}{z-i},
\qquad \frac{1}{{z+n \choose n}}= \sum_{i=1}^n (-1)^{i-1} {n \choose i} \frac{i}{z+i}.</math>

=== Newton's binomial series ===
{{main|Binomial series}}
Newton's binomial series, named after [[Sir Isaac Newton]], is a generalization of the binomial theorem to infinite series:
: <math> (1+z)^{\alpha} = \sum_{n=0}^{\infty}{\alpha\choose n}z^n = 1+{\alpha\choose1}z+{\alpha\choose 2}z^2+\cdots.</math>

The identity can be obtained by showing that both sides satisfy the [[differential equation]] {{math|1=(1 + ''z'') ''f'''(''z'') = ''α'' ''f''(''z'')}}.

The [[radius of convergence]] of this series is 1. An alternative expression is
: <math>\frac{1}{(1-z)^{\alpha+1}} = \sum_{n=0}^{\infty}{n+\alpha \choose n}z^n</math>
where the identity
: <math>{n \choose k} = (-1)^k {k-n-1 \choose k}</math>
is applied.

=== Multiset (rising) binomial coefficient ===
{{main|Multichoose#Counting multisets}}
Binomial coefficients count subsets of prescribed size from a given set. A related combinatorial problem is to count [[multiset]]s of prescribed size with elements drawn from a given set, that is, to count the number of ways to select a certain number of elements from a given set with the possibility of selecting the same element repeatedly. The resulting numbers are called ''[[Multiset#Counting multisets|multiset coefficients]]'';<ref>
{{citation
 | last = Munarini | first = Emanuele
 | doi = 10.2298/AADM110609014M
 | issue = 2
 | journal = Applicable Analysis and Discrete Mathematics
 | mr = 2867317
 | pages = 176–200
 | title = Riordan matrices and sums of harmonic numbers
 | volume = 5
 | year = 2011| url = http://www.doiserbia.nb.rs/img/doi/1452-8630/2011/1452-86301100014M.pdf
}}.</ref> the number of ways to "multichoose" (i.e., choose with replacement) ''k'' items from an ''n'' element set is denoted <math display="inline">\left(\!\!\binom n k\!\!\right)</math>.

To avoid ambiguity and confusion with ''n'''s main denotation in this article,<br /> let {{math|1=''f'' = ''n'' = ''r'' + (''k'' − 1)}} and {{math|1=''r'' = ''f'' − (''k'' − 1)}}.

Multiset coefficients may be expressed in terms of binomial coefficients by the rule
<math display="block">\binom{f}{k}=\left(\!\!\binom{r}{k}\!\!\right)=\binom{r+k-1}{k}.</math>
One possible alternative characterization of this identity is as follows:
We may define the [[falling factorial]] as
<math display="block">(f)_{k}=f^{\underline k}=(f-k+1)\cdots(f-3)\cdot(f-2)\cdot(f-1)\cdot f,</math>
and the corresponding rising factorial as
<math display="block">r^{(k)}=\,r^{\overline k}=\,r\cdot(r+1)\cdot(r+2)\cdot(r+3)\cdots(r+k-1);</math>
so, for example,
<math display="block">17\cdot18\cdot19\cdot20\cdot21=(21)_{5}=21^{\underline 5}=17^{\overline 5}=17^{(5)}.</math>
Then the binomial coefficients may be written as
<math display="block">\binom{f}{k} = \frac{(f)_{k}}{k!} =\frac{(f-k+1)\cdots(f-2)\cdot(f-1)\cdot f}{1\cdot2\cdot3\cdot4\cdot5\cdots k} ,</math>
while the corresponding multiset coefficient is defined by replacing the falling with the rising factorial:
<math display="block">\left(\!\!\binom{r}{k}\!\!\right)=\frac{r^{(k)}}{k!}=\frac{r\cdot(r+1)\cdot(r+2)\cdots(r+k-1)}{1\cdot2\cdot3\cdot4\cdot5\cdots k}.</math>

==== Generalization to negative integers ''n'' ====
{{Pascal_triangle_extended.svg}}
For any ''n'',
: <math>\begin{align}\binom{-n}{k} &= \frac{-n\cdot-(n+1)\dots-(n+k-2)\cdot-(n+k-1)}{k!}\\
&=(-1)^k\;\frac{n\cdot(n+1)\cdot(n+2)\cdots (n + k - 1)}{k!}\\
&=(-1)^k\binom{n + k - 1}{k}\\
&=(-1)^k\left(\!\!\binom{n}{k}\!\!\right)\;.\end{align}</math>
In particular, binomial coefficients evaluated at negative integers ''n'' are given by signed multiset coefficients. In the special case <math>n = -1</math>, this reduces to <math>(-1)^k=\binom{-1}{k}=\left(\!\!\binom{-k}{k}\!\!\right) .</math>

For example, if ''n'' = −4 and ''k'' = 7, then ''r'' = 4 and ''f'' = 10:
: <math>\begin{align}\binom{-4}{7} &= \frac
{-10\cdot-9\cdot-8\cdot-7\cdot-6\cdot-5\cdot-4}
{1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7}\\
&=(-1)^7\;\frac{4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10}
{1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot7}\\
&=\left(\!\!\binom{-7}{7}\!\!\right)\left(\!\!\binom{4}{7}\!\!\right)=\binom{-1}{7}\binom{10}{7}.\end{align}</math>

=== Two real or complex valued arguments ===
The binomial coefficient is generalized to two real or complex valued arguments using the [[gamma function]] or [[beta function]] via
: <math>{x \choose y}= \frac{\Gamma(x+1)}{\Gamma(y+1) \Gamma(x-y+1)}= \frac{1}{(x+1) \Beta(y+1, x-y+1)}.</math>
This definition inherits these following additional properties from <math>\Gamma</math>:
: <math>{x \choose y}= \frac{\sin (y \pi)}{\sin(x \pi)} {-y-1 \choose -x-1}= \frac{\sin((x-y) \pi)}{\sin (x \pi)} {y-x-1 \choose y};</math>
moreover,
: <math>{x \choose y} \cdot {y \choose x}= \frac{\sin((x-y) \pi)}{(x-y) \pi}.</math>

The resulting function has been little-studied, apparently first being graphed in {{Harv|Fowler|1996}}. Notably, many binomial identities fail: <math display="inline">\binom{n }{ m} = \binom{n }{ n-m}</math> but <math display="inline">\binom{-n}{m} \neq \binom{-n}{-n-m}</math> for ''n'' positive (so <math>-n</math> negative). The behavior is quite complex, and markedly different in various octants (that is, with respect to the ''x'' and ''y'' axes and the line <math>y=x</math>), with the behavior for negative ''x'' having singularities at negative integer values and a checkerboard of positive and negative regions:
* in the octant <math>0 \leq y \leq x</math> it is a smoothly interpolated form of the usual binomial, with a ridge ("Pascal's ridge").
* in the octant <math>0 \leq x \leq y</math> and in the quadrant <math>x \geq 0, y \leq 0</math> the function is close to zero.
* in the quadrant <math>x \leq 0, y \geq 0</math> the function is alternatingly very large positive and negative on the parallelograms with vertices <math display="block">(-n,m+1), (-n,m), (-n-1,m-1), (-n-1,m)</math>
* in the octant <math>0 > x > y</math> the behavior is again alternatingly very large positive and negative, but on a square grid.
* in the octant <math>-1 > y > x + 1</math> it is close to zero, except for near the singularities.

=== Generalization to ''q''-series ===
The binomial coefficient has a [[q-analog]] generalization known as the [[Gaussian binomial coefficient]].

=== Generalization to infinite cardinals ===
The definition of the binomial coefficient can be generalized to [[Cardinal Number|infinite cardinals]] by defining:
: <math>{\alpha \choose \beta} = \left| \left\{ B \subseteq A : \left|B\right| = \beta \right\} \right|</math>
where {{mvar|A}} is some set with [[cardinality]] <math>\alpha</math>. One can show that the generalized binomial coefficient is well-defined, in the sense that no matter what set we choose to represent the [[cardinal number]] <math>\alpha</math>, <math display="inline">{\alpha \choose \beta}</math> will remain the same. For finite cardinals, this definition coincides with the standard definition of the binomial coefficient.

Assuming the [[Axiom of Choice]], one can show that <math display="inline">{\alpha \choose \alpha} = 2^{\alpha}</math> for any infinite cardinal <math>\alpha</math>.