PERMUTATION AND COMBINATIONS
FUNDAMENTAL PRINCIPLE OF COUNTING 1. MULTIPLICATION PRINCIPLE OF COUNTING
If a job can be done in m ways, and when it is done in any one of these ways another job can be done in n, then both the jobs together can be done in mn ways.
2. ADDITION PRINCIPLE OF COUNTING If a job can be done in m ways and another job can be done in n ways then either of these jobs can be done in m + n ways.
PERMUTATIONS
Each of different arrangement which can be made by taking some or all of a number of things is called a permutation.
1. COUNTING FORMULAE FOR PERMUTATION To find the value of "Pr
"P, = n(n-1) (n-2) .....(n-r + 1)
=
n!
(n-r)!
(using factorial notation n! = n(n-1).....
3.2.1.) where 0 <r<n. In particular
• The number of permutations of n different things taken
all at a time = "Pn = n!
"Po = 1, "P₁= n and "Pn-1="Pn = n!
• "P, = n (-¹Pr-1) where r= 1, 2,... n.
3.
PERMUTATION OF n DISTINCT OBJECT WHEN REPETITION IS ALLOWED
• The number of permutations of n different things taken r at time when each thing may be repeated any number of times is n'.
. ARRANGEMENT OF n THINGS WHEN ALL ARE NOT DISTINCT
• The number of permutations of n things taken all at a time, where x are alike of one kind, y are alike of second kind and z are alike of third kind and the rest n- (x + y + z) are all distinct is given by n! x!y!z! (x + y + z≤n)
4.CIRCULAR PERMUTATIONS
In the event of the given n things arranged in a circular or even elliptical permutation and in this case the first and the last thing in the arrangement are indistinguishable the number of permutations is (n-1)!.
NUMBER OF CIRCULAR PERMUTATIONS OF n DIFFERENT THINGS TAKEN r AT A TIME
CASE I: If clockwise and anticlockwise orders are taken as different, then the required number of circular permutations
CASE II: If clockwise and anticlockwise orders are taken as not different, then the required number of circular permutations =
COMBINATIONS
Each of different grouping or selections that can be made by some or all of a number of given things without considering the order in which things are placed in each group, is called combinations.
1. COUNTING FORMULAE FOR COMBINATIONS The number of combinations of n different things taken r at
a time is given by nCr or C (n,r)
"C₁ = n! (n-1) r
(0 ≤r≤n)
as
"P
Key results on nCr "Co = "Cn = 1
"C₁ = n There are n ways to select one thing out of n
distinct things.
"Cr="Cn-r
If n is odd then the greatest value of "Cr is "c or "C"
. If n is even then the greatest value of "Cr is "Cn/2.
6. SELECTION FROM DISTINCT/IDENTICAL OBJECTS (1) SELECTION FROM DISTINCT OBJECTS
The number of ways (or combinations) of selection from n distinct objects, taken at least one of them is "C₂ + "C₂ + "C₂+...+ "C₁ = 2"-1
(II) SELECTION FROM IDENTICAL OBJECTS The number of ways of selections of atleast one out of a₁ + a₂ + a3 ++an + k objects, where a are alike of one kind, ..an are alike of nth kind and k are distinct is (a₁ +1) (a₂ + 1)(a +1) 2-1.
8. DIVISION OF DISTINCT OBJECT IN TO GROUPS In the case of grouping we have the following. If m +n + p things are divided into 3 groups one containing m, the second n and the third p things; number of groupings is
(m+n+p) where m, n, p are distinct natural numbers.
min!p!
In general, the number of ways in which mn different things can be divided equally into m distinct groups is (mn) when (n!)" order of groups is important.
9.DIVISION OF IDENTICAL OBJECTS INTO GROUPS
The number of ways of division or distribution of n identical things into r different groups is n+1Cr-1 or "-¹Cr-1 according as empty groups are allowed or not allowed.
10. ARRANGEMENTS IN GROUPS
The number of ways of distribution and arrangement of n distinct things into r different groups is n! +-¹Cr-1 or n! n-¹Cr-1 according as empty groups are allowed or not allowed.
