Editing Binomial coefficient (section)

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