# 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)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)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)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)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)We can verify this equality as follows:

(6)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)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.*