Permutations II

by Calvin on January 9, 2013

[This post is targeted at a Level 2 student. You should be familiar with Permutations before proceeding.]

We are already familiar with using basic permutations, and will work on generalizing this result. Let’s think again about Lisa’s mantle. She still wants to put 5 ornaments on it, but she actually has 12 ornaments in total she can use. How many ways can she do this? Once again, we use the Rule of Product. Lisa has 12 choices for what 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, we could write this more compactly as $\frac{12!}{7!}$ . Using the same argument, we can proceed with the general case. If we have $n$ objects and we want to arrange $k$ of them in a row, there are $\frac{n!}{(n-k)!}$ ways to do this. This is also known as a k-permutation of n, and the number of ways is sometimes denoted as $P_k ^n$ .

Let’s consider a different extension of the permutation problem. What happens if Lisa has some ornaments that are the same? If she has 2 identical cat ornaments, 3 identical dog ornaments and 3 other completely different ornaments, how many ways can they all be arranged on her mantle? In total there are 7 objects, and if we pretend they are all distinct, there are $7!$ ways to arrange them on the mantle. For any arrangement, we can swap the pair of cats and get the same arrangement back. Also, we can move the dogs around and again get the same arrangement. How many ways can the dogs be moved around? Since the positions of the dogs are fixed, it is just the number of permutations of the dogs, which is $3!.$ Thus, to account for these repeated arrangements, we divide out by the number of repetitions to obtain that the total number of permutations is $\frac{7!}{3!2!}$ .

Worked Examples

1. 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 1 post.

Solution 1: There are 30 students to pick for the class president, which leaves 29 students for the secretary and 28 students for the treasurer. Hence, by the rule of product, there are $30 \times 29 \times 28 = 24360$ ways.

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$ .

2. How many ways can the letters in the name RAMONA be arranged?

Solution: As before, if we treat the A’s as distinct from each other (say $A_1$ and $A_2$ ), then there are $6!= 720$ ways to rearrange the letters. However, since the letters are the same, we have to divide by $2!$ to obtain $\frac {720}{2!} = 360$ ways.

3. 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.

Test Yourself

1. Samir and Mirdula each have 7 distinct books that they want to display on their shelves. Mirdula has lots of room on her shelf, however, Samir only has room to put 6 of his 7 books. Assuming that they fill up the entire shelf, who has more possible ways to arrange the books on their shelf? Why is this the case?

2. A waiter at a restaurant takes the drink order for a table of ten people but forgets to write down who ordered which drink. The orders are 5 cups of coffee, 3 glasses of water, 1 glass of milk, and 1 apple juice. How many different ways can the waiter deliver the drinks to the customers so that each customer gets one drink?

3. Consider all the ways to rearrange the letters of the word CALVIN, and arrange them in alphabetical order. In what position will CALVIN appear in? How about NIVLAC?

4. (*) Lisa wants to arrange 7 ornaments on her mantle. She has 2 identical cats, one mouse and 4 other different ornaments. If the mouse cannot be next to either of the cats, how many ways can they be arranged? Hint: Principle of Inclusion and Exclusion.

From → Combinatorics, Key Technique, Level 2

7 Comments

Saurabh Dubey permalink

1->Samir has more options because he has to select 6 books out of seven (7!) and then arrange them .
so total of 6!*7! whereas Mirdula only has to arrange 7 books (7!).

2->The number of ways would be 10!/(5!*3!*1!*1!) i.e 5040 ways.

Reply
zubayr khalid permalink

No. 1, both have equal options.Samir has 7p6 options and Mirdula has 7! options.
No 3. no of ways is 6!. CALVIN occurs at 131th position and NIVLAC occurs at 551th position.

Reply
Prajwal.B.Bharadwaj permalink

1..both have same no of ways …7p6 = 7p7
2..5040
3..Calvin in 131 …Nivlac ..550
4..

Reply
Anonymous permalink

Mr. Calvin please tell answers for Q 3 and 4. I want to confirm

Reply
- Calvin permalink
  
  I never discuss numerical answers, especially if you do not show your working. If you explain the steps that you took, I can see what was done well / wrong.
  
  Reply
Nisha permalink

When cats are together they can be arrange 6 ways then mouse can 4 and others can 4! total 6*4*4!=576
and when cats are not together first can be arrange 7 ways second 5 ways and mouse 3 Others Be 4! total 7*5*3*24=2520 then total=2520+576=3096 ways

Reply