# 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)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)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)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)*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)