Binomial coefficient
Multiset (rising) binomial coefficient

Binomial coefficients count subsets of prescribed size from a given set. A related combinatorial problem is to count multisets 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 coefficients; the number of ways to "multichoose" (i.e., choose with replacement) k items from an n element set is denoted ((n k)) {\textstyle \left(\!\!{\binom {n}{k}}\!\!\right)}.

To avoid ambiguity and confusion with n' s main denotation in this article, let f = n = r + (k − 1) and r = f − (k − 1).

Multiset coefficients may be expressed in terms of binomial coefficients by the rule (f k) = ((r k)) = (r + k − 1 k). {\displaystyle {\binom {f}{k}}=\left(\!\!{\binom {r}{k}}\!\!\right)={\binom {r+k-1}{k}}.} One possible alternative characterization of this identity is as follows:We may define the falling factorial as (f) k = f k _ = (f − k + 1) ⋯ (f − 3) ⋅ (f − 2) ⋅ (f − 1) ⋅ f, {\displaystyle (f)_{k}=f^{\underline {k}}=(f-k+1)\cdots (f-3)\cdot (f-2)\cdot (f-1)\cdot f,} and the corresponding rising factorial as r (k) = r k ¯ = r ⋅ (r + 1) ⋅ (r + 2) ⋅ (r + 3) ⋯ (r + k − 1); {\displaystyle r^{(k)}=\,r^{\overline {k}}=\,r\cdot (r+1)\cdot (r+2)\cdot (r+3)\cdots (r+k-1);} so, for example, 17 ⋅ 18 ⋅ 19 ⋅ 20 ⋅ 21 = (21) 5 = 21 5 _ = 17 5 ¯ = 17 (5). {\displaystyle 17\cdot 18\cdot 19\cdot 20\cdot 21=(21)_{5}=21^{\underline {5}}=17^{\overline {5}}=17^{(5)}.} Then the binomial coefficients may be written as (f k) = (f) k k ! = (f − k + 1) ⋯ (f − 2) ⋅ (f − 1) ⋅ f 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋯ k, {\displaystyle {\binom {f}{k}}={\frac {(f)_{k}}{k!}}={\frac {(f-k+1)\cdots (f-2)\cdot (f-1)\cdot f}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}},} while the corresponding multiset coefficient is defined by replacing the falling with the rising factorial: ((r k)) = r (k) k ! = r ⋅ (r + 1) ⋅ (r + 2) ⋯ (r + k − 1) 1 ⋅ 2 ⋅ 3 ⋅ 4 ⋅ 5 ⋯ k. {\displaystyle \left(\!\!{\binom {r}{k}}\!\!\right)={\frac {r^{(k)}}{k!}}={\frac {r\cdot (r+1)\cdot (r+2)\cdots (r+k-1)}{1\cdot 2\cdot 3\cdot 4\cdot 5\cdots k}}.}
oulipo:avoid_letter[o]