Editing Multiset (section)

== Counting multisets ==<!-- Multiset coefficient and Multiset number redirect here -->
[[File:Combinations with repetition; 5 multichoose 3.svg|thumb|370px|[[Bijection]] between 3-subsets of a 7-set (left)<br>and 3-multisets with elements from a 5-set (right)<br>So this illustrates that <math display="inline"> {7 \choose 3} = \left(\!\!{5 \choose 3}\!\!\right).</math>]]
{{See also|Stars and bars (combinatorics)}}
The number of multisets of cardinality {{mvar|k}}, with elements taken from a finite set of cardinality {{mvar|n}}, is sometimes called the '''multiset coefficient''' or '''multiset number'''. This number is written by some authors as <math>\textstyle\left(\!\!{n\choose k}\!\!\right)</math>, a notation that is meant to resemble that of [[binomial coefficient]]s; it is used for instance in (Stanley, 1997), and could be pronounced "{{mvar|n}} multichoose {{mvar|k}}" to resemble "{{mvar|n}} choose {{mvar|k}}" for <math>\tbinom n k.</math> Like the [[binomial distribution]] that involves binomial coefficients, there is a [[negative binomial distribution]] in which the multiset coefficients occur.  Multiset coefficients should not be confused with the [[multinomial coefficient]]s that occur in the [[multinomial theorem]].

The value of multiset coefficients can be given explicitly as
<math display="block">\left(\!\!{n\choose k}\!\!\right) = {n+k-1 \choose k} = \frac{(n+k-1)!}{k!\,(n-1)!} = {n(n+1)(n+2)\cdots(n+k-1)\over k!},</math>
where the second expression is as a binomial coefficient;{{efn|The formula {{tmath|\tbinom{n+k-1}k}} does not work for {{math|1=''n'' = 0}} (where necessarily also {{math|1=''k'' = 0}}) if viewed as an ordinary binomial coefficient since it evaluates to {{tmath|\tbinom{-1}0}}, however the formula {{math|''n''(''n''+1)(''n''+2)...(''n''+''k''−1)/''k''!}} does work in this case because the numerator is an [[empty product]] giving {{math|1=1/0! = 1}}. However {{tmath|\tbinom{n+k-1}k}} does make sense for {{math|1=''n'' = ''k'' = 0}} if interpreted as a [[Binomial coefficient#Binomial coefficients as polynomials|generalized binomial coefficient]]; indeed {{tmath|\tbinom{n+k-1}k}} seen as a generalized binomial coefficient equals the extreme right-hand side of the above equation.}} many authors in fact avoid separate notation and just write binomial coefficients. So, the number of such multisets is the same as the number of subsets of cardinality {{mvar|k}} of a set of cardinality {{math|''n'' + ''k'' −&thinsp;1}}. The analogy with binomial coefficients can be stressed by writing the numerator in the above expression as a [[rising factorial power]]
<math display="block">\left(\!\!{n \choose k}\!\!\right) = {n^{\overline{k}}\over k!},</math>
to match the expression of binomial coefficients using a falling factorial power:
<math display="block">{n \choose k} = {n^{\underline{k}}\over k!}.</math>

For example, there are 4 multisets of cardinality 3 with elements taken from the set {{math|{{mset|1, 2}}}} of cardinality 2 ({{math|1=''n'' = 2}}, {{math|1=''k'' = 3}}), namely {{math|{{mset|1, 1, 1}}}}, {{math|{{mset|1, 1, 2}}}}, {{math|{{mset|1, 2, 2}}}}, {{math|{{mset|2, 2, 2}}}}. There are also 4 ''subsets'' of cardinality 3 in the set {{math|{{mset|1, 2, 3, 4}}}} of cardinality 4 ({{math|''n'' + ''k'' −&thinsp;1}}), namely {{math|{{mset|1, 2, 3}}}}, {{math|{{mset|1, 2, 4}}}}, {{math|{{mset|1, 3, 4}}}}, {{math|{{mset|2, 3, 4}}}}.

One simple way to [[mathematical proof|prove]] the equality of multiset coefficients and binomial coefficients given above involves representing multisets in the following way.  First, consider the notation for multisets that would represent {{math|{{mset|''a'', ''a'', ''a'', ''a'', ''a'', ''a'', ''b'', ''b'', ''c'', ''c'', ''c'', ''d'', ''d'', ''d'', ''d'', ''d'', ''d'', ''d''}}}} (6 {{mvar|a}}s, 2 {{mvar|b}}s, 3 {{mvar|c}}s, 7 {{mvar|d}}s) in this form:

:{{nowrap|{{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}}  &nbsp;{{!}} {{bullet}} {{bullet}}  &nbsp;{{!}} {{bullet}} {{bullet}} {{bullet}}  &nbsp;{{!}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} {{bullet}} }}

This is a multiset of cardinality {{math|1=''k'' =&thinsp;18}} made of elements of a set of cardinality {{math|1=''n'' = 4}}.  The number of characters including both dots and vertical lines used in this notation is {{math|18 + 4 − 1}}.  The number of vertical lines is 4 − 1.  The number of multisets of cardinality 18 is then the number of ways to arrange the {{math|4 − 1}} vertical lines among the 18 + 4 − 1 characters, and is thus the number of subsets of cardinality 4 − 1 of a set of cardinality {{math|18 + 4 − 1}}.  Equivalently, it is the number of ways to arrange the 18 dots among the {{math|18 + 4 − 1}} characters, which is the number of subsets of cardinality 18 of a set of cardinality {{math|18 + 4 − 1}}. This is
<math display="block">{4+18-1 \choose 4-1}={4+18-1 \choose 18} = 1330,</math>
thus is the value of the multiset coefficient and its equivalencies:
<math display="block">\begin{align}
\left(\!\!{4\choose18}\!\!\right)
&={21\choose18}=\frac{21!}{18!\,3!}={21\choose3}, \\[1ex]
&=\frac{{\color{red}{\mathfrak{
4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}}
\cdot
\mathbf{19\cdot20\cdot21}}{\mathbf{1\cdot2\cdot3}
\cdot
{\color{red}{\mathfrak{
4\cdot5\cdot6\cdot7\cdot8\cdot9\cdot10\cdot11\cdot12\cdot13\cdot14\cdot15\cdot16\cdot17\cdot18}}}}, \\[1ex]
&=\frac{
1\cdot2\cdot3\cdot4\cdot5\cdots16\cdot17\cdot18\;\mathbf{\cdot\;19\cdot20\cdot21}}
{\,1\cdot2\cdot3\cdot4\cdot5\cdots
16\cdot17\cdot18\;\mathbf{\cdot\;1\cdot2\cdot3\quad}}, \\[1ex]
&=\frac{19\cdot20\cdot21}{1\cdot2\cdot3}.
\end{align}</math>

From the relation between binomial coefficients and multiset coefficients, it follows that the number of multisets of cardinality {{mvar|k}} in a set of cardinality {{mvar|n}} can be written
<math display="block">\left(\!\!{n\choose k}\!\!\right)=(-1)^k{-n \choose k}.</math>
Additionally,
<math display="block">\left(\!\!{n\choose k}\!\!\right)=\left(\!\!{k+1\choose n-1}\!\!\right).</math>

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

===Generating series===
The [[generating function]] of the multiset coefficients is very simple, being
<math display="block">\sum_{d=0}^\infty \left(\!\!{n\choose d}\!\!\right)t^d = \frac{1}{(1-t)^n}.</math>
As multisets are in one-to-one correspondence with [[monomial]]s, <math>\left(\!\!{n\choose d}\!\!\right)</math> is also the number of monomials of [[Degree of a polynomial#Extension to polynomials with two or more variables|degree]] {{mvar|d}} in {{mvar|n}} indeterminates. Thus, the above series is also the [[Hilbert series]] of the [[polynomial ring]] <math>k[x_1, \ldots, x_n].</math>

As <math>\left(\!\!{n\choose d}\!\!\right)</math> is a polynomial in {{mvar|n}}, it and the generating function are well defined for any [[complex number|complex]] value of {{mvar|n}}.

=== Generalization and connection to the negative binomial series ===
The multiplicative formula allows the definition of multiset coefficients to be extended by replacing {{mvar|n}} by an arbitrary number {{mvar|α}} (negative, [[real number|real]], or complex):
<math display="block">\left(\!\!{\alpha\choose k}\!\!\right) = \frac{\alpha^{\overline k}}{k!} = \frac{\alpha(\alpha+1)(\alpha+2)\cdots(\alpha+k-1)}{k(k-1)(k-2)\cdots 1}
  \quad\text{for } k\in\N \text{ and arbitrary } \alpha.
</math>

With this definition one has a generalization of the negative binomial formula (with one of the variables set to 1), which justifies calling the <math>\left(\!\!{\alpha\choose k}\!\!\right)</math> negative binomial coefficients:
<math display="block">(1-X)^{-\alpha} = \sum_{k=0}^\infty \left(\!\!{\alpha\choose k}\!\!\right) X^k.</math>

This [[Taylor series]] formula is valid for all complex numbers ''α'' and ''X'' with {{math|{{abs|''X''}} < 1}}. It can also be interpreted as an [[identity (mathematics)|identity]] of [[formal power series]] in ''X'', where it actually can serve as definition of arbitrary powers of series with constant coefficient equal to&nbsp;1; the point is that with this definition all identities hold that one expects for [[exponentiation]], notably

<math display="block">(1-X)^{-\alpha}(1-X)^{-\beta}=(1-X)^{-(\alpha+\beta)} \quad\text{and}\quad ((1-X)^{-\alpha})^{-\beta}=(1-X)^{-(-\alpha\beta)},</math>
and formulas such as these can be used to prove identities for the multiset coefficients.

If {{mvar|α}} is a nonpositive integer {{mvar|n}}, then all terms with {{math|''k'' > −''n''}} are zero, and the infinite series becomes a finite sum. However, for other values of {{mvar|α}}, including positive integers and [[rational number]]s, the series is infinite.