How many ways are there to select three players from a 5 member tennis team to make a trip to a match at another school?
|
We saw in the last section that, when working with permutations, the order is always important. If we were choosing 3 people from a group of 7 to serve on a committee with no assigned roles, the nature of the problem would change. If we are choosing 3
people from a group of 7 to serve on a committee with no assigned roles then we should consider that any selection from a permutation that includes the same three people should only be counted once. EXERCISES 7.3 PERMUTATIONS and COMBINATIONS Simplified [#permalink]
Fundamental Principles of Counting Here we shall discuss two fundamental principles viz. principle of addition and principle
of multiplication. "If there are two jobs such that one of them can be completed in ‘m’ ways, and another one in ‘n’ ways then the two jobs in succession can be done in ‘m X n’ ways." Example
:- In her class of 10 girls and 8 boys, the teacher has to select 1 girl AND 1 boy. In how many ways can she make her selection? For selecting a boy she has 8 options/ways AND that for a girl 10 options/ways Remark :- The above principle can be extended for any finite number of jobs. Fundamental Principle of Addition "If there are two jobs such that they can be performed independently in ‘m’ and ‘n’ ways respectively, then either of the two jobs can be performed in (m + n) ways." Example :- In her class of 10 girls and 8 boys, the teacher has to select either a girl OR a boy. In how many ways can she make her selection? For selecting a boy she has 8 options/ways OR that for a girl 10 options/ways. The first of these can be performed in 8 ways and the second in 10 ways. Examples 1 :- There are 3 candidates for a classical, 5 for a mathematical, and 4 for a natural science scholarship. I. In How many ways can these scholarships be awarded? Clearly classical scholarship can be awarded to anyone of the 3 candidates, similarly mathematical and natural science scholarship can be awarded in 5
and 4 ways respectively. So, II. In How many ways one of these scholarships be awarded? Number of ways of awarding one of the three scholarships = 3 + 5 + 4 = 12------------------------[ By Fundamental Principle of Addition] Example 2 :- A room has 6 doors. In how many ways can a person enter the room through one door and come out through a different Number of ways coming in the room = 6 By Fundamental Principle of Multiplication--------> Coming in X Going out = 6 X 5 = 30. Example 3 :- Five persons entered the lift cabin on the ground floor of an 8 floor house. Suppose each of them can leave the cabin independently at any floor beginning with the first. Find the total number of ways in which each of the five persons can leave the cabin i) At any one of the 7 floors Let the five persons be b,c,d,e,f I) b can leave the cabin at any of the seven floors. So he has 7 options II) b can leave the cabin in 7 ways. c can leave the cabin in 6 ways, since he can
not leave at where b left. In the same way d has 5, e has 4, and f has 3 way. Example 4 :- In how many ways can 3 prizes be distributed among 4 boys, when i) No boy gets more than one prize ? I) The first prize can be given away to any of the 4 boys, hence there are 4 ways to distribute first prize. II) First prize to any one of the 4 boys. Similarly second to any one of the 4 boys, and third as well to any one of the 4 boys = 4 X 4 X 4 = 43 = 64 III) Since any one of the 4 boys may get all the prizes. So, the number of ways in which a boy gets all the 3 prizes = 4 Permutations (Arrangement) nPr Each of the arrangements which can be made by taking some or all of a number of things is called a permutation. For example, if there are three objects namely x,y, and z, then the permutations of these objects, taking two at a time, are xy, yx, yz, zy, xz, zx = Total 6 Permutations. NOTE :- It should be noted that in permutations the order of arrangement is taken into account; When the order is changed, a different permutation is obtained.
It is nPr i.e. Number of all permutations all n distinct things taken r at a time (1 ≤ r ≤ n) = nPr = \(\frac{n!}{(n-r)!}\) We will try to know how it is. We will try to prove it by a numerical example. In how many different ways would you arrange 5 persons on 3 chairs Here n= 5 and r= 3 Arranging 5 persons on 3 chairs is same as filling 3 places when we have 5 different things at our disposal. The first place can be filled in 5 ways -------------(Remember Fundamental Principal of Multiplication) Having filled it, there are 4 things left and anyone of these 4 things can be used to fill second place. So the second place can be filled in 4 ways. Hence by fundamental principal of multiplication, the first two places can be filled in 5 X 4 ways When the first two places are filled, there are 3 things left, so that the third place be filled in 3 ways So the total number of arrangements will be 5 X 4 X 3. As per the formula of permutation it will be 5P3 = \(\frac{5!}{(5-3)!}\) = \(\frac{5!}{2!}\) = 5 X 4 X 3 Remark :- Continuing in this manner we can say that number of permutations (or arrangements ) of n things taken all at a time will be n! Example 1 :- It is required to seat 4 Women and 5 Men in
a row so that the women occupy the even places. How many such arrangements are possible? By Fundamental Principle of Multiplication, Total number of arrangements will be 4! X 5! = 24 X 120 = 2880 Example 2 :- Three men have 4 coats, 5 waist coats, and 6 caps. In how many ways can they wear them? Number of ways in which 3 Men can wear 4 coats = \(\frac{4!}{1!}\) = 4! = 24 By Fundamental Principle of Multiplication Arrangement of 4 Coats AND Arrangement of 5 Waist Coats AND Arrangement of 6 Caps Total number of ways = 24 X 60 X 120 = 172800 NOTE
:- It is unlikely that GMAT will ask such an question in the real test, since it involves tedious calculations. However the idea behind putting this here is to show how the Fundamental Principle of Counting works. Lets modify the above question Three men have 4 coats, 5 waist coats, and 6 caps. In how many ways can they wear any one type of them? Number of ways in which 3 Men can wear 4 coats = \(\frac{4!}{1!}\) = 4! = 24 By Fundamental Principle of Addition Arrangement of 4 Coats OR Arrangement of 5 Waist Coats OR Arrangement of 6 Caps Total number of ways = 24 + 60 + 120 = 204 Example 3 :- How many four digit numbers are there with distinct digits Total Number of arrangements = \(\frac{10!}{(10-4)!}\) But these arrangements also include those numbers which have zero (0) at thousand’s place. Example 4 :- Find the sum of all the numbers that can be formed with the digits 2, 3, 4, and 5 taken all at a time. Total Number of numbers = 4! = 24 To find the sum of these 24 numbers, we will find the sum of digits at Unit’s, Ten’s, hundred’s, and thousand’s places in all these numbers. Keep 2 at unit’s place. _ _ _ 2 By other Way (2 + 3 + 4 + 5) 3! = 84 -------------> 84 (100 + 101 + 102 + 103) = 93324 Next Case :- What if repetition of digits would have been allowed? Keeping 2 at unit’s place. _ _ _ 2 we would get 4 X 4 X 4 = 64 numbers. The similar example is discussed at http://gmatclub.com/forum/what-is-the-s ... l#p1164866 Example 5 :- There are 6 periods in each working day of a school. In how many ways can one arrange 5 subjects such that each subject is allowed at least one period? 5 periods can be arranged in 6 periods in 6P5 ways. Now one period is left and it can be allotted to any
one of the 5 subjects. So number of ways in which remaining one period can be arranged is 5. A Probability Question on the same logic is here. http://gmatclub.com/forum/combinatorics ... l#p1209126 Permutations under Certain Conditions Here we shall see permutations where either repetitions of items are allowed or distinction between some of the items is ignored or a particular item occurs in every arrangement etc. First Some Theoretical ( boring?) Part 1) Permutations of n different objects taken r at a time, when a particular object is to be always included in each arrangement is r(n-1Pr-1) Objects = n Places to be filled = r Condition = A Specific Object (lets say x) should always be included in each arrangement. We will place this x at first place. Now we are left with n-1 objects and r-1 places. We can arrange the n-1 objects at r-1 places in n-1Pr-1 ways (NOTE Our X was at 1st place in these arrangements) So each time we push x one place ahead by one position (i.e. 2nd, 3rd,4th,…….rth), we will get n-1Pr-1 new ways of arranging n-1 at r-1 places. How many places can x go ? r places right! So Total Permutations = n-1Pr-1 + n-1Pr-1 + n-1Pr-1 …………r times = r(n-1Pr-1) 2) Permutations of n different objects taken r at a time, when a particular object is never taken in each arrangement is n-1Pr Since a particular object is never taken. So, we have to determine the number of ways in which r places can be filled with n-1 distinct objects. Example 1 :- Make all arrangement of letters of the word PENCIL so that i) N is always next to E I) Let’s keep EN together and consider it one letter. Now we have 5 letters which can be arranged in a row in 5P5 = 5! = 120 ways. II) Solve as above. Just keep in mind that now E and N can interchange their places in 2! Ways. So total arrangements = 5!2! = 240 Example 2 :- A Tea Party is arranged for 16 persons along two sides of a long table with 8 chairs on each side. 4 Persons wish to sit on one particular and 2 on the other side. How many arrangements are possible? Let the Sides be A and B Let 4 persons wish to sit at side A. They can sit in 8P4 ways. Similarly 2 Persons can sit on other side in 8P2 Now we are left with 10 places and 10 persons. So they can be arranged in 10! Ways. Total Number of Arrangements = 8P4 X 8P2 X 10! Permutations of Objects not all distinct \(\frac{n!}{p!q!}\) Many of us may be familiar and adept in solving problems pertaining to this concept For example if I ask, How many words (with or without meaning) can be formed using all digits of the word INDIA Almost everybody will say it is \(\frac{5!}{2!}\) Why we need to do this division? We will first look the Theorem underlying above Let’s say n is such that n=p+q where p is set of p alike things and q is set of q alike things Lets x is the total permutations of n Let n=5, p=3, q=2 -----------------let’s consider the integers 3,3,3,2,2 where n=33322, p=333, q=22 Now Replace p alike things by p distinct things--------------- Replace integers 3,3,3 by integers 4,5,6 These replaced integers 4,5,6 could have been permuted themselves in p! or 3! or 6 ways. Similarly Replace q alike things by q distinct things--------------- Replace integers 2,2 by integers 7,8 These replaced integers 7,8 could have been permuted themselves in q! or 2! or 2 ways. Now we
know x is the total number of permutations of n. If all the terms in set P and Q were different the total number of permutations of n would have been So x = \(\frac{n!}{p!q!}\) ---------- x = \(\frac{120}{12}\) ------> x=10 REMARK :- The total number of permutations of n things, of which p are alike of one kind, q are alike of second kind Example 1 :- How many words would you form with the letters of the word MISSISSIPPI Example
2 :- APPLE Circular Permutations (n-1)! So far we have discussed linear permutations. The basic difference between linear permutations and circulations is that every linear arrangement has a beginning and an end, but there is nothing like beginning or end in a circular permutation. Thus, in circular permutations, we consider one object as fixed and the remaining objects are arranged as in case of linear arrangement. Thus Total number of circular arrangement of n distinct objects is (n-1)!
Example 1:
(5-1)! = 4! = 24 ii) In how many of these arrangements will two particular persons be next to each other? Consider two particular persons as one person. We have 4 persons in all. These 4 persons can be seated around a circular table in (4-1)! = 3! Ways. But two Particular persons can be arranged between themselves in 2! Ways Example 2: - Solve this question in
light of above explanation. OA and OE can be found in spoiler. A) 19! X 2 Answer C Example 3 :- In how many ways can a party of 4 men and 4 women be seated at a circular table so that no two women are adjacent? The 4 men can be seated at the circular table such that there is a vacant seat between every pair of men in (4-1)! =3! Ways. Now 4 vacant seats can be occupied by 4 women in 4! Ways. Hence the required number of seating arrangements = 3! X 4! = 144 Combinations (Selection) nCr So far we have discussed Permutations (arrangements) of a certain number or objects by taking some of them or all at a time. Most of the times, we are only interested in selection of objects and not their arrangements. In other words, we do not want to specify the ordering of selected objects. Suppose there are three objects namely x,y, and z. We are asked to calculate the permutations (arrangements) of these objects taking 2 at a time Now we are asked to calculate the combinations (selections) of these objects taking 2 at a time Note the important difference here. In later case we did not differ between xy and yx, as we did in the first case. This is the only difference between Permutations and Combinations. In Combinations we find different ways of choosing r objects from n given objects While in Permutations we find different ways of choosing r objects from n given objects and ways of arranging these r objects. The formula of permutations(nPr) itself says first selection (nCr) and then arrangement (r!) nPr = nCr X r! \(\frac{n!}{(n-r)!}\) = \(\frac{n!}{r!(n-r)!}\) X r! -----------> \(\frac{n!}{(n-r)!}\) = \(\frac{n!}{(n-r)!}\) Difference between A Permutation and Combination. 1. In a combination, the ordering of the selected objects is immaterial, whereas in a permutation, the ordering is essential. For example a,b and b,a are same as combinations but different as permutations. 2. Each Combination Correspond to many permutations. For example, the six permutations ABC, ACB, BCA, BAC, CBA, and CAB correspond to the same combination ABC 3. Generally we use the word ‘arrangements’ for permutations and the word ‘selections’ for combinations. Example 1 :- From a class of 32 students, 4 are to be chosen for a competition. In how many ways can this be done? Example 2 :- 3 Gentlemen and 3 Ladies are candidates for 2 vacancies. A voter has to vote for 2 candidates. In how many ways can one cast her/his vote. In all there are 6 candidates and a voter has to vote for any 2 of them. So he can select 2 candidates from 6 candidates in 6C2 ways = \(\frac{6!}{4!2!}\) = \(\frac{(6 X 5)}{2}\) = 5 X 3 = 15 Example 3 :- In how many ways can a cricket eleven be chosen out of a batch of 15 players if i) There is no restriction on the selection = 15C11 ii) A Particular Player is always chosen = 14C10 iii) A Particular Player is never chosen = 14C11 Example 4 :- Out of 2 Women and 5 Men, a committee of 3 is to be formed. In how many ways can it be formed if at least one woman is to be included? A Committee can be formed in the following ways 1 woman AND 2 men OR 2 women AND 1 man 2C1 X 5C2 + 2C2 X 5C1 = 20 + 10 = 30 Example 5 :- (Pay special attention here, because things to be arranged are identical) In how many ways can 7 plus(+) signs and 5 minus (-) signs be arranged in a row so that no two minus signs are together? The Plus signs can be arranged in only one way, because all are identical. | |+| |+| |+| |+| |+| |+| |+| | There are 8 boxes available for placing 5 minus signs. So 5 boxes can be chosen out of 8 boxes in 8C5 ways. However since 5 minus signs are identical, they can be placed in 5 chosen boxes in only one way So Total number of possible arrangements = 1 X 8C5 X 1 = 56 Other Important Concepts in Permutations and Combinations
Let there be n distinct things and you have told to choose any number things out of n things each thing you can either select or deselect. So you get two options for dealing with each thing. There are n things and you have 2 options for each thing. In all you will have 2 X 2 X 2 X 2 X 2 X……………………n times options -------By Fundamental Principle of Multiplication So there will be \(2^n\) options with you for selection Example :- Number of ways Shreya can or cannot eat sweets at a party out of 10 distinct sweets available at party = \(2^10\) Corollary = \(2^n\) – 1 = When zero selections are not allowed. i.e. If Shreya has asked to select at least one sweet. Note :- This is especially important in SET concept. For example let the Set A = (1,2,3) Question :- How many subsets does the Set A have. Solution :- We know a subset can be formed by taking any number of elements (or even zero) from its superset. So the number of subsets of Set A will be \(2^3\) = 8
(Here n=3 because Set A have 3 distinct elements) 2) n+1 = Selection of any number of things out of n identical things Selection of any number of balls from 3 red balls. Zero ball selected – 1 way One ball selected – 1 way Two balls selected – 1 way Three balls selected – 1 way Total (3 +1 ) = 4 ways.
5) nC3 - rC3 = Number of triangles formed by n points of which r are collinear
8) If n is even, then nCr will be maximum for r = \(\frac{n}{2}\) Regards, _________________ How many ways can we select 3 students out of a group of 5 students to stand in a line for a picture only write the number?By the product rule, there are 5 · 4 · 3 = 60 ways to select three students from a group of five students to stand in line for a picture.
How many possible combinations of 3 items from a group of 5 are possible?So 5 choose 3 = 10 possible combinations.
How many ways are there to select 5 players from a 10 member tennis team?5! Therefore, the number of ways of selecting a committee of 5 members from a group of 10 persons is 252.
How many ways can basketball team of 5 players be chosen from 8 players?∴ The required number of ways is 21.
|
