- Fundamental Principle of Counting (XI-6.1)
- Permutations (XI-6.2)
- Permutations when all the Objects are Distinct (XI-6.2)
- Factorial Notation (XI-6.2)
- Derivation of the formula for n^P_r (XI-6.3)
- Permutations when all the objects are not distinct object (XI-6.3)
- Combinations (XI-6.4)
- Miscellaneous Exercise (XI-6)
The unit place can be filled by any one of the digits 1, 2, 3, 4 and 5.
So the unit place can be filled in 5 ways. Now four digits left. So the
tens place can be filled in 4 ways. The hundreds place can be filled in 3
ways by the remaining 3 digits because repetition of digits is not
allowed.
Total number of 3-digits numbers
Here the unit place can be filled by any one of the digits 2, 4, 6. So
the unit place can be filled in 3 ways. Now the tens and hundreds place
can be filled by any one of the digits 1, 2, 3, 4, 5, 6. So the tens and
hundreds place can be filled in 6 ways each.
Total number of 3-digit even numbers
Here the unit place can be filled by any one of the first 10 letters of
the English alphabet. So the unit place can be filled in 10 ways. The
tens place can be filled in 9 ways by remaining 9 letters of the English
alphabet. The hundreds place can be filled in 8 ways by remaining 8
letters of the English alphabet.
The thousands place can be filled in 7 ways by the remaining 7 letters of the English alphabet.
Total number of 4-letter code numbers
=7×8×9×10=5040
.
According to the problem, 2-digits i.e. 6 and 7 are fixed. Thus, 10 - 2 = 8-digits can be used in constructing the telephone numbers. There are 8-digits 0, 1, 2, 3, 4, 5, 8, 9. The first number can be selected in 8 ways. After the selection of the first digit, we have 8 - 1 = 7-digits in hand, second digit can be selected in 7 ways and the third digit can be selected in 6 ways. According to the fundamental principle of multiplication (FPM), the number of ways of selecting a digit for remaining three places: = 8 7 × × 6 = 336 ways
The coin is tossed first time and the number of outcomes is 2. Now the coin is tossed twice and the number of outcomes is 2 again. Also the coin is tossed thrice and the number of outcomes is 2 again. ∴ Total number of outcomes in tossing a coin 3 times =2×2×2=8
Here the upper place of the flag can be fil1ed in 5 ways by using the 5 flags of different colours. Now the lower place of the flag can be filled in 4 ways by using the remaining 4 flags of different colours. Total numbers of signals =4×5=20
8!=8×7×6×5×4×3×2×1=40320
4!−3!=4×3×2×1−3×2×1=24−6=18
3!+4!=3×2×1+4×3×2×1=6+24=30 , 7!=7×6×5×4×3×2×1=5040 , 3!+4!≠7!
Each of different arrangement which can be made by taking some or all of a number of things is called a permutation. It is assumed that
∙ the given things let us say there are n of them are all distinct, that is, no two are alike.
∙ the arrangement is one of placing one thing next to another as in a straight line; hence it is also known as linear permutation.
∙ In any arrangement any one thing is used only once. In other words, there is no repetition.
3.1 COUNTING FORMULAE FOR PERMUTATION
To find the value of nPr
Suppose there are r blank spaces in a row and n different letters. The number of ways of filling up the blank spaces with n different letters is the number of ways of arranging n things r at a time, i.e. nPr. It must be noted that each space has to be filled up with only one letter.
1 |
2 |
3 |
|
r |
|
|
|
|
|
The
first space can be filled in n
ways. Having filled it, there are n
– 1 letters left and therefore the second space can be filled in n
– 1 ways. Hence the first two spaces can be filled in
n(n
– 1) ways. When the first two spaces are filled, there are n
– 2 letters left, so that the third space can be filled in n
– 2 ways. Therefore the first three spaces can be filled in n(n
– 1) (n
– 2) ways; proceeding like this, the r
spaces can be filled in n(n
– 1) (n
– 2) ... [n
– (r
– 1)] ways.
The number of permutations of n things taken r at a time is denoted as nPr and its value is equal to: nPr = n (n − 1) (n − 2) …….. (n − r + 1)
= (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 = nPn = n!
∙ nP0 = 1, nP1 = n and nPn−1 = nPn = n!
∙ nPr = n (n−1Pr−1) where r = 1, 2, …….. n
Question: Prove from definition that nPr = n n−1Pr−1 and hence deduce the value of nPr.
1 |
2 |
3 |
|
r |
|
|
|
|
|
Solution: Suppose there are n different letters and a row of r blank spaces, each of which has to be filled up with one letter. The number of ways of filling up the blank spaces is the number of ways of arranging n things r at a time, i.e., .
The first space can be filled in n ways. Having filled it, there are n – 1 letters left, and r – 1 spaces to be filled. By definition, the number of ways of filling up the r – 1 spaces with n – 1 letters is the number of ways of arranging n – 1 things r – 1 at a time, i.e. .
∴ the number of ways of filling up the r blank spaces with n different letters is
i.e.,
∴
∴
Proceeding like this, we have
Note that the last term is formed as
Evidently,
∴ = n (n – 1) (n – 2) (n – 3) …. (n – r + 2) (n – r + 1).
In particular,
= n (n – 1) …. 1 = n !
i.e., the number of permutations of n things, taken all at a time is n ! .
Question: Show that .
Solution: =
=
= (Q (n − r )! = (n − r ) (n − r − 1) !)
=
A common sense interpretation of the identity above is possible. The number of permutations of r things which may be made from n things, contain one specified thing and do not contain that specified thing and these two together give .
3.2 IMPORTANT RESULTS
Number of permutations under certain conditions:
∙ Number of permutations of n different things, taken r at a time, when a particular thing is to be always included in each arrangement is r n−1Pr−1.
∙ Number of permutations of n different things, taken r at a time, when a particular thing is never taken in any arrangement is n−1Pr.
∙ Number of permutations of n different things, taken r at a time, when m particular things are never taken in any arrangement is n−mPr.
∙ Number of permutations of n different things, taken all at a time, when m specified things always come together is (m !) (n − m + 1) !.
∙ Number of permutations of n different things, taken all at a time, when m specified things never come together is n! − m! (n − m + 1) !.
Question: Find the number of permutations of n different things taken r at a time so that two particular things are always included and are together.
Solution: The
two things can be combined as one unit. The remaining (n
– 2) things may be permuted (r
– 2) at a time in n−2Pr−2
ways. In each arrangement of these (r
– 2) things, are created
(r
– 1) spaces in which the unit of two things can be placed. Further
the two things in the unit may be interchanged. The number of
permutations is
Question: In how many ways can m persons entering a theatre, be seated in two rows each containing n seats with condition in the first row, no two sit in adjacent seats (2m ≤ n)?
Solution: Suppose k persons are seated in the first row where 0 ≤ k ≤ m. In the first row, there are n seats of which n – k are vacant; and the k seats between any two of the vacants have positions in (n – k + 1) spaces.
∴ The number of seating arrangements for the 1st row = (n − k + 1)Pk
The number of seating arrangements is
providing for none, one or…. All the m persons being seated in the first row.
3.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 r.
In other words if a job can be completed in n ways and it is to be repeated r number of times then the total number of ways is n r.
As an example the number of 5 digit numbers, in which digits are not repeated is 9(9p4) while when repetition is allowed is 9 × 104.
Also if n distinct things are arrangement at r places when repetition is allowed, then the number of arrangements are .
Question: There are m men and n monkeys (n > m). If a man have any number of monkeys. In how many ways may every monkey have a master?
Solution: The first monkey can select his master by m ways, and after that the second monkey can select his master again by m ways, so can the third. And so on, hence all monkeys can select master by = m × m × m …. up to n times = (m)n ways.
Question: Show that the total number of permutations of n different things taken not more than ‘r’ at a time, each being allowed to repeat any number of times, is .
Solution: Number of a permutations taken one at a time = n
Number of permutations taken two at a time = n2
.. .. .. .. .. .. .. .. .. .. .. ..
Number of permutations taken r at a time = n r
Total number of permutations
= n + n2 + n3 + ……… + n r
Question: In a steamer there are stalls for 12 animals, and there are cows, horses, and calves (not less than 12 of each) ready to be shipped; in how many ways can the shipload be made?
Solution: The first stall can be occupied by a cow, a horse or a calf, i.e., it can be occupied in 3 ways. The second stall can also be occupied in 3 ways. Therefore the first 2 stalls can be occupied in 32 ways. Proceeding like this, it is clear that the 12 stalls can be occupied in 312 ways, i.e., in 531441 ways.
3.4 ARRANGEMENT OF n THINGS WHEN ALL ARE NOT DISTINCT
∙ If given n things are not all distinct, then it is possible that few many be of one kind, and few others may be of second kind, etc. In such case, the number of permutations of n things taken all at a time, where p are alike of one kind, q are alike of second kind and r are alike of third kind and the rest n − (p + q + r) are all distinct is given by
(p + q + r ≤ n)
Question: Find the number of ways in which we can arrange four letters of the word MATHEMATICS.
Solution: The letters of the word MATHEMATICS are (M, M), (A, A), (T, T), H, E, I, C and S, making eight distinct letters. We can choose four out of them in 8C4 = 70 ways, and arrange each of these sets of four in 4! = 24 ways, yielding (70) (24) = 1680 arrangements. Second, we can choose one pair from among the three identical letter pairs, and two distinct letters out of the remaining seven in (3C1) (7C2) = (3) [(7 × 6)/2] = 63 ways. The letters so obtained can be arranged in 4!/2! = 12 ways, so the number of arrangements in this case is (63) (12) = 756. Finally, we can choose two pairs out of the three identical letter pairs. This can be done in 3C2 = 3 ways and the letters obtained can be arranged in 4!/2!2! = 6 ways, so that the number of arrangements in this last case is (3) (6) = 18. Hence the total number of arrangements is 1680 + 756 + 18 = 2454.
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.
5.1 COUNTING FORMULAE FOR COMBINATIONS
The number of combinations (selections or groupings) that can be formed from n different objects taken r at a time is denoted by nCr and its value is equal to
(0 ≤ r ≤ n)
as
as in a permutation the arrangement of r selected objects out of n, is done in r! ways and in combination arrangement in a group is not considered.
In particular
∙ nC0 = nCn = 1 i.e. there is only one way to select none or to select all objects out of n distinct objects.
∙ nC1 = n There are n ways to select one thing out of n distinct things.
∙ nCr = nCn−r
Therefore nCx = nCy ⇔ x = y or x + y = n.
∙ If n is odd then the greatest value of nCr is or .
∙ If n is even then the greatest value of nCr is nCn/2.
Question: Prove that product of r consecutive positive integer is divisible by r ! .
Solution: Let
r
consecutive positive integers be (m),
(m
+ 1), (m
+ 2), ….. , (m
+ r
−
1), where
m
∈
N.
∴ Product = m(m + 1) (m + 2) ….. (m + r − 1)
=
=
which is divisible by r ! (Q m+r−1Cr is natural number)
Question: Show
that the number of triangles whose angular points are at the vertices
of a given polygon of n
sides but none of whose sides are the sides of the polygon is
.
Solution: For any triangle to be possible, 3 of the n vertices are to be chosen. This can be done in nC3 ways. Of these there are n triangles with two sides as adjacent sides of the polygon – like side 1 and side 2; side 2 and side 3 etc, the third side of the triangle being the corresponding diagonal; and there are, with one side of the polygon as a side of the triangle, (n – 4) triangles.
∴ Required number of triangles = nC3 − n − n (n − 4)
Question: Six X’s have to be placed in spaces on the adjoining Figure so that each row contains at least one X. In how many different ways this can be done?
Solution: If there be no restriction on the placing of the X’s, the number of ways is 8C6 = 8C2 = 28. Of these there are two ways in which the X ;s can be placed; one, with the first row empty and the other with the third row empty. These two cases only do not satisfy the condition.
∴ the number of ways = 28 – 2 = 26.
Question: A bag contains 23 balls in which 7 are identical. Then find the number of ways of selecting 12 balls from bag.
Solution: Here n = 23, p = 7, r = 12 (r > p)
Hence,
required number of selections =
= 16C5 + 16C6 + 16C7 + 16C8 + 16C9 + 16C10 + 16C11 + 16C12
= (16C5 + 16C6) + (16C7 + 16C8) + (16C9 + 16C10) + (16C11 + 16C12)
= 17C6 + 17C8 + 17C10 + 17C12 ( nCr + nCr−1 = n+1Cr)
= 17C11 + 17C9 + 17C10 + 17C12 ( nCr = nCn−r)
= (17C11 + 17C12) + (17C9 + 17C10)
= 18C12 + 18C10 = 18C6 + 18C8
Solution: The following three methods of approach are indicated.
(i) Number of ways of forming the party
= since is the number of ways of making up the party with both the specified guests included.
= 495 – 210 = 285
(OR)
(ii) Number of ways of forming the party
= Number of ways of forming without both of them
+ Number of ways of forming with one of them and without the other
(OR)
(iii) Split the number of ways of forming the party
= those with one of the two (say A) + those without A
∙ The number of ways in which r objects can be selected from n objects if m particular objects are identical is or according as r ≤ m or r > m.
∙ The number of ways in which r objects can be selected from n distinct objects if a particular object is always included is n−1Cr−1.
∙ The number of ways in which r objects can be selected from n distinct objects if a particular object is always excluded is n−1Cr.
∙ The number of ways in which r objects can be selected from n distinct objects if m particular objects are always included is n−mCr−m.
∙ The number of ways in which r objects can be selected from n distinct objects if m particular objects are always excluded is n−mCr.
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) !.
For example is 20 persons are circularly arranged, the number of arrangements is 19 !.
However, in the case of circular permutations wherein clockwise and anticlockwise orders need not be differentiated – as in the case of differently coloured beads or different flowers made into a garland, the number of permutations is where the number of beads or flowers is taken as n. In details the concept is explained as follows:
4.1 ARRANGEMENTS AROUND A CIRCULAR TABLE
Consider five persons A, B, C, D, E be seated on the circumference of a circular table in order which has no head now, shifting A, B, C, D, E one position in anticlockwise direction we will get arrangements as shown in following figure:
We observe that arrangements in all figures are different.
Thus, the number of circular permutations of n different things taken all at a time is (n − 1)!, if clockwise and anticlockwise orders are taken as different.
Question: 20 persons were invited to a party. In how many ways can they and the host be seated at a circular table? In how many of these ways will two particular persons be seated on either side of the host?
Solution: 1st part: Total persons on the circular table = 20 guest + 1 host = 21
they can be seated in (21 − 1)! = 20! ways.
2nd
part: After
fixing the places of three persons (1 host + 2 persons). Treating
Hence, the number of ways of seating 21 persons on the circular table such that two particular persons be seated on either side of the host = 18! × 2! = 2 × 18!
|
|
4.2 ARRANGEMENTS OF BEADS OR FLOWERS (ALL DIFFERENT) AROUND A CIRCULAR NECKLACE OR GARLAND
Consider five beads A, B, C, D, E in a necklace or five flowers A, B, C, D, E in a garland etc. If the necklace or garland on the left is turned over we obtain the arrangement on the right, i.e., anticlockwise and clockwise order of arrangement is not different we will get arrangements as follows:
we see that arrangements in above figures are not different.
Then the number of circular permutations of n different things taken all at a time is !, if clockwise and anticlockwise orders are taken as not different.
Question: Consider 21 different pearls on a necklace. How many ways can the pearls be placed in on this necklace such that 3 specific pearls always remain together?
Solution: After fixing the places of three pearls. Treating 3 specific pearls = 1 units, so we have now 18 pearls + 1 unit = 19 and the number of arrangement will be (19 − 1)! = 18! also, the number of ways of 3 pearls can be arranged between themselves is 3! = 6. Since, there is no distinction between the clockwise and anticlockwise arrangements. So, the required number of arrangements = 18! . 6 = 3 (18 !).
4.3 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 = .
Question: In how many ways can 24 persons be seated round a table, if there are 13 seats?
Solution: In case of circular table the clockwise and anticlockwise order are 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 =
Question: How many necklace of 12 beads each can be made from 18 beads of various colours?
Solution: In the case of necklace there is not distinction between the clockwise and anticlockwise arrangements, then the required number of circular permutations
=
=
Question: In how many ways 10 boys and 5 girls can sit around a circular table so that no two girls sit together.
Solution: 10 boys can be seated in a circle in 9! ways. There are 10 spaces in between the boys, which can be occupied by 5 girls in 10P5 ways. Hence total numbers of ways are 9! 10P5.
Question: If n distinct objects are arranged in a circle, show that the number of ways of selecting three of these n things so that no two of them is next to each other is .
Solution: Let the n things be
The first choice may be one of these n things; and, this is done in nC1 ways.
Suppose x1 is the one chosen; the next two may be chosen – excluding x1 and, the two next to x1, namely x2, xn – from the remaining (n – 3) in n−3C2 ways.
Of these n−3C2 there are (n – 4) selections when the second two chosen are next to each other, like
∴ the number of ways of selecting the second two after x1 is chosen, so that the two are not next to each other is
The two objects can be relatively interchanged in 2 ways. Further the order of the choice of the three is not to be considered.
Hence the number of ways of choice of the three is
Question: 2n persons are to be seated n on each side of a long table. r(<n) particular persons desire to sit on one side; and s(<n) other persons desire to sit on the other side. In how many ways can the persons be seated?
Solution: For
the side where r
persons desire to sit, we need (n
– r)
more persons. This (n
– r)
may be chosen from (2n
– r
– s)
in (2n
– r
– s)
ways. Automatically the remaining
(n
– s) person go to the other side where already there are s desirous
of seating. Thus there are (2n
– r
– s)
ways of distributing n
persons for each side providing for the restriction of r
on one side and s
on the other side.
n persons on each side can be permuted in n seats in n ! ways. The number of ways of seating the 2n persons, n on each side, is therefore
.
The number of ways (or combinations) of selection from n distinct objects, taken at least one of them is
Logically it can be explained in two ways, as one can be selected in nC1 ways, two in nC2 ways and so on ……. and by addition principle of counting the total number of ways of doing either of the job is nC1 + nC2 + …..+ nCn
Also, for every object, there are two choices, either selection or non-selection. Hence total choices are 2n. But this also includes the case when none of them is selected. Therefore the number of selections, when atleast one is selected = 2n − 1.
Question: Find the number of ways in which we can put n distinct objects into two identical boxes so that no box remains empty.
Solution: Let us first label the boxes 1 and 2. We can select at least one or at most (n−1) balls for box 1 in
nC1 + nC2 + ……… nCn−1 ways
= nC0 + nC1 + ……… nCn − nC0 − nCn
= 2n − 2 = 2(2n−1 − 1) ways.
In this way box 2 is not empty. But since the boxes are identical the number of ways that no box remains empty is
Alternative solutions:
Let us first label the boxes 1 and 2. There are then to choices for each of the n objects; we can put it in the first box or in the second box. Therefore the number of choices for n distinct objects is .
Two of these choices correspond to either the first or the second box being empty. Thus there are 2n − 2 ways in which neither box is empty. If we now remove the labels from the boxes so that they become identical, this number must be divided by 2, yielding the answer 1/2 (2n − 2) = 2n−1 − 1.
Question: Given five different green dyes, four different blue dyes and three different red dyes, how many combination of dyes can be chosen taking at least one green, one blue dye?
Solution: Any one dye of a particular colour can be either chosen or not; and, thus there are 2 ways in which each one may be dealt with.
Number of ways of selection so that at least one green dye is included = 25 − 1 = 31
(1 is subtracted to correspond to the case when none of the green dyes is chosen.)
A similar argument may be advanced in respect of other two colours also.
Number of combinations = (25 − 1) (24 − 1) (23).
= 31 × 15 × 8 = 3720
6.2 SELECTION FROM IDENTICAL OBJECTS
1. The number of selections of r (r ≤ n) objects out of n identical objects is 1.
2. The number of ways of selections of at least one object out of n identical object is n.
3. The number of ways of selections of at least one out of a1 + a2 ……. + an objects, where a1 are alike of one kind, a2 are alike of second kind, and so on ……..an are alike of nth kind, is
(a1 + 1) (a2 + 1) …….(an + 1) − 1.
4. The number of ways of selections of atleast one out of a1 + a2 + a3 + ……+ an + k objects, where a1 are alike of one kind, ……….an are alike of nth kind and k are distinct is
.
Question: Find the number of combinations that can be formed with 5 oranges, 4 mangoes and 3 bananas when it is essential to take
(i) at least one fruit
(ii) one fruit of each kind.
Solution: Here 5 oranges are alike of one kind, 4 mangoes are alike of second kind and 3 bananas are alike of third kind
(i) The required number of combinations (when at least one fruit)
= (5 + 1) (4 + 1) (3 + 1) 20 − 1
= 120 − 1 = 119
(ii) The required number of combinations (when one fruit of each kind)
= 5C1 × 4C1 × 3C1 = 5 × 4 × 3 = 60.
7
DIVISORS OF A GIVEN NATURAL NUMBER
Let n ∈ N and n = , where p1, p2, p3, ….. pk are different prime numbers and α1, α2, α3, …. , αk are natural numbers then:
∙ the total number of divisors of N including 1 and n is
= (α1 + 1) (α2 + 1) (α3 + 1) …. (αk + 1)
∙ the total number of divisors of n excluding 1 and n is
= (α1 + 1) (α2 + 1) (α3 + 1) …. (αk + 1) − 2
∙ the total number of divisors of n excluding exactly one out of 1 or n is
= (α1 + 1) (α2 + 1) (α3 + 1) …. (αk + 1) − 1
∙ the sum of these divisors is
=
(Use sum of G.P. in each bracket)
∙ the number of ways in which n can be resolved as a product of two factors is
(α1 + 1) (α2 + 1) …... (αk + 1), if n is not a perfect square
[(α1 + 1) (α2 + 1) …... (αk + 1) + 1], if n is a perfect square
∙ the number of ways in which is composite number n can be resolved into two factors which are relatively prime (or coprime) to each other is equal to 2k−1 where k is the number of different factors (or different primes) in n.
Question: If n = 10800, then find the
(a) total number of divisors of n
(b) the number of even divisors
(c) the number of divisors of the form 4m + 2
(d) the number of divisors which are multiples of 15
Solution: n = 10800 = 24 × 33 × 52
Any divisor of n will be of the form 2a × 3b × 5c where 0 ≤ a ≤ 4, 0 ≤ b ≤ 3, 0 ≤ c ≤ 2.
For any distinct choices of a, b and c, we get a divisor of n
(a) total number of divisors = (4 + 1) (3 + 1) (2 + 1) = 60
(b) for
a divisor to be even, a
should be at least one. So total number of even divisors
= 4(3
+ 1) (2 + 1) = 48.
(c) 4m + 2 = 2(2m + 1). In any divisor of the form 4m + 2, a should be exactly 1. So number of divisors of the form 4m + 2 = 1 (3 + 1) (2 + 1) = 12.
(d) A divisor of n will be a multiple of 15 if b is at least one and c is at least one. So number of such divisors = (4+ 1) × 3 × 2 = 30.
Question: Find the number of divisors of 428652000 excluding the number and unity. Find also the sum of the divisors.
428652000 = 25 . 37 . 53 . 72
Solution: Any divisor of the given number has to be a combination of the 2’s (five); 3’s (seven); 5’s (three) and 7’s (two).
There are 5 + 1 = 6 ways of selecting none or one or two etc., or all the 2’s. Similar argument repeats for the other numbers.
The number of divisors = 6 × 8 × 4 × 3 = 576.
The includes 1 and the given number also.
Excluding these two, the number of divisors = 574
With regard to the sum of the divisors
Any divisor is of the form where 0 p 5; 0 q 7; 0 s 3 and 0 t 2
Thus the sum of the divisors is
