MACM 101 Lecture 20: Lecture 20 Part 3_ Permutations
21 Dec 2018
School
Department
Course
Professor
Lecture 20 Part 3: Permutations
Theorem.
If there are n objects with n1 indistinguishable objects of a first type, n2 indistinguishable objects
of a second type, … , and nr indistinguishable objects of a type r, where n1+n2+...+nr = n, then
there are
n!/n1!n2!...nr!
(linear) arrangements of the given n objects.
- Each arrangement of this type is called a permutation with repetitions
Proof
- Let us denote objects by capital letters and add subscripts to indistinguishable objects so
that they become distinct.
- Then
A1, A2,..., An1 - objects of the first type
B1, B2,..., Bn2 - objects of the second type
- In how many ways can we construct a permutation of the n distinct objects?
- Clearly there are P(n,n) = n! ways to do so.
- Now we split this process into stages: first choose a permutation of indistinguishable
objects then select a permutation of A’s, of B’s etc
And we obtain the result Q.E.D.
Document Summary
Each arrangement of this type is called a permutation with repetitions. Let us denote objects by capital letters and add subscripts to indistinguishable objects so that they become distinct. A1, a2,, an1 - objects of the first type. B1, b2,, bn2 - objects of the second type. Clearly there are p(n,n) = n! ways to do so. Now we split this process into stages: first choose a permutation of indistinguishable objects then select a permutation of a"s, of b"s etc. Determine the number of (staircase) paths in the xy-plane from (0,0) to (6,4), where each such path is made up of individual steps going one unit to the right (r) or one unit upward (u). Every path like this can be encoded as a sequence of r"s and u"s. For example, the path on the picture is encoded as ruurrrurru. Therefore, the number of paths equals to the number of permutations with repetitions: 6.
