Permutations

Warning

Please Login to Read More...

The standard configuration for a Malaysian license plate is 3 letters followed by 4 digits. How many different license plates are possible if digits and letters can be repeated?

Sol: There are 26 choices for each letter and 10 choices for each digit. You can use the fundamental counting principle to find the number of different plates.

No. of diff. plates	=	(26.26.26)(10.10.10.10)
	=	175760000

Fundamental principle of counting

Fundamental principle of counting (multiplication rule): If a first operation can be performed in 'p' ways and a second operation can be performed in 'q' ways, then the two operations together can be performed in 'p × q' ways. For example, if a first operation can be performed in 4 ways and a second operation can be performed in 5 ways, then the two operations together can be performed in 4 × 5 = 20 ways.

The above principle can be extended to the case in which the different operations can be performed in p, q, r, s, ..... ways. In this case, the number of ways of performing all the operations together would be p × q × r × s ..... ways. For example, if four different operations can be performed in 2, 3, 4 and 5 ways, then the four operations together can be performed in 2 × 3 × 4 × 5 = 120 ways.

Fundamental principle of counting (addition rule): If there are two assignments such that they can be performed independently in p and q ways respectively, then either of the two assignments can be performed in (p + q) ways. For example, if there are two assignments such that they can be performed independently in 4 and 5 ways respectively, then either of the two assignments can be performed in 4 + 5 = 9 ways.

Example
You have four posters to paste in your room. You want to put one poster on each wall. How many ways can you arrange the posters?
Sol: You have 4 choices for the first wall. After pasting one, you have 3 choices for the second wall. Similarly, 2 for the third wall, and 1 for the fourth wall. So, the no. of ways you can arrange the posters is 4!. 4! = 4.3.2.1 = 24 There are 24 ways you can arrange the posters.

Factorial Notation

The product of ‘n’ consecutive positive integers beginning with 1 is denoted by n! or and read as ‘factorial n’ or ‘n factorial’. Thus,
n! = 1 . 2 . 3 . . . . . (n – 1)n
= n(n – 1) . . . . . 3 . 2 . 1

Points to remember
• When ‘n’ is a negative integer or a fraction, n! is not defined.
• The factorial of 0, i.e., 0! = 1
• n! = n(n – 1)!
• (2n)! = 2ⁿ . n![1 . 3 . 5 . . . . (2n – 1)]

Example Brain Teaser

Factorial

Example
Find the exponent of 15 in 100!?
Sol:
We have, 15 = 3 × 5
Now, E₃(100!) = 48 and,

∴ Exponent of 15 in 100! = min(24, 48) = 24

Exponent of prime p in n!

Let p be a prime number and n be a positive integer.
Then, the last integer amongst 1, 2, 3, ...., (n – 1), n which is divisible by p is p
where denotes the greatest integer less than or equal to n/p.

For example,

Let E_p(n) denote the exponent of the prime p in the positive integer n. Then,
where s is the largest positive integer such that p^s ≤ n < p^{s + 1}

Derivation

Letters in envelops
Case 1: i^th letter is put in 1^st envelop. In this case, remaining 'n – 2' letters have to be deranged in 'n – 2' envelops. This can be done in d_n–2 ways. Case 2: i^th letter is not put in 1^st envelop. In this case i^th letter is forbidden from being placed in 1^st envelop. This is equivalent to solving the problem with 'n – 1' letters and 'n – 1' envelops: each of 'n – 1' letters forbidden from being put in to exactly one envelop each. Total derangement in this case = d_n–1 Case 1 and Case 2 are mutually exclusive.

Letters in envelops

Case 1: i^th letter is put in 1^st envelop.

In this case, remaining 'n – 2' letters have to be deranged in 'n – 2' envelops.
This can be done in d_n–2 ways.
Case 2: i^th letter is not put in 1^st envelop.

In this case i^th letter is forbidden from being placed in 1^st envelop.
This is equivalent to solving the problem with 'n – 1' letters and 'n – 1' envelops:
each of 'n – 1' letters forbidden from being put in to exactly one envelop each.
Total derangement in this case = d_n–1
Case 1 and Case 2 are mutually exclusive.

Derangements

Derangement is permutation of a set, such that no element appears in it's original position.
Example: Suppose there are n letters which are numbered 1, 2, ..... n.
Let there be 'n' envelops also numbered 1, 2, ... n.
An arrangement where letters are put inside envelops such that no letter is in it's corresponding envelop, is called a derangement.
Let 'd_n' represent the no. of derangements when 'n' letters and 'n' envelops are involved.
Let us put first letter in i^th envelop. This i^th envelop can be selected in 'n – 1' ways.
There are two possibilities, depending on whether i^th letter is put in 1^st envelop in return. The two cases are dealt at the adjacent with the conclusion that the two are mutually exclusive.

∴ Total no. of derangements = (no. of ways of selecting) (d_{n – 2} + d_{n – 1})
⇒ d_n = (n – 1) (d_n–1 + d_n–2)
This is a recursive relation for derangements.
d₁ = 0 (1 letter has only one way of being put in 1 envelop)
d₂ = 1 (letters 1, 2 are put in envelops 2, 1 respectively)
From d₁ = 0, d₂ = 1 and d_n = (n – 1) (d_n–1 + d_n–2),
we can get derangements for any 'n'.
d₃ = (3 – 1) (d_3–1 + d_3–2) = 2 (1 + 0) = 2
d₄ = (4 – 1) (d₃ + d₂) = 3 (2 + 1) = 9
. . . . . . . .
And so on.
From the above, it can be shown that
d_n =

Follow Us


Guided Tour

Get In Touch
Contact Us
support@wonderwhizkids.com
marketing@wonderwhizkids.com