linguistic:translation, linguistic:voice_change, stylistic:style_transfer
Recurrence relation

A recurrence relation for multiset coefficients may be given as ((n k)) = ((n k − 1)) + ((n − 1 k)) for n, k > 0 {\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right)\quad {\mbox{for }}n,k>0} with ((n 0)) = 1, n ∈ N, and ((0 k)) = 0, k > 0. {\displaystyle \left(\!\!{n \choose 0}\!\!\right)=1,\quad n\in \mathbb {N},\quad {\mbox{and}}\quad \left(\!\!{0 \choose k}\!\!\right)=0,\quad k>0.}

The above recurrence may be interpreted as follows.Let:= { 1, …, n } {\displaystyle:=\{1,\dots,n\}} be the source set. There is always exactly one (empty) multiset of size 0, and if n = 0 there are no larger multisets, which gives the initial conditions.

Now, consider the case in which n, k > 0. A multiset of cardinality k with elements from might or might not contain any instance of the final element n. If it does appear, then by removing n once, one is left with a multiset of cardinality k − 1 of elements from, and every such multiset can arise, which gives a total of ((n k − 1)) {\displaystyle \left(\!\!{n \choose k-1}\!\!\right)} possibilities.

If n does not appear, then our original multiset is equal to a multiset of cardinality k with elements from, of which there are ((n − 1 k)). {\displaystyle \left(\!\!{n-1 \choose k}\!\!\right).}

Thus, ((n k)) = ((n k − 1)) + ((n − 1 k)). {\displaystyle \left(\!\!{n \choose k}\!\!\right)=\left(\!\!{n \choose k-1}\!\!\right)+\left(\!\!{n-1 \choose k}\!\!\right).}