Editing Multiset (section)

=== Recurrence relation ===
A [[recurrence relation]] for multiset coefficients may be given as
<math display="block">\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right) \quad \mbox{for } n,k>0</math>
with
<math display="block">\left(\!\!{n \choose 0}\!\!\right) = 1,\quad n\in\N, \quad\mbox{and}\quad \left(\!\!{0 \choose k}\!\!\right) = 0,\quad k>0.</math>

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

Now, consider the case in which {{math|''n'', ''k'' > 0}}. A multiset of cardinality {{mvar|k}} with elements from {{math|[''n'']}} might or might not contain any instance of the final element {{mvar|n}}. If it does appear, then by removing {{mvar|n}} once, one is left with a multiset of cardinality {{math|''k'' −&thinsp;1}} of elements from {{math|[''n'']}}, and every such multiset can arise, which gives a total of
<math display="block">\left(\!\!{n\choose k - 1}\!\!\right)</math> possibilities.

If {{mvar|n}} does not appear, then our original multiset is equal to a multiset of cardinality {{mvar|k}} with elements from {{math|[''n'' −&thinsp;1]}}, of which there are
<math display="block">\left(\!\!{n-1\choose k}\!\!\right).</math>

Thus,
<math display="block">\left(\!\!{n\choose k}\!\!\right) = \left(\!\!{n\choose k - 1}\!\!\right) + \left(\!\!{n-1\choose k}\!\!\right).</math>