Permutations of Elements in Multisets with Infinite Repetition Numbers

Recall that a multiset is a collection of elements allowing the repetition of elements and that the repetition number of an element in a multiset is the number of times that element appears in the multiset.

We first consider counting the number of $k$-permutations of a multiset containing $n$ distinct elements $x_1, x_2, ..., x_n$ and all of whose repetition numbers are $\infty$. Such a multiset $A$ is of the following form:

(1)

\begin{align} \quad A = \{ \infty \cdot x_1, \infty \cdot x_2, ..., \infty \cdot x_n \} \end{align}

Now suppose that we want to determine how many $k$-permutations of the elements from the multiset $A$ are possible. For the first position in our $k$-permutation we can select any of the elements in $A$ and there are $n$ distinct elements to choose from. For the second position, we can also select any of the $n$ distinct elements in $A$ and there is no restriction to choosing any of them since each distinct element appears an infinite number of times in $A$. In fact, for each position in our $k$-permutation, we have a choice between $n$ distinct elements to choose from. Therefore by the multiplication principle we have that:

(2)

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

As a simple example, suppose that we want to construct a $3$-letter password out of the letters in the alphabet. In a sense, our "multiset" is the alphabet for which there is no restriction on which of the $26$ letters we can choose from. For the first character of our password, we can choose any of the $26$ letters. The same goes for the second and third characters of our password and so the total number of passwords we can have, i.e., the total number of $3$-permutations from a multiset with $26$ distinct elements and whose repetition numbers are $\infty$ is $26^3 = 17576$.

For another example, consider a bag of $3$ balls that are coloured red, yellow, and blue. Suppose that we select three balls, one ball at a time, and return the ball every time we draw one. How many different ways are there to select the three balls? Once again, we can imagine the bag of balls for which we return each drawn ball as a multiset, and our problem becomes finding the number of $3$-permutations of coloured balls that are possible. We can select either the red, yellow, or blue for all three of the drawings and so by the multiplication principle we have that there will be $3^3 = 27$ different ways for three balls to be drawn. They are given in the following table:

$(R, R, R )$	$(R, R, Y )$	$(R, R, B )$	$(R, Y, R )$	$(R, Y, B )$	$(R, B, R )$	$(R, B, Y )$	$(R, Y, Y )$	$(R, B, B )$
$(Y, Y, Y )$	$(Y, Y, R )$	$(Y, Y, B )$	$(Y, R, Y )$	$(Y, R, B)$	$(Y, B, Y )$	$(Y, B, R )$	$(Y, R, R )$	$(Y, B, B )$
$(B, B, B )$	$(B, B, Y )$	$(B, B, R )$	$(B, Y, B )$	$(B, Y, R )$	$(B, R, B )$	$(B, R, Y )$	$(B, Y, Y )$	$(B, R, R )$