Combinations of Elements in Multisets with Finite Repetition Numbers

Recall from the Combinations of Elements in Multisets with Infinite Repetition Numbers page that if $A$ is a multiset containing $n$ distinct elements $x_1, x_2, ..., x_n$ and whose repetition numbers are $\infty$ then the number of $k$-combinations that can be formed is given by:

(1)

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

In obtaining this formula, we let $b_1$ be the number of times $x_1$ is chosen, $b_2$ be the number of times $x_2$ is chosen, …, $b_n$ be the number of times $x_n$ is chosen. To ensure we obtained a $k$-combination each time, we needed the values of the $b$'s to satisfy $b_1 + b_2 + ... + b_n = k$. By placing $n - 1$ placeholders between each grouping $b_i$, $i \in \{1, 2, ..., n \}$ we obtain a total of $k + n - 1$ positions for which the choices of $k$ of them to be elements $x_1$ through $x_n$ determines all $k$-combinations from $A$ (or equivalently, the choices of the $n - 1$ placeholders determines all $k$-combinations from $A$).

We postponed on looking at combinations of elements in multisets with finite repetition numbers until now because this problem is better tackled after looking at The Inclusion-Exclusion Principle, which we recall states that if $A_1, A_2, ..., A_n$ are finite sets, then:

(2)

\begin{align} \quad \biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert = \sum_{i=1}^{n} \lvert A_i \rvert - \sum_{1 \leq p_1 < p_2 \leq n} \lvert A_{p_1} \cap A_{p_2} \rvert + \sum_{1 \leq p_1 < p_2 < p_3 \leq n} \lvert A_{p_1} \cap A_{p_2} \cap A_{p_3} \rvert - ... + (-1)^{n+1} \sum_{1 \leq p_1 < p_2 < ... < p_n \leq n} \lvert A_{p_1} \cap A_{p_2} \cap ... \cap A_{p_n} \rvert \end{align}

We are now able to determine the number of $k$-combinations of a multiset $A$ with $n$ distinct elements and finite repetition numbers:

(3)

\begin{align} \quad A = \{ r_1 \cdot x_1, r_2 \cdot x_2, ..., r_n \cdot x_n \} \end{align}

We first notice that if $r_i \geq k$ for any $i \in \{1, 2, ..., n \}$ that then the number of $k$-combinations of $A$ is equal to the number of $k$-combinations in $A^* = \{ r_1 \cdot x_1, r_2 \cdot x_2, ..., k \cdot x_i, ..., r_n \cdot x_n \}$. This is because we can at most place $k$ many of the $x_i$s into any $k$-combination. As a result, we see that the number of $k$-combinations of the multiset $A_{\infty} = \{ \infty \cdot x_1, \infty \cdot x_2, ..., \infty \cdot x_n \}$ is the same as the number of $k$-combinations of the multiset $A_k = \{ k \cdot x_1, k \cdot x_2, ..., k \cdot x_n \}$ which of course is $\displaystyle{\binom{k + n - 1}{k} = \binom{k + n - 1}{n - 1}}$.

Let $A^{+}$ denote the set of all $k$-combinations from $A$ ignoring repetition numbers (or assuming each repetiton number is at least $k$), and suppose that at least some of the $r_i$ are such that $r_i < k$. For each $i \in \{ 1, 2, ..., n \}$ let $A_i$ be the set of $k$-combinations from the multiset $A$ that contain more than $r_i$ many $x_i$s. Then the number of $k$-combinations of $A$ is the total number of $k$-combinations minus any $k$-combination in at least one of the $A_i$'s i.e.:

(4)

\begin{align} \quad \mathrm{number \: of \:} k-\mathrm{combinations} = \mid A^{+} \mid - \biggr \lvert \bigcup_{i=1}^{n} A_i \biggr \rvert \end{align}

In applying the inclusion-exclusion principle we have:

(5)

\begin{align} \quad \mathrm{number \: of \:} k-\mathrm{combinations} = \mid A^{+} \mid - \left ( \sum_{i=1}^{n} \lvert A_i \rvert - \sum_{1 \leq p_1 < p_2 \leq n} \lvert A_{p_1} \cap A_{p_2} \rvert + \sum_{1 \leq p_1 < p_2 < p_3 \leq n} \lvert A_{p_1} \cap A_{p_2} \cap A_{p_3} \rvert - ... \\ \quad \quad \quad \quad \quad \quad \quad \quad + (-1)^{n+1} \sum_{1 \leq p_1 < p_2 < ... < p_n \leq n} \lvert A_{p_1} \cap A_{p_2} \cap ... \cap A_{p_n} \rvert \right ) \end{align}

For example, consider the following multiset:

(6)

\begin{align} \quad A = \{ 2 \cdot x, 3 \cdot y, 4 \cdot z \} \end{align}

Suppose that we want to determine the number of $6$-combinations of elements from the multiset $A$. Let $A_1$ be the set of $6$-combinations containing more than $2$ many $x$s, let $A_2$ be the set of $6$-combinations containing more than $3$ many $y$s, let $A_3$ be the set of $6$-combinations containing more than $4$ many $z$s.

The total number of $6$-combinations that can be formed when ignoring the repetiton numbers is $\binom{6 + 3 - 1}{3} = \binom{8}{3} = 56$. Therefore $\mid A^{+} \mid = 56$.

Now consider the total number of $6$-combinations that have at least $3$ many $x$s, i.e., $\mid A_1 \mid$. This is the same number as the number of $3$-combinations of elements from $A$ to which we choose $3$ of them, i.e., $\mid A_1 \mid = \binom{3 + 3 - 1}{3} = \binom{5}{3} = 10$.

Now consider the total number of $6$-combinations that have at least $4$ many $y$s, i.e., $\mid A_2 \mid$. This is the same number as the number of $2$-combinations of elements from $A$ to which we choose $2$ of them, i.e., $\mid A_2 \mid = \binom{2 + 3 - 1}{2} = \binom{4}{2} = 6$.

Now consider the total number of $6$-combinations that have at least $5$ many $z$s, i.e., $\mid A_3 \mid$. This is the same number as the number of $1$-combinations of elements from $A$ to which we choose $1$ of them, i.e., $\mid A_3 \mid = \binom{1 + 3 - 1}{1} = \binom{3}{1} = 3$.

Now consider the total number of $6$-combinations that have at least $3$ many $x$ and at least $4$ many $y$s, i.e, $\mid A_1 \cap A_2$. The size of $A_1 \cap A_2$ is $0$ though since then we'd exceed $6$ elements in our $6$-combination. Similarly, $\mid A_1 \cap A_3 \mid = 0$, $\mid A_2 \cap A_3 \mid = 0$ and $\mid A_1 \cap A_2 \cap A_3 \mid = 0$. Therefore:

(7)

\begin{align} \quad \mathrm{number \: of} \: k-\mathrm{combinations} = 56 - (10 + 6 + 3 - (0 + 0 + 0) + 0) = 37 \end{align}