PERMUTATION AND COMBINATION
[Link] CLASS11
INTRODUCTION
Suppose you have a suitcase with a number lock. The number
lock has 4 wheels each labelled with10 digits from 0 to 9. The lock
can be opened if 4 specific digits are arranged in a particular
sequence with no repetition. Some how, you have forgotten this
specific sequence of digits. You remember only the first digit which is
7. In order to open the lock, how many sequences of 3-digitsyou
may have to check with? To answer this question, you may,
immediately, start listing all possible arrangements of 9 remaining
digits taken 3 at a time. But, this method will be tedious, because the
number of possible sequences may be large. Here, in this Chapter,
we shall learn some basic counting techniques which will enable us
to answer this question without actually listing 3-digitarrangements.
In fact, these techniques will be useful in determining the number of
different ways of arranging and selecting objects without actually
listing them. As a first step, we shall examine aprinciple which is
most fundamental to the learning of these techniques.
OVERVIEW
The study of permutations and combinations is concerned
with determining the number of different ways of
arranging and selecting objects out of a given number of
objects without actually listing them. There are some
basic counting techniques which will be useful in
determining the number of different ways of arranging or
selecting objects. The two basic counting principle are
given below:
FUNDAMENTAL PRINCIPLE OF COUNTING
MULTIPLICATIVE PRINCIPLE
Suppose an event E can occur in m
different ways and associated with
each way of occurring of E,
another event F can occur in n
different ways, then the total
number of occurrence of the two
events in the given order is m × n.
ADDITION PRINCIPLE
If
an event E can occur in m
ways and another event F can
occur in n ways, and suppose
that both can not occur
together, then E or F can occur
in m + n ways.
PERMUTATION
A permutation is an arrangement of objects in a definite
order.
The number of permutations of n objects taken all at a
time, denoted by the symbol nPn ,
is given by nPn = n …………. (1)
where n = n(n – 1) (n – 2) ... 3.2.1, read as factorial n, or
n factorial. The number of permutations of n objects
taken r at a time, where 0 < r ≤ n,
denoted by nPr , is given by nPr = n / n-r
We assume that 0 = 1
WHEN REPETITION OF OBJECT IS
ALLOWED
The number of permutations of n things taken all at a
time, when repetion of objects is allowed is n Xn. The
number of permutations of n objects, taken r at a time,
when repetition of objects is allowed, is nr.
PERMUTATION WHEN THE OBJECTS ARE
NOT DISTINCT
The number of permutations of n objects of which p1 are
of one kind, p2 are of second kind,..., pk are of kth kind
and the rest if any, are of different kinds is
n!/p1! p2! ……pk!
COMBINATION
On many occasions we are not interested in arranging
but only in selecting r objects from given n objects. A
combination is a selection of some or all of a number of
different objects where the order of selection is
immaterial. The number of selections of r objects from
the given n objects is denoted by nCr , and is given by
nCr = n!/ r! (n-r)!
REMARKS
1. Use permutations if a problem calls for the number of
arrangements of objects and different orders are to be
counted.
2. Use combinations if a problem calls for the number of
ways of selecting objects and the order of selection is not
to be counted.
SOME IMPORTANT RESULTS
Let n and r be positive integers such that r ≤ n. Then
(i) nCr = nCn – r
(ii) nCr + nCr – 1 = n + 1Cr
(iii) n n – 1Cr – 1 = (n – r + 1) nCr –1
EXAMPLE 1
In a class, there are 27 boys and 14 girls. The teacher
wants to select 1 boy and 1 girl to represent the class for
a function. In how many ways can the teacher make this
selection?
Solution
Here the teacher is to perform two operations:
(i) Selecting a boy from among the 27 boys and
(ii) Selecting a girl from among 14 girls.
The first of these can be done in 27 ways and second can
be performed in 14 ways. By the fundamental principle of
counting, the required number of ways is 27 × 14 = 378.
EXAMPLE2
(i) How many numbers are there between 99 and 1000 having
7 in the units place?
(ii) How many numbers are there between 99 and 1000
having at least one of their digits 7?
Solution
(i) First note that all these numbers have three digits. 7 is in
the unit’s place. The middle digit can be any one of the 10 digits
from 0 to 9. The digit in hundred’s place can be any one of the
9 digits from 1 to 9. Therefore, by the fundamental principle of
counting, there are 10 × 9 = 90 numbers between 99 and 1000
having 7 in the unit’s place.
(ii) Total number of 3 digit numbers having at least one of
their digits as 7 = (Total numbers of three digit numbers) –
(Total number of 3 digit numbers in which 7 does not appear
at all). = (9 × 10 × 10) – (8 × 9 × 9) = 900 – 648 = 252.
THANK YOU