Permutations With Restriction
A permutation is an ordering of a set of objects. When additional restrictions are imposed, the situation is transformed into a problem about permutations with restrictions. Most commonly, the restriction is that only a small number of objects are to be considered, meaning that not all the objects need to be ordered. Other common types of restrictions include restricting the type of objects that can be adjacent to one another, or changing the ordering mechanism from a line to another topology (e.g. a round table instead of a line, or a keychain instead of a ring).
Problems of this form are perhaps the most common in practice. For example, deciding on an order of what to eat, do, or watch are all implicit examples of permutations with restrictions, since it is obviously impractical to plan an ordering for all possible foods/tasks/shows.
Contents
Restriction to Few Objects
Restrictions to few objects is equivalent to the following problem:
Given \(n\) distinct objects, how many ways are there to place \(k\) of them into an ordering?
As in the strategy for dealing with permutations of the entire set of objects, consider an empty ordering which consists of \( k\) empty positions in a line to be filled by \(k\) objects. There are \( n\) choices for which of the \(n\) objects to place in the first position. After the first object is placed, there are \(n-1\) remaining objects, so there are \( n-1\) choices for which object to place in the second position. Repeating this argument, there are \( n-2\) choices for the third position, \( n-3\) choices for the fourth position, and so on. Finally, for the \( k^\text{th}\) position, there are \( n - (k-1) = n- k + 1\) choices. Then the rule of product implies the total number of orderings is given by the following:
Given \( n \) distinct objects, the number of different ways to place \(k\) of them into an ordering is
\[ P^n_k = n (n-1)(n-2) \cdots (n-k+1) = \frac{n!}{(n-k)!} . \]
This is also known as a \(k\)-permutation of \(n\).
Lisa has 12 ornaments and wants to put 5 ornaments on her mantle. How many ways can she do this?
By the rule of product, Lisa has 12 choices for which ornament to put in the first position, 11 for the second, 10 for the third, 9 for the fourth and 8 for the fifth. So the total number of choices she has is \( 12 \times 11 \times 10 \times 9 \times 8 \). Using the factorial notation, the total number of choices is \( \frac{12!}{7!} \). \(_\square\)
Out of a class of 30 students, how many ways are there to choose a class president, a secretary, and a treasurer? A student may hold at most one post.
Solution 1: We can choose from among 30 students for the class president, 29 students for the secretary, and 28 students for the treasurer. Hence, by the rule of product, the number of possibilities is \( 30 \times 29 \times 28 = 24360 \).
Solution 2: By the above discussion, there are \( P_{27}^{30} = \frac {30!}{(30-3)!} \) ways. While it is extremely hard to evaluate \( 30!\) and \( 27!\), we notice that dividing out gives \( 30 \times 29 \times 28 = 24360 \). \(_\square\)
Restrictions on Adjacent Objects
Lisa has 4 different dog ornaments and 6 different cat ornaments that she wants to place on her mantle. All of the dog ornaments should be consecutive and the cat ornaments should also be consecutive. How many ways can they be arranged?
We have to decide if we want to place the dog ornaments first, or the cat ornaments first, which gives us 2 possibilities. We can arrange the dog ornaments in \( 4!\) ways, and the cat ornaments in \( 6!\) ways. Hence, by the rule of product, there are \( 2 \times 6! \times 4! =34560 \) ways to arrange the ornaments. \(_\square\)
Restrictions on Topology
6 friends go out for dinner. How many ways are there to sit them around a round table? Rotations of a sitting arrangement are considered the same, but a reflection will be considered different.
Solution 1: Since rotations are considered the same, we may fix the position of one of the friends, and then proceed to arrange the 5 remaining friends clockwise around him. Thus, there are \( 5! = 120 \) ways to arrange the friends.
Solution 2: There are \( 6! \) ways to seat the 6 friends around the table. However, since rotations are considered the same, there are 6 arrangements which would be the same. Hence, to account for these repeated arrangements, we divide out by the number of repetitions to obtain that the total number of arrangements is \( \frac {6!}{6} = 120 \).
Both solutions are equally valid and illustrate how thinking of the problem in a different manner can yield another way of calculating the answer. \(_\square\)