Permutations

Consider the following problem: Lisa has 12 ornaments and wants to put 5 ornaments on her mantle. How many ways can she do this? Using 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×11×10×9×8 12 \times 11 \times 10 \times 9 \times 8 . Using the factorial notation, the total number of choices is 12!7! \frac{12!}{7!} .

Using the same argument, we can proceed with the general case. If we have n n objects and want to arrange k k of them in a row, there are n!(nk)! \frac{n!}{(n-k)!} ways to do this. This is also known as a kk-permutation of nn, and is denoted by Pkn 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 8! 8! ways to arrange them on the mantle. For any arrangement, we can take any of the 2! 2! permutations of the pair of cats and obtain the same arrangement. Similarly, we can take any of the 3! 3! permutations of dogs and obtain the same arrangement. Thus, to account for these repeated arrangements, we divide by the number of repetitions to obtain that the total number of permutations is 8!3!2! \frac{8!}{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 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×29×28=24360 30 \times 29 \times 28 = 24360 .

Solution 2: By the above discussion, there are P2730=30!(303)! P_{27}^{30} = \frac {30!}{(30-3)!} ways. While it is extremely hard to evaluate 30! 30! and 27! 27!, we notice that dividing out gives 30×29×28=24360 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 A1 A_1 and A2 A_2 ), then there are 6!=720 6!= 720 ways to rearrange the letters. However, since the letters are the same, we have to divide by 2! 2! to obtain 7202!=360 \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 5! = 120 ways to arrange the friends.

Solution 2: There are 6! 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 6!6=120 \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.

Note by Arron Kau
5 years, 6 months ago

No vote yet
1 vote

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

In the first example, aren't there 8 objects?

Nanayaranaraknas Vahdam - 5 years, 4 months ago

Log in to reply

Yes, thanks! I've fixed it now.

Arron Kau Staff - 5 years, 4 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...