Permutations of Elements in Mulitsets with Finite Repetition Numbers

Permutations of Elements in Mulitsets with Finite Repetition Numbers

Recall from the Permutations 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$-permutations of $A$ is:

(1)
\begin{align} \quad \mathrm{number \: of \:} k-\mathrm{permutations} = \underbrace{n \cdot n \cdot ... \cdot n}_{k} = n^k \end{align}

We will now look at the case when we want to count the number of $k$-permutations of a multiset containing $n$ distinct numbers and whose repetition numbers are not infinite.

Now consider a multiset $A$ containing $n$ distinct elements $x_1, x_2, ..., x_n$ and whose repetition numbers $r_1, r_2, ..., r_n$ are finite. Then $A$ is of the following form:

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

Suppose that we now want to determine the number of permutations of elements from $A$. If each repetition of each distinct element was instead a distinct element in $A$ then there would be $r_1 + r_2 + ... + r_n$ distinct elements, and so the number of permutations from elements in $A$ would be:

(3)
\begin{align} \quad \left ( \sum_{i=1}^{n} r_i \right ) ! = (r_1 + r_2 + ... + r_n)! \end{align}

Now for $j = 1, 2, ..., n$, since each distinct element $x_j$ instead appears $r_j$ times then the sum above is an overcount of the actual number of permutations from elements in the multiset $A$. For each repeated element $x_j$ there will be $r_j$ many permutations that are actually identical, and so the total number of permutations from the multiset $A$ with $n$ distinct elements and with finite repetition numbers $r_1, r_2, ..., r_n$ is equal and notationally written to be:

(4)
\begin{align} \quad \binom{(r_1 + r_2 + ... + r_n)!}{r_1, r_2, ..., r_n} = \frac{(r_1 + r_2 + ... + r_n)!}{r_1! \cdot r_2! \cdot ... \cdot r_n!} \end{align}

The notation above is called a Multinomial Coefficient which we will look more into later. Of course we can also use summation notation to write $\displaystyle{\binom{\left (\sum_{i=1}^{n} r_i \right )!}{r_1, r_2, ..., r_n} = \frac{\left ( \sum_{i=1}^{n} r_i \right )!}{\prod_{i=1}^{n} (r_i!)}}$.

To solidify this, consider the multiset $\{x, x, y\}$. Suppose instead that we label the $x$'s so that they're distinct to get the set $A^* = \{ x, x^*, y \}$. Further suppose that we want to find the number of permutations ($3$-permutations to be specific) that exist in this set. Therefore since the number of elements in $A^*$ is $n = 3$ we will have that $\frac{n!}{(n-k)!} = \frac{3!}{(3-3)!} = 6$ permutations given below.

 $(x, x^*, y)$ $(x, y, x^*)$ $(x^*, x, y)$ $(x^*, y, x)$ $(y, x, x*)$ $(y, x^*, x)$

Now replace all of the $x^*$'s with $x$'s to get:

 $(x, x, y)$ $(x, y, x)$ $(x, x, y)$ $(x, y, x)$ $(y, x, x)$ $(y, x, x)$

Notice how certain permutations are repeated. There are only three distinct $3$-permutations now, namely $(x, x, y)$, $(x, y, x)$, and $(y, x, x)$.

Now note that the repetition numbers of $A$ are $r_1 = 2$, $r_2 = 1$, and $r_3 = 1$. In applying the formula above we see that we indeed get $3$-permutations:

(5)
\begin{align} \quad \binom{r_1 + r_2 + r_3}{r_1, r_2, r_3} = \binom{3}{2, 1, 1} = \frac{3!}{2! \cdot 1! \cdot 1!} = 3 \end{align}