Permutation and Combination

PERMUTATION AND COMBINATION INTRODUCTION The most fundamental application of mathematics is counting. There are many natural methods used for counting This chapter is dealing with various known techniques those are much faster than the usual counting methods. We mainly focus, our methods, on counting the number of arrangements (Permutations) and the number of selections (combinations), even although we may use these techniques for counting in some other situations also. FUNDAMENTAL PRINCIPLE OF COUNTING (Counting Without Actual Counting) If an event A can occur in 'm' different ways and another event B can occur in 'n' different ways, then the total number of different ways of- (a) (b) Ex. Ex. Ex. Sol. Ex. Sol. simultaneous occurrence of both events in a definite order is m× n. This can be extended to any number of events (known as multiplication principle). happening exactly one of the events is m + n (known as addition principle). There are 15 IITs in India and let each IIT has 10 branches, then the IITJEE topper can select the IIT and branch in 15 × 10 = 150 number of ways. There are 15 IITs & 20 NITs in India, then a student who cleared both IITJEE & AIEEE exams can select an institute in (15 + 20) = 35 number of ways. There are 8 buses running from Kota to Jaipur and 10 buses running from Jaipur to Delhi. In how many ways a person can travel from Kota to Delhi via Jaipur by bus? Let E 1 be the event of travelling from Kota to Jaipur & E 2 be the event of travelling from Jaipur to Delhi by the person. E1 can happen in 8 ways and E 2 can happen in 10 ways. Since both the events E1 and E 2 are to be happened in order, simultaneously, the number of ways = 8 × 10 = 80. A college offers 6 courses in the morning and 4 in the evening. The number of ways a student can select exactly one course, either in the morning or in the eveningThe student has 6 choices from the morning courses out of which he can select one course in 6 ways. For the evening course, he has 4 choices out of which he can select one in 4 ways. Hence the total number of ways 6 + 4 = 10. PERMUTATION & COMBINATION (a) Factorial : A Useful Notation : n! = n.(n – 1).(n – 2)..............3. 2. 1 ; n! = n. (n – 1)! where n  N (i) 0! = 1! = 1 (ii) Factorials of negative integers are not defined. (iii) n! is also denoted by n (iv) (2n)! = 2n.n! [1. 3. 5. 7........(2n – 1)] (v) Prime factorisation of n! : Let p be a prime number and n be a positive integer, then exponent of p in n! is n  n   n   n  denoted by Ep (n!) and is given by Ep(n!) =   +  2  +  p 3  + ..... +  p k  p p         where pk < n < pk+1 and [x] denotes the integral part of x. If we isolate the power of each prime contained in any number n, then n can be written as     n = 2 1 · 3 2 · 5 3 · 7 4 .... where i are whole numbers. (b) Permutation : Each of the arrangements in a definite order which can be made by taking some or all of the things at a time is called a PERMUTATION. In permutation, order of appearance of things is taken into account; when the order is changed, a different permutation is obtained. Generally, it involves the problems of arrangements (standing in a line, seated in a row), problems on digit, problems on letters from a word etc. nP denotes the number of permutations of n different things, taken r at a time (n  N, r  W, r  n) r n! nP = n (n – 1) (n – 2) ............. (n – r + 1) = r (n  r)! nP n=  n!, nP0= 1, nP1= n Number of arrangements of n distinct things taken all at a time = n!  nP r is also  (c) denoted by A nr or P(n,r). Combination : Each of the groups or selections which can be made by taking some or all of the things without considering the order of the things in each group is called a COMBINATION. Generally, involves the problem of selections, choosing, distributed groups formation, committee formation, geometrical problems etc. nC denotes the number of combinations of n different things taken r at a time (n  N, r  W, r < n) r n Cr  n! r !(n  r)!  n (i) nCr is also denoted by   or C (n, r). r  (ii) nPr = nCr. r! Ex. Sol. How many three digit can be formed using the digits 1, 2, 3, 4, 5, without repetition of digits? How many of these are even ? Three places are to be filled with 5 different objects.  Number of ways = 5P 3 = 5 × 4 × 3 = 60 For the 2nd part, unit digit can be filled in two ways & the remaining two digits can be filled in 4P 2 ways.  Number of even numbers = 2 × 4P 2 = 24. Ex. Find the exponent of 6 in 50! Sol.  50   50   50   50   50   50  E 2 (50!)                    2   4   8   16   32   64  E2(50!) = 25 + 12 + 6 + 3 + 1 + 0 = 47 E3(50!) = 16 + 5 + 1 + 0 = 22 (where [ ] denotes integral part)  50   50   50   50  E3(50!) =             3   9   27   81  PERMUTATION AND COMBINATION Ex. Sol. If a denotes the number of permutations of (x + 2) things taken all at a time, b the number of permutations of x things taken 11 at a time and c the number of permutations of (x – 11) things taken all at a time such that a = 182 bc, then the value of x is x2 x and Px  2  a P11  b x 11 Px 11  c  a   x  2!  b  c   x  11! x!  x  11!  a = 182bc  x  2  !  1 82  x  1  13 x!  x  11  !  x  1 1 !     x  2  x  1   182  14  13 x  12 Ex. How many 4 letter words can be formed from the letters of the word 'ANSWER' ? How many of these words start with a vowel ? Sol. Number of ways of arranging 4 different letters from 6 different letters are 6 C 4 4 !  6 !  3 6 0 . 2! There are two vowels (A & E) in the word 'ANSWER'. Total number of 4 letter words starting with A : A .......... = 5 C 3 3 !  5!  60 2! Total number of 4 letter words starting with E : E .......... = 5 C 3 3 !  5!  60 2!  Total number of 4 letter words starting with a vowel = 60 + 60 = 120. n n PROPERTIES OF Pr and Cr (I) The number of permutation of n different objects taken r at a time, when p particular objects are always to be included is r!.n–pCr–p (p  r  n) (II) The number of permutations of n different objects taken r at a time, when repetition is allowed any number of times is nr. (III) Following properties of nCr should be remembered : (iii) n C = nC n n r n–r ; C0 = Cn nC + nC n+1C r r–1 = r (v) nC r (vi) nC is maximum when r (i) (IV) = =1 (ii) (iv) nC = nC  x = y or x + y = n x y nC + nC + nC + ............ + nC = 2n 0 1 2 n n n–1 Cr–1 r r n n 1 n 1 if n is even & r  or r  if n is odd. 2 2 2 The number of combinations of n different things taking r at a time, (i) when p particular things are always to be included = n – pCr–p (ii) when p particular things are always to be excluded = n – pCr (iii) when p particular things are always to be included and q particular things are to be excluded  n – p – qCr–p Ex. If 49C3r – 2 = 49C2r + 1, find 'r'. Sol. n Ex. Sol. Ex. Sol. Ex. Sol. Cr = nCs if either r = s or r + s = n. Thus 3r – 2 = 2r + 1  r=3 or 3r – 2 + 2r + 1 = 49  5r – 1 = 49  r = 10  r = 3, 10 If all the letters of the word 'QUEST' are arranged in all possible ways and put in dictionary order, then find the rank of the given word. Number of words beginning with E = 4P4 = 24 Number of words beginning with QE = 3P3 = 6 Number of words beginning with QS = 6 Number of words beginning withQT = 6. Next word is 'QUEST'  its rank is 24 + 6 + 6 + 6 + 1 = 43. There are three coplanar parallel lines. If any p points are taken on each of the lines, then find the maximum number of triangles with vertices at these points. p p p 3 The number of triangles with vertices on different lines = C1 × C1 × C1 = p The number of triangles with two vertices on one line and the third vertex on any one of the other two lines p (p  1) 3 p 2p = C1 { C2 × C1} = 6p. 2 3 2 2 So, the required number of triangles = p + 3p (p – 1) = p (4p – 3) There are 10 points in a row. In how many ways can 4 points be selected such that no two of them are consecutive ? Total number of remaining non-selected points = 6 . . . . . . Total number of gaps made by these 6 points = 6 + 1 = 7 If we select 4 gaps out of these 7 gaps and put 4 points in selected gaps then the new points will represent 4 points such that no two of them are consecutive. x . . x . x . . x . 7 Total number of ways of selecting 4 gaps out of 7 gaps = C4 FORMATION OF GROUPS (I) (i) The number of ways in which (m + n) different things can be divided into two groups such that one of them contains m things and other has n things, is (II) (m  n)! (m  n). m! n! (2n )! . As in any one n! n! 2! way it is possible to interchange the two groups without obtaining a new distribution. (ii) If m = n, it means the groups are equal & in this case the number of divisions is (iii) If 2n things are to be divided equally between two persons then the number of ways : (i) Number of ways in which (m + n + p) different things can be divided into three groups containing m, n & p things respectively is : (ii) (iii) (m  n  p )! , m! n! p! (2n)!  2!. n ! n ! (2 !) m  n  p.... (3n )! . n! n! n! 3! If 3n things are to be divided equally among three people then the number of ways in which it can be done If m = n = p then the number of groups = is (3n)! . (n !)3 PERMUTATION AND COMBINATION (III) In general, the number of ways of dividing n distinct objects into  groups containing p objects each and m groups containing q objects each is equal to Ex. Sol. Sol.  p !l  q!m l !m ! Here p + mq = n 12 different toys are to be distributed to three children equally. In how many ways this can be done ? The problem is to divide 12 different things into three different groups. Number of ways = Ex. n !(l  m)! 12 ! = 34650. 4!4!4! In how many ways can 15 students be divided into 3 groups of 5 students each such that 2 particular students are always together ? Also find the number of ways if these groups are to be sent to three different colleges. Assuming two particular students as one student (as they are always together), we have to make groups of 5 + 5 + 4 students out of 14 students. Therefore total number of ways = 14 ! 5 !5 !4 !2 ! Now if these groups are to be sent to three different colleges, the total number of ways = 14 ! 3! 5 !5 !4 !2 ! Ex. Find the number of ways of dividing 52 cards among 4 players equally such that each gets exactly one Ace. Sol. Total number of ways of dividing 48 cards (Excluding 4Aces) in 4 groups  48 ! (12 !)4 4 ! Now, distribute exactly one Ace to each group of 12 cards. Total number of ways = 48 ! 4! (12 !)4 4 ! Now, distribute these groups of cards among four players  48 ! 48 !  4 !4 !  4! 4 (12 !) 4 ! (1 2 !)4 CIRCULAR PERMUTATION The number of circular permutations of n different things taken all at a time is (n  1) !. If clockwise & anticlockwise circular permutations are considered to be same, then it is Ex. Sol. (n  1)! . 2 In how many ways can we arrange 6 different flowers in a circle? In how many ways we can form a garland using these flowers ? The number of circular arrangements of 6 different flowers = (6 – 1)! = 120 When we form a garland, clockwise and anticlockwise arrangements are similar. Therefore, the 1 number of ways of forming garland = (6 – 1) ! = 60. 2 Ex. Sol. In how many ways can 5 boys and 5 girls be seated at a round table so that no two girls are together? Leaving one seat vacant between two boys, 5 boys may be seated in 4! ways. Then at remaining 5 seats, 5 girls sit in 5! ways. Hence the required number of ways = 4! × 5! Ex. A person invites a group of 10 friends at dinner. They sit (i) 5 on one round table and 5 on other round table, (ii) 4 on one round table and 6 on other round table. Find the number of ways in each case in which he can arrange the guests. Sol. (i) The number of ways of selection of 5 friends for first table is 10C5. Remaining 5 friends are left for second table. (ii) The total number of permutations of 5 guests at a round table is 4!. Hence, the total number of arrangements is 10!4!4! 10! 10C × 4! × 4! =  5 5!5! 25 The number of ways of selection of 6 guests is 10C6. The number of ways of permutations of 6 guests on round table is 5!. The number of permutations of 4 guests on round table is 3! Therefore, total number of arrangements is : 10 C 6 5 ! 3 !  (10 )! (10 )! 5 !3 !  6 !4 ! 24 Principle of Inclusion and Exclusion In the Venn's diagram (i), we get n(A  B) = n(A) + n(B) – n(A B) n(A'  B') = n(U) – n(A  B) In the Venn's diagram (ii), we get U B A U B A (i) (ii) C n(A  B C) = n(A) + n(B) + n(C) – n(A B) – n(B C) – n(A  C) + n(A  B  C) n(A'  B' C') = n(U) – n(A B C) In general, we have n(A1 A2 ........ An)   n( Ai )   n( Ai  Aj )   n( Ai  Aj  Ak )  .....  (1) n  n( A1  A2  ...  An ) i j i jk Ex. Find the number of permutations of letters a,b,c,d,e,f,g taken all at a time if neither 'beg' nor 'cad' pattern appear. Sol. The total number of permutations without any restrictions; n(U) = 7! beg acdf Let A be the set of all possible permutations in which 'beg' pattern always appears : n(A) = 5! cad befg Let B be the set of all possible permutations in which 'cad' pattern always appears : n(B) = 5! cad beg f n(A B) : Number of all possible permutations when both 'beg' and 'cad' patterns appear. n(A B) = 3!. A B U PERMUTATION AND COMBINATION Therefore, the total number of permutations in which 'beg' and 'cad' patterns do not appear n(A'  B') = n(U) – n(A B) = n(U) – n(A) – n(B) + n(AB) = 7! – 5! – 5! + 3!. Arrangement of n Things, Those are not All Different The number of permutations of 'n' things, taken all at a time, when 'p' of them are same & of one type, q of them ar e same & of second typ e, 'r' o f them are same & of a third typ e & the r ema ining n  (p + q + r) things are all different, is Ex. Sol. n! . p! q! r ! In how many ways we can arrange 3 red flowers, 4 yellow flowers and 5 white flowers in a row ? In how many ways this is possible if the white flowers are to be separated in any arrangement ? (Flowers of same color are identical). Total we have 12 flowers 3 red, 4 yellow and 5 white. 12 ! = 27720. 3! 4 !5 ! For the second part, first arrange 3 red & 4 yellow Number of arrangements = This can be done in  Ex. Sol. 7! = 35 ways 3!4! Now select 5 places from among 8 places (including extremes) & put the white flowers there. This can be done in 8C5 = 56. The number of ways for the 2 nd part = 35 × 56 = 1960. How many numbers can be formed with the digits 1, 2, 3, 4, 3, 2, 1 so that the odd digits always occupy the odd places ? There are 4 odd digits (1, 1, 3, 3) and 4 odd places (first, third, fifth and seventh). At these places the odd digits can 4!  6 ways be arranged in 2 !2 ! Then at the remaining 3 places, the remaining three digits (2, 2, 4) can be arranged in  Ex. Sol. 3!  3 ways 2! The required number of numbers = 6 × 3 = 18. Find the total number of 4 letter words formed using four letters from the word ''PARALLELOPIPED'. Given letters are PPP, LLL, AA, EE, R, O, I, D. Cas es 8 A ll dis tinct 2 a like, 2 dis tinct 4 2 8 C4 7 C1  C2 4 2 a like, 2 other a like 3 a like, a dis tinct No. of way of arrangements No. of ways of s election 4 7 7 C1  C2  4C2  C2 C1  C1 C4  4 ! 2 4! 2! 4! 2!2! 7 C1  C1  Total 4! 3! Total 1680 1008 36 56 2780 Total Number of Combination If nCr denotes the number of combinations (selections) of n different things taken r at a time, then n (a) Cr = n P n! = r where r  n ; n  N and r  W. r! r! (n  r)! Given n different objects , the number of ways of selecting atleast one of them is, nC 1 + nC2 + nC3 +........+ nCn = 2n – 1. This can also be stated as the total number of combinations of n distinct things. (b) (i) Total number of ways in which it is possible to make a selection by taking some or all out of p + q + r +......things, where p are alike of one kind, q alike of a second kind, r alike of third kind & so on is given by : (p + 1) (q + 1) (r + 1).........–1. (ii) The total number of ways of selecting one or more things from p identical things of one kind, q identical things of second kind, r identical things of third kind and n different things is given by : (p + 1) (q + 1) (r + 1) 2n –1 (i) nCr = nCn – r (ii) nCr + nCr – 1 = n + 1Cr (iii) nCr = 0 if r  {0, 1, 2, 3........, n} Ex. Fifteen players are selected for a cricket match. (i) In how many ways the playing 11 can be selected ? (ii) In how many ways the playing 11 can be selected including a particular player ? (iii) In how many ways the playing 11 can be selected excluding two particular players ? Sol. (i) (ii) (iii) 11 players are to be selected from 15 Number of ways = 15C11 = 1365. Since one player is already included, we have to select 10 from the remaining 14 Number of ways = 14C10 = 1001. Since two players are to be excluded, we have to select 11 from the remaining 13. Number of ways = 13C11 = 78. Ex. There are 3 books of Mathematics, 4 of Science and 5 of English. How many different collections can be made such that each collection consists of(i) one book of each subject ? (ii) at least one book of each subject ? (iii) at least one book of English ? Sol. (i) C1 × C1 × C1 = 60 5 3 4 (iii) (2 – 1) (2 ) (2 ) = 31 × 128= 3968 3 4 5 3 4 5 (ii) (2 –1) (2 – 1) (2 –1) = 7 × 15 × 31 = 3255 DIVISORS Let N = pa. qb. rc ....... where p, q, r........ are distinct primes & a, b, c....... are natural numbers then : (a) The total numbers of divisors of N including 1 & N is = (a + 1) (b + 1) (c + 1)....... (b) The sum of these divisors is = (p0 + p1 + p2 + ....+ pa) (q0 + q1 + q2 + ....+ qb) (r0 + r1 + r2 + ....+ rc)... (c) Number of ways in which N can be resolved as a product of two factor is = 1 ( a  1) (b  1) ( c  1)...... if N is not a perfect square 2 1 2  ( a  1) (b  1) ( c  1)......  1 if N is a perfect square PERMUTATION AND COMBINATION (i) Every natural number except 1 has atleast 2 divisors. If it has exactly two divisors then it is called a prime. System of prime numbers begin with 2. All primes except 2 are odd. (ii) A number having more than 2 divisors is called composite. 2 is the only even number which is not composite. (iii) Two natural numbers are said to be relatively prime or coprime if their HCF is one. For two natural numbers to be relatively prime, it is not necessary that one or both should be prime. It is possible that they both are composite but still coprime, eg. 4 and 25. (iv) 1 is neither prime nor composite however it is co-prime with every other natural number. (v) Two prime numbers are said to be twin prime numbers if their non-negative difference is 2 (e.g.5 & 7, 19 & 17 etc). (vi) All divisors except 1 and the number itself are called proper divisors. Ex. Find the number of proper divisors of the number 38808. Also find the sum of these divisors. Sol. (i) The number 38808 = 23 . 32 . 72 . 11 Hence the total number of divisors (excluding 1 and itself i.e.38808) = (3 + 1) (2 + 1) (2 + 1) (1 + 1) – 2 = 70 (ii) The sum of these divisors =(20 + 21 + 22 + 23) (30 + 31 + 32) (70 + 71 + 72) (110 + 111) – 1 – 38808 = (15) (13) (57) (12) – 1 – 38808 = 133380 – 1 – 38808 = 94571. Ex. Sol. In how many ways the number 18900 can be split in two factors which are relative prime (or coprime) ? Here N = 18900 = 22 . 33 . 52 . 71 Number of different prime factors in 18900 = n = 4 Hence number of ways in which 18900 can be resolved into two factors which are relative prime (or coprime) = 24–1 = 23 = 8. TOTAL DISTRIBUTION (a) Distribution of Distinct Objects : Number of ways in which n distinct things can be distributed to p persons if (b) Distribution of Alike Objects : Number of ways to distribute n alike things among p persons so that each may get there is no restriction to the number of things received by them is given by : p n none, one or more thing(s) is given by n+p–1Cp–1. Ex. Find the number of solutions of the equation x + y + z = 6, where x, y, z  W. Sol. Number of solutions = coefficient of x6 in (1 + x + x2 + ....... x6)3 = coefficient of x6 in (1 – x7)3 (1 – x) –3 = coefficient of x6 in (1 – x)–3 = 3+6–1C6 = 8C2 = 28. Ex. In how many ways can 5 different mangoes, 4 different oranges & 3 different apples be distributed among 3 children such that each gets alteast one mango ? Sol. 5 different mangoes can be distributed by following ways among 3 children such that each gets atleast 1 : 311 221 5! 5!    Total number of ways :  3!  3 !1 !1 !2 ! 2 !2 !2 !  Now, the number of ways of distributing remaining fruits (i.e. 4 oranges + 3 apples) among 3 children = 37 (as each fruit has 3 options). 5!  5!   Total number of ways   3 !2 ! (2 !)3   7   3 ! 3  Ex. Find the number of non negative integral solutions of the inequation x + y + z  20. Sol. Let w be any number (0 < w < 20), then we can write the equation as : x + y + z + w = 20 (here x, y, z, w  0) Total ways = 23C3 ARRANGEMENTS If nP r denotes the number of permutations (arrangements) of n different things, taking r at a time, then n P r = n (n  1) (n  2)..... (n  r + 1) = n! (n  r)! DEARRANGEMENT There are n letters and n corresponding envelopes. The number of ways in which letters can be placed in the  1 1 (1) n  envelopes (one letter in each envelope) so that no letter is placed in correct envelope is n !1    .....   n!   1! 2! Proof : n letters are denoted by 1,2,3,........,n. Let Ai denote the set of distribution of letters in envelopes (one letter th in each envelope) so that the i letter is placed in the corresponding envelope. Then, n(Ai) = 1 × (n–1)! [since the remaining n–1 letters can be placed in n –1 envelops in (n–1)! ways] Then, n(Ai  Aj) represents the number of ways where letters i and j can be placed in their corresponding envelopes. Then, n(Ai  Aj) = 1 × 1 × (n–2)! Also n(Ai  Aj  Ak) = 1 × 1 × 1× (n–3)! Hence, the required number is n(A1'  A2'  ..... An') = n! – n(A1 A2......... An)  n !   n(A i )   n(A i  A j )   n(A i  A j  A k )  .......  (1)n  n(A i  A 2 .....  A n ) n n n = n! – [ C1(n–1)! – C2(n–2)! + C3(n–3)! + .......+ (–1) n–1 n × Cn1]  1 1 (1)n  n! n!    n !  (n  1)! (n  2 )! .......  (1)n 1   n ! 1    ........   n!  2 !(n  2 )!  1 !(n  1)!   1! 2 ! PERMUTATION AND COMBINATION Ex. Sol. A person writes letters to six friends and addresses the corresponding envelopes. In how many ways can the letters be placed in the envelopes so that (i) All the letters are in the wrong envelopes. (ii) At least two of them are in the wrong envelopes. (i) The number of ways is which all letters be placed in wrong envelopes 1 1 1 1 1 1  –   = 720 = 6!  1     1 ! 2 ! 3 ! 4 ! 5 ! 6 ! 1 1 1  1 1  2 – 6  24  120  720    = 360 – 120 + 30 – 6 + 1 = 265. (i) The number of ways in which at least two of them in the wrong envelopes 1 1 6  6 = C4 . 2!  1    + C3 . 3! 1! 2 ! 1 1 1 6   1  1 !  2 !  3 ! + C2 . 4! 1 1 1 1 1 6  6 – + C1. 5!  1     + C0 6! 1 ! 2 ! 3 ! 4 ! 5 ! = 15 + 40 + 135 + 264 + 265 = 719 1 1 1 1   1  1 !  2 !  3 !  4 ! 1 1 1 1 1 1   1  1 !  2 !  3 !  4 ! – 5 !  6 ! 1. (a) (b) 2. 3. (a) (b) Fundamental Principle of Counting (Counting Without Actually Counting) If an event can occur in ‘m’ different ways, following which another event can occur in ‘n’ different ways, then the total number ofdifferent ways of Simultaneous occurrence of both events in a definite order is m × n. This can be extended to any number of event (known as multiplication principle). Happening of exactly one of the events is m + n (known as addition principle). Factorial A Useful Notation : n! = n (n – 1) (n – 2).........3.2.1; n! = n. (n – 1)! where n  W 0! = 1! = 1 (2n)! = 2n . n! [1. 3. 5. 7.........(2n – 1)] Note that factorials of negative integers are not defined. Permutation nP r denotes the number of permutations of n different things, taken r at a time (n  N, r  W, n  r) nP r = n (n – 1) (n – 2) .............(n – r + 1) = The number of permutations of n things taken all at a time when p of them are similar of one type, q of them are similar of second type, r of them are similar of third type and the remaining n – (p + q + r) are all different is : (c) (d) (e) n! n   r ! n! . p!q!r! The number of permutation of n different objects taken r at a time, when a particular objects is always to be included is r! . n–1Cr–1. The number of permutation of n different objects taken r at a times, when repetition be allowed any number of times is n × n × n ........r times = nr. (i) The number of circular permutations of n different things taken all at a time is : ( n – 1)! = If clockwise & anti-clockwise circular permutations are considered to be same, then it is n Pn . n  n  1! . n (ii) The number of circular permutation of n different things taking r at a time distinguishing clockwise & anticlockwise arrangement is 4. Combination (a) nC r n Pr r denotes the number of combinations of n different things taken r at a time, and n where r  n ; n  N and r  W. nCr is also denoted by   or A nr or C (n, r). r nC r = n P n!  r r! n  r  ! r! PERMUTATION AND COMBINATION (b) The number of combination of n different things taking r at a time. (i) when p particular things are always to be included = n–pCr–p (ii) when p particular things are always to be excluded = n–pCr (iii) when p particular things are always to be included and q particular things are to be excluded = n – p – qCr–p (c) Given n different objects, the number of ways of selecting atleast one of them is, nC1 + nC2 + nC3 + .....+ nCn = 2n – 1. This can also be started as the total number of combinations of n distinct things. (d) (i) (ii) 5. Total number of ways in which it is possible to make a selection by taking some or all out of p + q + r + ...... things, where p are alike of one kind, q alike of a second kind, r alike of third kind & so on is given by : ( p + 1) (q + 1) (r + 1)........– 1. The total number of ways of selecting one or more things from p identical things of one kind ,q identical things of second kind, r identical things of thrid kind and n different things is (p + 1) (q + 1) (r + 1) 2n – 1. n n Properties of Pr and Cr (a) The number of permutation of n different objects taken r at a time, when p particular objects are always to be (b) The number of permutations of n different objects taken r at a time, when repetition is allowed any number (c) Following properties of nCr should be remembered : n C = nC n n (i) (ii) r n–r ; C0 = Cn = 1 n n n+1 (iii) Cr + Cr–1 = Cr (iv) n nC = n–1C (v) r r–1 r included is r!.n–pCr–p (p  r  n) of times is nr. (vi) (d) r n n 1 n 1 if n is even & r  or r  if n is odd. 2 2 2 The number of combinations of n different things taking r at a time, (i) (ii) (iii) 6. nC is maximum when r nC = nC  x = y or x + y = n x y nC + nC + nC + ............ + nC = 2n 0 1 2 n when p particular things are always to be included = n – pCr–p when p particular things are always to be excluded = n – pCr when p particular things are always to be included and q particular things are to be excluded  n – p – qCr–p Circular Permutation The number of circular permutations of n different things taken all at a time is (n  1) !. If clockwise & anticlockwise circular permutations are considered to be same, then it is 7. (n  1)! . 2 Arrangement of n Things, Those are not all Different The number of permutations of 'n' things, taken all at a time, when 'p' of them are same & of one type, q of them ar e same & of second typ e, 'r' o f them are same & of a third typ e & the r ema ining n  (p + q + r) things are all different, is n! . p! q! r ! 8. Divisors Let N = pa. qb. rc ....... where p, q, r .......are distinct primes & a, b, c.......are natural numbers then : (a) The total numbers of divisors of N including 1 & N is = (a + 1) (b + 1) (c + 1)......... (b) The sum of these divisors is = (p0 + p1 + p2 + ......+ pa) (q0 + q1 + q2 + ......+ qb) (r0 + r1 + r2 + .....+ rc)..... (c) Number of ways in which N can be resolved as a product of two factor is = 1  a  1 b  1 c  1 ....... if N is not a perfect sqaure 2 1  a  1 b  1 c  1 ........  1 if N is a perfect square 2 (d) Number of ways in which a composite number N can be resolved into two factors which are relatively prime (or coprime) to each other is equal to 2 n–1 where n is number of different prime factors is N. 9. Division and Distribution (a) (i) The number of ways in which (m + n ) different things can be divided into two groups containing m & n things respectively is : (ii)  m  n ! (m  n) m!n! If m = n, it means the groups are equal & in this case the number of subdivision is  2n ! n!n!2n! ; for in any one way it is possible to inter change the two groups without obtaining a new distribution. (b) (i) Number of ways in which (m + n + p) different things can be divided into three groups containing m, n & (ii) (iii)  m  n  p ! m!n!p!  3n ! . n!n!n!3! If 3n things are to be divided equally among three people then the number of ways in which it can be done  3n ! 3 .  n! In general, the number of ways of dividing n distinct objects into l groups containing p objects each, m groups containing q objects each is equal to (e) n!n! 2! , m  n  p If m = n = p then the number of groups = is (d)  2! . If 2n things are to be divided equally between two persons then the number of ways = p things respectively is (c)  2n ! (iii) n! l  m  !  p!  q! l m l !m! Here p + mq = n Number of ways in which n distinct things can be distributed to p person if there is no restriction to the number of things received by them = pn Number of ways in which n identical things may by distributed among p persons if each person may receive none, one or more things is; n+p–1Cn PERMUTATION AND COMBINATION 10. Total Distribution (a) Distribution of Distinct Objects : Number of ways in which n distinct things can be distributed to p persons if there (b) Distribution of Alike Objects : Number of ways to distribute n alike things among p persons so that each may get is no restriction to the number of things received by them is given by : p n none, one or more thing(s) is given by n+p–1Cp–1. 11. Arrangements If nP r denotes the number of permutations (arrangements) of n different things, taking r at a time, then n 12. P r = n (n  1) (n  2)..... (n  r + 1) = n! (n  r)! Dearrangement Number of ways in which n letters can be placed in n directed envelopes so that no letter goes into its own envelope is n 1   1 1 1 1 = n! 1      ........   1 n!  1! 2! 3! 4! 13. Important Results (a) Number of rectangle of any size in a square of size n × n is n r 3 & number of square of any size is r 1 (b) Number of rectangle of any size in a rectangle of size n × p (n < p) is size is (d) 2 r 1 np (n + 1) (p + 1) & number of squares of any 4 n   n  1  r  p  1  r  r 1 (c) n r If there are n points in a plane of which m(< n) are collinear : (i) Total number of lines obtained by joining these points is nC2 – mC2 + 1 (ii) Total number of different triangle nC3 – mC3 Maximum number of point of intersection of n circles is nP2 & n lines is nC2.