Combinations of Elements in Multisets with Infinite Repetition Numbers

We will now look at the number of $k$-combinations of a multiset containing $n$ distinct elements whose repetition numbers are $\infty$.

Recall that a $k$-combination of an ordinary finite $n$-element set $A$ is simply a selection of $k$ out of all $n$ elements in $A$. In others words, a $k$-combination of $A$ is a subset $B \subseteq A$ such that $\lvert B \rvert = k$. By extension, a $k$-combination of a multiset $A$ is simply a submultiset $B$ of $A$ that contains $k$ elements.

Suppose that $A$ is a multiset containing $n$ distinct elements $x_1, x_2, ..., x_n$ and whose repetition numbers are $\infty$. Then $A$ is of the following form:

(1)

\begin{align} \quad A = \{\infty \cdot x_1, \infty \cdot x_2, ..., \infty \cdot x_n \} \end{align}

Let's determine how many $k$-combinations of $A$ exist. We first note that if $B$ is a submultiset of $A$ then $B$ must be of the form:

(2)

\begin{align} \quad B = \{ b_1 \cdot x_1, b_2 \cdot x_2, ..., b_n \cdot x_n \} \end{align}

For $B$ to be a $k$-combination of $A$ we must have that $B$ has $k$-elements, i.e, we must have that the repetition numbers of the subset $B$ are nonnegative integers satisfying the following linear equation:

(3)

\begin{align} \quad b_1 + b_2 + ... + b_n = k \end{align}

Set up positions to place all $k$ elements from $A$ and group like-elements together. Place $n - 1$ placeholders between each grouping of like-elements. There are now $k + n - 1$ positions total and the rearrangement of the placeholders signifies a new $k$-combination of the multiset $A$ as illustrated in the diagram below.

We must choose $k$ of these positions of the elements from $A$ to form a $k$-combination, and so the total number of $k$-combinations of $A$ is:

(4)

\begin{align} \quad \mathrm{number \: of \:} k-\mathrm{combinations} = \binom{k + n - 1}{k} \end{align}

We should further note that instead of choosing the $k$ positions of the elements from $A$ first, we can instead choose the $n - 1$ positions of the placeholders which also form a $k$-combination, and so the total number of $k$-combinations of $A$ is also given by:

(5)

\begin{align} \quad \mathrm{number \: of \:} k-\mathrm{combinations} = \binom{k + n - 1}{n - 1} \end{align}

We can verify this equality as follows:

(6)

\begin{align} \quad \binom{k + n - 1}{k} = \frac{(k + n - 1)!}{k! \cdot (k + n - 1 - k)!} = \frac{(k + n - 1)!}{k! \cdot (n - 1)!} = \frac{(k + n - 1)!}{(n - 1)! \cdot (n - 1 + k - [n - 1])!} = \binom{k + n - 1}{n - 1} \end{align}

For example, suppose that we have the multiset $A = \{x, x, y, z, z \} = \{ 2 \cdot x, 1 \cdot y, 2 \cdot z \}$ and we want to find the number of $2$-combinations of elements from $A$. The number of distinct elements in $A$ is $n = 3$, and we're looking for the $k = 2 $}]-combinations of elements from [[$ A$ and so there are:

(7)

\begin{align} \quad \binom{(k + n - 1)!}{k!} = \binom{(2 + 3 - 1)}{3!} = \binom{4!}{3!} = 4 \end{align}

These $2$-combinations are given in the table below as submultisets.

$\{ 2 \cdot x, 0 \cdot y, 0 \cdot z \}$

$\{ 1 \cdot x, 1 \cdot y, 0 \cdot z \}$

$\{ 1 \cdot y, 1 \cdot z \}$

$\{ 0 \cdot x, 0 \cdot y, 2 \cdot z \}$

We will look at the case of determining the number of $k$-combinations of a multiset containing $n$ distinct elements and whose repetition number are finite on the Combinations of Elements in Multisets with Finite Repetition Numbers page AFTER we have looked at The Inclusion-Exclusion Principle.