Category: Permutation and Combinations

Dividing people or distinct objects into groups

Calculating number of ways of dividing people or distinct objects into groups of the same size often pose difficulty to students.

Hopefully these examples will help students understand the concept.

Basic Example

How many ways can 10 children be divided into two groups of 5?

1

When dividing people or distinct objects into groups, if p groups are indistinguishable, we need to divide by p! to avoid double counting.

Challenging example 1 

At a particular reception, 9 guests are to stand at 3 identical round tables. How many ways can this be done if there are at least two people at each table?

3

Challenging example 2 (SAJC 2011/MYCT/2/6)

2

Venn diagram, Inclusion and Exclusion Principle

Venn diagram, Inclusion and exclusion principle can be useful in solving permutations, combinations and probability problems.

It is especially useful in solving combinations where the cases are not mutually exclusive and hence addition principle cannot be applied.

Example 1

venn diagram pnc

venn diagram p2

Circular Permutations

Circular permutations often pose some difficulty to students. Let’s consider the following scenarios:

Scenario A: 10 people to be seated at a round table with 10 identical seats

Number of ways = (10-1)! = 9! = 362880

Scenario B: 5 people to be seated at a round table with 10 numbered seats

Number of ways = 10 P 5 = 30240

Scenario C: 6 people to be seated at a round table with 10 identical seats

circular

There will be 4 identical empty seats. Consider fixing 1 occupied seat, and permutate the other 9 seats around it. There are 4 identical seats among the 9 seats. So number of ways = 9!/4! = 15120

Challenging Permutation question 5

A tennis club has n male players and n female players. For a tournament the players are to be arranged in n pairs, with each pair consisting of one male and one female. Find the number of possible pairings.

Answer: n!

Solution

Suppose the male got to choose his partner. The first male can choose from n females. After he has chosen, the next male can choose from (n-1) females. So the number of possible pairings is n.(n-1).(n-2)…1 = n!

For instance there are 2 male players (M1, M2) and 2 female (F1, F2) players.

One way to arrange 2 pairs of players: M1 F1 and M2 F2

Second way to arrange 2 pairs of players: M1 F2 and M2 F1

Number of ways to arrange 2 pairs of players is 2!

Comments

Some students will give the wrong answer n x n, which is the number of ways to choose a pair.

Challenging Permutation question 4

In how many ways can 9 balls of which 4 are red, 4 are white and 1 black be arranged in a line so that no red ball is next to the black?

Answer: 175

Solution

Case 1: 1st ball is black in the whole row of 9 balls

Then the 2nd ball must be white. The rest of the 4 red and 3 white balls can be arranged in Tex2Img_1404380765= 35 ways

Case 2: last ball is black

Then the 2nd last ball must be white. The rest of the 4 red and 3 white balls can be arranged in Tex2Img_1404380765 = 35 ways

Case 3: Black ball is not the 1st or last ball

Then the black ball must be between 2 white balls. Consider WBW as one unit. Together with 4 red balls and 2 white balls, these can arranged in Tex2Img_1404380967 = 105 ways

Using the addition principle, total number of ways = 35+35+105= 175

Challenging Permutation question 3

There are a total of 20 amusement rides in a theme park. A child insists on trying at least 5 of the amusement rides. Calculate the number of ways in which this can be done.

Answer: 1042380

Solution

Method 1

20 choose 5 + 20 choose 6 +… 20 choose 20

Using TI 84 OS (2.55)

sum (seq(20 nCr X, X, 5, 20, 1)

= 1042380

Method 2

2^20- (20 choose 0+ 20 choose 1+20 choose 2+20 choose 3+ 20 choose 4)

=1042380

Challenging Permutation question 2

Question: 6 adults and 3 children are sitting in a round table. Find the number of possible seating arrangement if none of the children sit together.

Solution: Choose 3 out of the 6 possible slots for the children to be seated between 2 adults, then multiply by 3! for the children permutation, then multiply by (6-1)! for the 6 adult circular permutation. Ans: 14400

Principle used: Slotting principle.

Challenging Permutation question 1

Q: There are five buildings. There are 4 different colours of paint. Each building must be painted with only 1 colour. Find the number of ways to paint all the 5 buildings if all 4 colours must be used.

Solution: 5 Choose 2 to have the same colour, then multiply by 4! for the colour permutation. Ans = 240

Principle used: Grouping principle.