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}