Let \(x_1, x_2, \dots, x_n\) represent a permutation. We can create a particular permutation by first assigning one element of \(A\) to \(x_1.\) Then assign an element in \(A\) not assigned to \(x_1\) to \(x_2.\) Then assign an element in \(A\) not assigned to \(x_1\) or \(x_2\) to \(x_3,\) and so on.

Each assignment of a value from \(A\) to one of the \(x_i\) will be an experiment. This is a total of \(n\) experiments:

• Assign a value to \(x_1\)
• Assign a value not assigned to \(x_1\) to \(x_2\)
• Assign a value not assigned to \(x_1\) or \(x_2\) to \(x_3\)
\(\vdots\)
• Assign a value not assigned to \(x_1, x_2, \dots, x_{n-2}\) or \(x_{n-1}\) to \(x_n.\)

We can next count the number of outcomes for each experiment.

• There are \(n\) values that can be assigned to \(x_1\) so the first experiment has \(n\) possible outcomes.
• No matter which value is assigned to \(x_1,\) there will be \(n-1\) numbers left to assign to \(x_2.\) The second experiment has \(n-1\) possible outcomes.
• No matter which values are assigned to \(x_1\) and \(x_2,\) there are \(n-2\) numbers left to assign to \(x_3.\) The third experiment has \(n-2\) possible outcomes.
\(\vdots\)
• After all the other \(n-1\) values are assigned, there is only \(1\) value left to assign to \(x_n.\) The last experiment will only have \(1\) possible outcome.

Since the number of outcomes of the experiments do not change based on the previous experiments, we can use the multiplication rule. The multiplication rule tells us that the number of possible outcomes of all \(n\) experiments is \(n \cdot (n-1) \cdot (n-2) \cdot \dots \cdot 1 = n!.\)

Example to help understand the proof:
Let \(A = \{a,b,c\}.\) The first experiment is to assign a value to \(x_1.\) There are \(3\) possible outcomes: \(x_1 = a,\) \(x_1 = b,\) or \(x_1 = c.\) For this example, suppose \(x_1 = b.\)
The next experiment is to assign a value to \(x_2.\) Since \(x_1 = b,\) there are only \(2\) possible outcomes: \(x_2 = a,\) \(x_2 = c.\) Suppose \(x_2 = c.\)
The last experiment is to assign a value to \(x_3.\) Since \(x_1 = b\) and \(x_2 = c,\) the only possible outcomes is \(x_3 = a.\) The permutation is \(b, c, a.\)
There are always \(3\) possible outcomes for \(x_1,\) \(2\) possible outcomes for \(x_2,\) and \(1\) possible outcome for \(x_1.\) By the multiplication rule, the total number of possible outcomes is \(3 \cdot 2 \cdot 1 = 6 = 3!.\)
Since \(A\) as \(3\) elements, there are \(3!\) possible permutations of the elements of \(A.\)

Number the elements in of each type \(a_i\) as elements \(1\) to \(n_i.\) This way, for every \(i\) the \(n_i\) elements of type \(a_i\) can be distinguished, since they will each have a different number. Since all \(n\) elements can be distinguished, there are \(n!\) permutations.

For a given permutation and a fixed \(i,\) every permutation of the \(n_i\) elements of type \(a_i\) will result in a permutation that will look identical without the numbers. There are \(n_i!\) permutations of the \(n_i\) elements of type \(a_i,\) so the same permutation will be duplicated \(n_i!\) times. Divide by \(n_i!\) to cancel the duplication. This is necessary for every \(i\) from \(1\) to \(k.\)

Example to help understand the proof:
Consider the permutations of the letters \(AABBB.\) There are \(2\) type \(A\) elements and \(3\) type \(B\) elements.
As the proof describes above, we can number the elements so that they can be distinguished: \(A_1A_2B_1B_2B_3.\) There are \(5!\) distinct permutations of \(A_1A_2B_1B_2B_3.\) For example, on such permutation is \[B_1B_3A_2B_2A_1\] Since there \(3\) elements in class \(B,\) there are \(6\) ways the \(B\) elements can be permutated that will result in the same permutation of the original letters.

1. \(B_1B_3A_2B_2A_1\)
2. \(B_1B_2A_2B_3A_1\)
3. \(B_3B_1A_2B_2A_1\)
4. \(B_3B_2A_2B_1A_1\)
5. \(B_2B_1A_2B_3A_1\)
6. \(B_2B_3A_2B_1A_1\)

All \(3!\) of these permutations will give us \(BBABA.\) That means the permutations of all \(5\) letters will result in a factor of \(3!\) duplicates due to the reptition of the \(B\) elements.
Similarly, for each permutations of the \(B\) elements, there are \(2!\) permutations of the \(A\) elements. So, there will be \(2!\) duplicates due to the repetition of the \(A\) elements.
Cancel the duplicates to find the total number of permutations: \[\frac{5!}{2!3!} = 10\]

The total number of balls is \(3 + 4 + 6 = 13.\)
There are \(3\) classes, red, blue, and yellow, with \(3,\) \(4,\) and \(6\) elements respectively.
Using the formula, the number of ways to put the balls in order is \[\frac{13!}{3!4!6!} = 60,060\]