Combinations of Elements in Multisets with Finite Repetition Numbers

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}