Permutation and Combination

4.1

Permutation

Multiplication Rule

If an event can occur in \(m\) ways and a second event can occur in \(n\) ways,

then both events can occur in \(m \times n\) ways

For example:


	\(3 \text{ types of }roti \ \times 2 \text{ types of gravy } = 6 \text{ ways to choose a breakfast set}\)

This rule can also be applied to more than two events

Example

(a)	Determine the number of ways to toss a dice and a piece of coin simultaneously.

(b)	Find the number of ways a person can guess a \(4\)-digit code to access a cell phone if the digits can be repeated.


Penyelesaian:

(a)	A dice has \(6\) surfaces and a piece of coin has \(2\) surfaces. Hence, the number of ways to toss both objects simultaneously is \(6 × 2 = 12\).

(b)	The number of ways a person can guess the \(4\)-digit code to access a cell phone is \(10 \times 10 \times 10 \times 10 = 10 \ 000\) because there are \(10\) digits of number.

Permutation


	The number of ways to arrange these letters.

Determining the number of permutation for \(n\) different objects:


	\(n! = \ _{n}P_{r} = n \times (n-1) \times (n-2) \times \ ... \ \times 3 \times 2 \times 1\)

The permutation of \(n\) objects in a circle is:


	\(P = \dfrac{n!}{n} = \dfrac{n(n-1)!}{n} = (n-1)!\)

Example

(a)	Find the value of \(\dfrac{11!}{9!}\) without using a calculator.

(b)	Find the number of ways to arrange all the letters from the word BIJAK when repetition of letters is not allowed.

(c)	Determine the number of ways to arrange six pupils to sit at a round table.


Solution:

(a)	\(\begin{aligned} \dfrac{11!}{9!} &= \dfrac{11 \times 10 \times 9!}{9!}\\\\ &=11\times 10\\\\ &=110 \end{aligned}\)

(b)	Given the number of letters, \(n=5\). Thus, the number of ways to arrange all the letters is \(5! = 120\).

(c)	Given the number of pupils, \(n=6\). Thus, the number of ways to arrange the six pupils is \((6 – 1)! = 120\).

Determining the number of permutation of \(n\) different objects, taking \(r\) objects each time:


	\( _{n}P_{r} = \dfrac{n!}{(n-r)!}\), where \(r \leqslant n\)

The number of permutations for \(n\) different objects taking \(r\) objects each time and arranged in a circle is given by:


	\(\dfrac{_{n}P_{r}}{r}\)

Remark


	A permutation of an object in a circle where clockwise and anticlockwise arrangements are the same, then the number of ways is
	\(\dfrac{_{n}P_{r}}{2r}\)

Example

(a)	Eight committee members from a society are nominated to contest for the posts of President, Vice President and Secretary. How many ways can this three posts be filled?

(b)	Nadia bought \(12\) beads of different colours from Handicraft Market in Kota Kinabalu and she intends to make a bracelet. Nadia realises that the bracelet requires only \(8\) beads. How many ways are there to make the bracelet?


Solution:

(a)	Three out of the eight committee members will fill up the three posts. Hence, \(_{8}P_{3} = \dfrac{8!}{(8-3)!} = 336 \)

(b)	Given the number of beads is 12 and 8 beads are to be arranged to form a bracelet. It is found that clockwise and anticlockwise arrangements are identical. Hence, the number of permutations is \(\dfrac{_{12}P_{8}}{2(8)} = 1 \ 247 \ 400\)

Determining the number of permutations for \(n\) objects involving identical objects:


	\(P = \dfrac{n!}{a!b!c! \ ...}\), where

	\(a, b \text{ and } c, \ ... \) are the number of identical objects for each type

Example

	Calculate the number of ways to arrange the letters from the word SIMBIOSIS

	Solution:

	Given \(n=9\). The identical objects for letters S and I are the same, which is \(3\). Hence, the number of ways to arrange the letters from the word SIMBIOSIS is \(\dfrac{9!}{3!3!}= 10\ 080\)

4.2

Combination


	When choosing an object from a set where positions or arrangements are not important.

Comparing permutation and combination:

Permutation

Combination


	Process of arranging objects where order and sequence are taken into consideration


	Process of selection without considering the order and sequence of the objects

Determining the number of combinations of \(r\) objects chosen from \(n\) different objects at a time:


	\(_{n}C_{r} = \dfrac{_{n}P_{r}}{r!} = \dfrac{n!}{r!(n-r)!}\)

Remark

Combination can be written as

\(_{n}C_{r} \text{ or }\dbinom{n}{r}\) and

\(_{n}C_{r} \) is also known as binomial coefficient.

Contoh

(a)	Find the number of triangles that can be formed from the vertices of a hexagon.

(b)	Encik Samad wants to choose three types of batik motifs from four organic motifs and five geometrical motifs. Find the number of ways to choose at least one organic motif and one geometrical motif.


Solution:

(a)	Hexagon has six vertices. To form a triangle, any three vertices are required. So, the number of ways is \(\begin{aligned} _{n}C_{r} &= \dfrac{6!}{3!(6-3)!} \\\\ &=\dfrac{6!}{3!3!}\\\\ &=20 \end{aligned}\)

(b)	Number of ways to choose two organic motifs and one geometric motif, \(_{4}C_{2} \times \ _{5}C_{1}\) Number of ways to choose one organic motif and two geometric motifs, \(_{4}C_{1} \times \ _{5}C_{2}\) So, the number of ways \((_{4}C_{2} \times \ _{5}C_{1}) + (_{4}C_{1} \times \ _{5}C_{2}) = 70 \)

Permutation and Combination

4.1

Permutation

Multiplication Rule

If an event can occur in \(m\) ways and a second event can occur in \(n\) ways,

then both events can occur in \(m \times n\) ways

For example:


	\(3 \text{ types of }roti \ \times 2 \text{ types of gravy } = 6 \text{ ways to choose a breakfast set}\)

This rule can also be applied to more than two events

Example

(a)	Determine the number of ways to toss a dice and a piece of coin simultaneously.

(b)	Find the number of ways a person can guess a \(4\)-digit code to access a cell phone if the digits can be repeated.


Penyelesaian:

(a)	A dice has \(6\) surfaces and a piece of coin has \(2\) surfaces. Hence, the number of ways to toss both objects simultaneously is \(6 × 2 = 12\).

(b)	The number of ways a person can guess the \(4\)-digit code to access a cell phone is \(10 \times 10 \times 10 \times 10 = 10 \ 000\) because there are \(10\) digits of number.

Permutation


	The number of ways to arrange these letters.

Determining the number of permutation for \(n\) different objects:


	\(n! = \ _{n}P_{r} = n \times (n-1) \times (n-2) \times \ ... \ \times 3 \times 2 \times 1\)

The permutation of \(n\) objects in a circle is:


	\(P = \dfrac{n!}{n} = \dfrac{n(n-1)!}{n} = (n-1)!\)

Example

(a)	Find the value of \(\dfrac{11!}{9!}\) without using a calculator.

(b)	Find the number of ways to arrange all the letters from the word BIJAK when repetition of letters is not allowed.

(c)	Determine the number of ways to arrange six pupils to sit at a round table.


Solution:

(a)	\(\begin{aligned} \dfrac{11!}{9!} &= \dfrac{11 \times 10 \times 9!}{9!}\\\\ &=11\times 10\\\\ &=110 \end{aligned}\)

(b)	Given the number of letters, \(n=5\). Thus, the number of ways to arrange all the letters is \(5! = 120\).

(c)	Given the number of pupils, \(n=6\). Thus, the number of ways to arrange the six pupils is \((6 – 1)! = 120\).

Determining the number of permutation of \(n\) different objects, taking \(r\) objects each time:


	\( _{n}P_{r} = \dfrac{n!}{(n-r)!}\), where \(r \leqslant n\)

The number of permutations for \(n\) different objects taking \(r\) objects each time and arranged in a circle is given by:


	\(\dfrac{_{n}P_{r}}{r}\)

Remark


	A permutation of an object in a circle where clockwise and anticlockwise arrangements are the same, then the number of ways is
	\(\dfrac{_{n}P_{r}}{2r}\)

Example

(a)	Eight committee members from a society are nominated to contest for the posts of President, Vice President and Secretary. How many ways can this three posts be filled?

(b)	Nadia bought \(12\) beads of different colours from Handicraft Market in Kota Kinabalu and she intends to make a bracelet. Nadia realises that the bracelet requires only \(8\) beads. How many ways are there to make the bracelet?


Solution:

(a)	Three out of the eight committee members will fill up the three posts. Hence, \(_{8}P_{3} = \dfrac{8!}{(8-3)!} = 336 \)

(b)	Given the number of beads is 12 and 8 beads are to be arranged to form a bracelet. It is found that clockwise and anticlockwise arrangements are identical. Hence, the number of permutations is \(\dfrac{_{12}P_{8}}{2(8)} = 1 \ 247 \ 400\)

Determining the number of permutations for \(n\) objects involving identical objects:


	\(P = \dfrac{n!}{a!b!c! \ ...}\), where

	\(a, b \text{ and } c, \ ... \) are the number of identical objects for each type

Example

	Calculate the number of ways to arrange the letters from the word SIMBIOSIS

	Solution:

	Given \(n=9\). The identical objects for letters S and I are the same, which is \(3\). Hence, the number of ways to arrange the letters from the word SIMBIOSIS is \(\dfrac{9!}{3!3!}= 10\ 080\)

4.2

Combination


	When choosing an object from a set where positions or arrangements are not important.

Comparing permutation and combination:

Permutation

Combination


	Process of arranging objects where order and sequence are taken into consideration


	Process of selection without considering the order and sequence of the objects

Determining the number of combinations of \(r\) objects chosen from \(n\) different objects at a time:


	\(_{n}C_{r} = \dfrac{_{n}P_{r}}{r!} = \dfrac{n!}{r!(n-r)!}\)

Remark

Combination can be written as

\(_{n}C_{r} \text{ or }\dbinom{n}{r}\) and

\(_{n}C_{r} \) is also known as binomial coefficient.

Contoh

(a)	Find the number of triangles that can be formed from the vertices of a hexagon.

(b)	Encik Samad wants to choose three types of batik motifs from four organic motifs and five geometrical motifs. Find the number of ways to choose at least one organic motif and one geometrical motif.


Solution:

(a)	Hexagon has six vertices. To form a triangle, any three vertices are required. So, the number of ways is \(\begin{aligned} _{n}C_{r} &= \dfrac{6!}{3!(6-3)!} \\\\ &=\dfrac{6!}{3!3!}\\\\ &=20 \end{aligned}\)

(b)	Number of ways to choose two organic motifs and one geometric motif, \(_{4}C_{2} \times \ _{5}C_{1}\) Number of ways to choose one organic motif and two geometric motifs, \(_{4}C_{1} \times \ _{5}C_{2}\) So, the number of ways \((_{4}C_{2} \times \ _{5}C_{1}) + (_{4}C_{1} \times \ _{5}C_{2}) = 70 \)

Permutation and Combination

Permutation and Combination

Chapter : Permutation and Combination

Topic : Permutation

Related notes