Permutations and Combinations Notes

PERMUTATION AND COMBINATION Page # 1 PERMUTATION AND COMBINATION 1. FACTORIAL NOTATION For example, if three things a, b and c are The continuous product of first n natural given then ab, bc and ac are three different numbers is called factorial groups, because ab and ba will give only one represented and it can be group, similarly bc and cb will give one group by notation n or n! . So n! = 1.2.3......... (n–1) .n and ac and ca will give another group. Thus or = n (n–1) (n–2) ........3.2.1 taking two things out of three different things = n { (n–1) (n–2) ........3.2.1.} a, b and c, the following three groups can be  n! formed : n! = n (n–1)! = n (n–1) (n–2 ) ! ab, bc, ca = n (n–1) (n–2) (n–3) ! n (n–1) ...........(n – r + 1) = The number of combinations of n different things n! (n  r )! taken r at a time is denoted by nC or C (n, r ) n! nC = r r !(n  r )! Some useful results : 0! = 1 4! = 24 5! = 120 2! = 2 6! = 720 10! = 3628800 3! = 6 7! = 5040 9! 8! = 40320 1! = 1 = 362880 So –n! = Meaningless nC r r n(n  1)(n  2).....(n  r  1) r! = 2. FUNDAMENTAL PRINCIPLES OF nC OPERATION When one or more operations n Particular cases : nCr can be accomplished by number of ways then there nC pr r! = n = 1 0 = 1 Some Important Results : * nC * operations without counting them as follows : Fundamental Principle of Multiplication nC = nC r x = * nC r + * nC r = n n–1 . Cr–1 r * nC r = 1 (n  r  1) nCr–1 r then that operation can be completed in m × * nC 1= n ways. * Greatest value of are two principles to find the total number of ways to accomplish one, two, or all of the n–r nC y x + y = nC n+1C r–1 = r Let there are two parts A and B of an operation and if these two parts can be performed in m and n different number of ways respectively, Fundamental Principle of addition : If there are two operations such that they can be done independently in m and n ways respectively, then any one of these two operations can be done by (m + n) number of ways. nC = nC = nC n–1 n = n nC r n/2, when n is even (n–1)/2 or nC (n+1)/2 , when n is odd 4. PERMUTATIONS An arrangement of some given things taking some or all of them, is called a permutation of these things. For Example, three different things a, b and c 3. COMBINATIONS The different groups or selections of a given are given, then different arrangements which number of things by taking some or all at a time can be made by taking two things from the without paying any regard to three given things are called their combinations. their order, are ab, ac, bc, ba, ca, cb PERMUTATION AND COMBINATION Page # 2 Therefore, the number of permutations will be 6. Permutations in which all things are not The number of permutations of n different things different : taken r at a time is nP r nP r, The number of permutations of n things taken where all at a time when p of them are alike and of n! (n  r )! = n ( n–1) (n–2) ..... (n–r + 1) = one kind, q of them The number of permutations of n dissimilar things taken all at a time = nP n = n! are alike and of second kind, r of them are alike and of third kind and n! all remaining being different is p ! q !r! Explanation : If all n things were different Explanation : Arrangement of n things at r then total number of permutations will be n!, places may be done as follows : but if p things are similar, then these p things First we make arrangement for first place which can be mutually arranged only in one way, may be done in n ways. After this, we make Whereas in the case when they were different, arrangement for second place which may be their mutual arrangements could be p!. Similarly done in (n–1) ways. Continuing this process, when q things and r things were different, their we shall find the arrangements for third, fourth....rth places may be done in (n–2), (n–3) ....(n–r +1) ways respectively. Hence total number of permutations of n things taking r at a time Note = n :.nPr = n. n–1 .n P r = . nP n= Difference the total number of permutations is obtained by dividing n! by p! . q! .r!. Note : Above formula is applicable only when all repeated : Pr–1 The number of permutations of n different things taken r at a time when each thing can n–1 between Thus Permutations in which things may be (n–r+1) .nPr–1 nP respectively. n things are taken at a time. = n (n–1) (n–2) .......(n–r +1) .nP 1 mutual arrangements could be q! and r! be used once, twice, .....upto r Permutation and times in any permutation is nr. Combination : In particular, in above case when n things are (a) In combinations the order of things has no taken at a time then total number of permutation role to play, while in permutations the order of things plays an important role. (b) In combinations the different groups are formed by taking some or all given things, while in case of permutations all possible arrangements of things are made in each group. Thus the number of permutations is always is nn. Permutation of numbers when given digits include zero : If the given digits include 0, then two or more digit numbers formed with these digits cannot have 0 on the extreme left. In such cases we find the number of permutations in the following two ways. greater than the number of combinations. (a) (The number of digits which may be used Note: at the extreme left) x (The number of ways in In general, we use the methods of finding combinations in case of forming groups, teams or committees, while the methods of finding permutations are used in forming numbers with the help of digits, words with the help of letters, distribution of prizes etc. which the remaining places may be filled up) (b) If given digits be n (including 0) then total number of m- digit numbers formed with them = because n–1P m–1 nP m - n–1 Pm–1. is the number of such numbers which contain 0 at extreme left.