72. Permutations and Combinations Solutions Part 6#
L.H.S. \(= 2.6.10.\ldots(4n - 6)(4n - 2)\)
\(= 2^n(1.3.5.\ldots.(2n - 3)(2n - 1))\)
\(= \frac{2^n(1.2.3.4.5.\ldots(2n - 3)(2n - 2)(2n - 1)2n)}{2.4.6.\ldots.2n}\)
\(= \frac{2^n(1.2.3.4.5.\ldots(2n - 3)(2n - 2)(2n - 1)2n)}{2^n(1.2.3.\ldots.n)}\)
\(= \frac{2n!}{n!} =\) R.H.S.
L.H.S. \(= {}^{47}C_4 + \sum_{i=0}^3{}^{50- i}C_3 + \sum_{j=1}^5{}^{56 - j}C_{53 - j}\)
\(= {}^{47}C_4 + {}^{47}C_3 + \sum_{i=0}^2{}^{50 - i}C_3 + \sum_{j=1}^5{}^{56 - j}C_{53 - j}\)
[ We know that \({}^nC_r + {}^nC_{r - 1} = {}^{n + 1}C_r\) ]
\(= {}^{48}C_4 + \sum_{i=0}^2{}^{50- i}C_3 + \sum_{j=1}^5{}^{56 - j}C_{53 - j}\)
\(= {}^{48}C_4 + {}^{48}C_3 + \sum_{i=0}^1{}^{50 - i}C_3 + \sum_{j=1}^5{}^{56 - j}C_{53 - j}\)
\(= {}^{49}C_4 + \sum_{i=0}^1{}^{50- i}C_3 + \sum_{j=1}^5{}^{56 - j}C_{53 - j}\)
Following similarly we obtain,
\(= {}^{51}C_4 + \sum_{j=1}^5{}^{56 - j}C_{53 - j}\)
[ We know that \({}^nC_r = {}^nC_{n - r}\) ]
Thus, we can rewrite the previous expression as
\(= {}^{51}C_4 + \sum_{j=1}^5{}^{56 - j}C_3\)
Again, we follow as previously to obtain
\(= {}^{57}C_4\)
L.H.S. \(= {}^nC_k + \sum_{j=0}^m{}^{n+j}C_{k - 1}\)
[ We know that \({}^nC_r + {}^nC_{r - 1} = {}^{n + 1}C_r\) ]
Rewriting given expression,
\(= {}^nC_k + {}^nC_{k - 1} + \sum_{j=1}^m{}^{n+j}C_{k - 1}\)
\(= {}^{n + 1}C_k + \sum_{j=1}^m{}^{n+j}C_{k - 1}\)
Repeating,
\(= {}^{n + 1}C_k + {}^{n + 1}C_{k - 1} + \sum_{j=2}^m{}^{n+j}C_{k - 1}\)
\(= {}^{n + 2}C_k + \sum_{j=2}^m{}^{n+j}C_{k - 1}\)
Repeating this for remaining values of \(j\), we obtain
\(= {}^{n + m + 1}C_k\)
L.H.S. \(= {}^mC_1 +{}^{m+1}C_2 + \ldots +{}^{m + n - 1}C_n\)
\(= {}^mC_0 + {}^mC_1 +{}^{m+1}C_2 + \ldots +{}^{m + n - 1}C_n - {}^mC_0\)
[ We know that \({}^nC_r + {}^nC_{r - 1} = {}^{n + 1}C_r\) and \({}^nC_0 =1\) ]
Applying the above formula, we get
\(= {}^{m+1}C_1 + {}^{m+1}C_2 + \ldots +{}^{m + n - 1}C_n - 1\)
\(= {}^{m+2}C_2 + {}^{m+2}C_3 + \ldots +{}^{m + n - 1}C_n - 1\)
Repeating this we obain,
\(= {}^{m + n}C_n - 1\)
We obtain the same value by computing R.H.S. in similar manner which turns out to be,
\(= {}^{m + n}C_m - 1\)
\(\because {}^nC_r = {}^nC_{n - r}\)
L.H.S. = R.H.S.
For a number to be divisible by \(25\) last two digits should be one of \(00, 25, 50, 75\).
Since we have only one \(0\), last two digits cannot be \(00\).
Case I: When last two digits are \(25\)
No. of ways to fill ten thousand’s place \(= 5\) because we cannot use \(0\)
No. of ways to fill thousand’s place \(= 5\)
No. of ways to fill hundred’s place \(= 4\)
\(\therefore\) Total no. of ways \(= 100\)
Case II: When last two digits are \(75\)
Like Case I total no. of such numbers \(= 100\)
Case III: When last two digits are \(50\)
No. of ways to fill ten thousand’s place \(= 6\)
No. of ways to fill thousand’s place \(= 5\)
No. of ways to fill hundred’s place \(= 4\)
Total no. of such numbers \(= 120\)
\(\therefore\) Desired answer is \(320\)
For a number to be divisible by \(4\) last two digits should be \(12, 24, 32, 52\)
No. of ways to fill ten thousand’s place \(= 3\)
No. of ways to fill thousand’s place \(= 2\)
No. of ways to fill hundred’s place \(= 1\)
\(\therefore\) Desired answer \(= 4*3*2 = 24\)
For a number to be divisible by \(3\) sum of digits should be divisible by \(3\). The combination of such digits are \(123, 234, 345, 135, 1245\)
Considering \(123\) with \(0\)
No. of ways to fill thousand’s place \(= 3\)
No. of ways to fill hundred’s place \(= 3\)
No. of ways to fill ten’s place \(= 2\)
\(\therefore\) total no. of permutations \(= 18\)
Total no. of numbers including \(0 = 4*18 = 72\)
Total no. of permutation of \(1245 = 4! = 24\)
Total no. of numbers divisible by \(6 = 24 + 72 = 96\)
For these numbers to be divisible by \(6\) these should be even.
Case I: When out three digit no. has two odd digits
If \(0\) is at unit’s place, total no. of such numbers \(= 3 * 2\)
If \(0\) is not at unit’s place, total no. of such numbers \(= 2 * 2\)
There are three such numbers(with two odd digits), therefore total no. of numbers \(= 3 * (3 * 2 + 2 *2) = 30\)
Case II: When there are two even numbers in our combination of three digit numbers
If \(0\) is at unit’s place, total no. of such numbers \(= 3 * 2\)
If \(0\) is not at unit’s place, total no. of such numbers \(= 2 * 2\)
There are one such numbers(with one odd digits), therefore total no. of numbers \(= 1 * (3 * 2 + 2 *2) = 10\)
Case III: When the no. is permutation of \(1245\)
Half of these will have even no. at unit’s place i.e. \(12\)
Therefore, total no. of numbers divisible by \(6 = 40 + 12 = 52\)
If the two \(3\) were different then,
Unit’s place can be filled in \(3\) ways.
Thousand’s place can be filled in \(3\) ways.
Hundred’s place can be filled in \(2\) ways.
Therefore, total no. of \(4\) digit numbers \(= 3 * 3 *2 = 18\)
However, the two \(3\) are same, therefore total no. of numbers \(= \frac{18}{2} = 9\)
Out of \(9\) numbers at unit’s, ten’s and hundred’s place there will be \(3\) will come four times, \(1\) will come twice and \(0\) will come thrice.
On thousand’s place \(3\) will come six times and \(1\) will come three times.
Sum of digits at unit’s place \(= 4*3 + 2*1 = 14\)
Sum of digits at ten’s place \(= 4*3 + 2*1 = 14\)
Sum of digits at hundred’s place \(= 4*3 + 2*1 = 14\)
Sum of digits at thousand’s place \(= 6*3 + 3*1 = 21\)
Thus, sum of digits \(= 22554\)
Total no. of ways of taking \(1\) thing at a time \(= n\)
Total no. of ways of taking \(2\) thing at a time \(= n^2\)
Total no. of ways of taking \(3\) thing at a time \(= n^3\)
\(\ldots\)
Total no. of ways of taking \(r\) thing at a time \(= n^r\)
\(\therefore\) total no. of ways \(= n + n^2 + n^3 + \ldots + n^r\)
\(= \frac{n(n^r - 1)}{n - 1}\)
Smallest \(7\) digit number \(= 1000000\)
largest \(7\) digit number \(= 9999999\)
\(\therefore\) Total no. of \(7\) digit numbers \(= 9000000\)
Half of these will have sum of digits as even, which is \(4500000\)
Ways of choosing \(k\) numbers out of \(r(r\le n) = r^k\)
However, \((r - 1)^k\) ways will not have \(r\) as maximum.
\(\therefore\) Desired answer \(= r^k - (r - 1)^k\)
Ways of filling most significant position \(= 9\)
Ways of filling next signifcant position \(= 8 \because\) we cannot repeat digits.
This is true for next \(n - 1\) positions. Thus, total no. of numbers formed \(= 9.8^{n - 1}\)
No. of ways of filling first position \(= 26 \because\) it has to be an alphabet.
No. of ways of filling next five positions \(= 36\)
However, the identifier can be of one to six characters. Thus, total no. of identifiers \(= 26 + 26.36 + 26.36^2 + \ldots + 26.36^4\)
\(= 26.\frac{36^5 - 1}{35}\)
First we compute total no. of \(5\) digit numbers.
Ways to fill ten thousand’s position \(= 9\)
No. of ways to fill rest of positions \(= 10\)
\(\therefore\) Total no. of \(5\) digit numbers \(= 9\times 10^4\)
However, these will include numbers without repetitions.
No. of numbers with no repetition \(= 9\times 9\times 8 \times 7\times 6\)
\(\therefore\) Desired answer \(= 90000 - 27216 = 62784\)
Total no. of numbers between \(2\times 10^4\) and \(6\times 10^4\) is \(4\times 10^4\)
Half of these will have sum of digits as even, which is \(20000\)
Let us solve these two parts:
Treating \(A_1\) and \(A_2\) as one entity. Total no. of ways of arranging them \(9!\)
However, \(A_1\) and \(A_2\) can be arranged in \(2!\) ways among themselves.
Thus, total no. of ways in which \(A_1\) and \(A_2\) are together \(= 9!2!\)
Total no. of permutations \(= 10!\)
Out of these half the time \(A_1\) will be above \(A_2\).
Thus, desired answer \(= \frac{10!}{2}\)
Since no man should sit between two women we have to sit all the men together.
Treating all men as one entity, total no. of ways to sit them \(= (n + 1)!\)
However, \(m\) men can be seated in \(m!\) ways among themselves.
Thus, total no. of desired arrangements \(= (n + 1)!m!\)
No. of Is is \(2\), no. of Ts is \(2\), no. of Es is \(3\). Rest of the characters come once each.
Treating all vowels as one character total no. of characters \(= 7\)
No. of ways to arrange them \(= \frac{7!}{2!}\)
Six vowels can be arranged in \(\frac{6!}{2!3!}\) no. of ways among themselves.
Thus, total no. of desired words \(= \frac{7!6!}{2!2!3!} = 151200\)
Total no. of arrangements \(= \frac{18!}{5!6!7!}\)
Treating all balls of same color as one ball so that they stay together, total no. of arrangements \(= 3!\)
Thus, desired answer \(= \frac{18!}{5!6!7!} - 3!\)
No. of ways of seating men together \(= 7!\)
No. of ways of seating women together \(= 3!\)
No. of ways of seating two men together \(= 2!\)
No. of arragements when three ladies and two men are together \(= 7!3!2!\)
Treating all ladies as one we have \(8\) people and ladies can be seated in \(3!\) ways among themselves.
No. of arragements with ladies together and no codition on sitting men \(= 8!3!\)
\(\therefore\) Desired no. of seating arragements \(= 8!3! - 7!3!2!\)
Total no. of permuatations \(= n!\)
Treating \(p\) things as one we have \(n - p + 1\) things.
No. of arragements when \(p\) things are together \((n - p + 1)!\)
However, \(p\) things can be arranged in \(p!\) ways among themselves.
\(\therefore\) No. of ways in which \(p\) things are never together \(= n! - (n - p + 1)!p!\)
Let us mark ten positions in a line XOXOXOXOXOX where Xs mark position of ‘-’ and Os mark positions of ‘+’. There are total of \(7\) positions to be filled by \(4\) ‘-’ signs.
No. of ways \(= {}^7C_4 = 35\)
let Gentelman be G and lady be L. They can be seated as,
GLGGLGLG
On both of these Gentelman can now exchange places in \(5!\) ways
Ladies can exchange places in \(3!\) ways
So total number of ways is \(5!*3! = 720\)
There are three S, two C, and one U and E each.
Treating two Cs as one character.
SXSXSXS can be a way where S is position of S and X is position of other characters.
No. of ways to fill S \(= {}^4C_3\)
However, rest of \(3\) characters can be arranged in \(3!\) ways. Thus, total no. of ways \(= 24\)
The total number of permutation of letters (T) \(= \frac{7!}{2!3!}\)
With two C together (A) \(= \frac{6!}{2!}\)
With three S together (B) \(= \frac{6!}{2!} - \frac{5!}{2!}\)
With both S and C together (C) \(= 5! - 4!\)
\(\therefore\) Desired answer \(= T - A - B + C = 96\)
No. of words beginning with E \(= 5!\)
No. of words beginning with H \(= 5!\)
No. of words beginning with ME \(= 4!\)
No. of words beginning with MH \(= 4!\)
No. of words begining with MOE \(= 3!\)
No. of words begining with MOH \(= 3!\)
No. of words begining with MOR \(= 3!\)
No. of words beginning with MOTE \(= 2!\)
There are two words which beging with MOTH and MOTHER is first of them.
\(\therefore\) Rank of MOTHER \(= 309\)
There are \(7\) intermediate destinations and Delhi as final destination. Thus, there are \(8\) places where passengers can go to. Let the intermediate stations be \(S_1, S_2, \ldots, S_7\)
People starting at Calcutta will have \(8\) destinations.
People starting at \(S_1\) will have \(7\) destinations.
People starting at \(S_2\) will have \(6\) destinations.
Proceeding similarly, total no. of tickets possible \(= 8 + 7 + \ldots + 1\)
\(= \frac{8*9}{2} = 36\)
Thus, total no. of sets possible \(= {}^{36}C_5\)
This problem is similar to previous one. Answer is \({}^{55}C_6\)
A day can be either clear or overcast. Thus, we have two possibilities. Total no. of possibilties for \(7\) days \(= 2^7 = 128\)
No. of ways of selecting \(1\) book \(= {}^{2n + 1}C_1\)
No. of ways of selecting \(2\) book \(= {}^{2n + 1}C_2\)
\(\ldots\)
No. of ways of selecting \(n\) book \(= {}^{2n + 1}C_n\)
\(\therefore {}^{2n + 1}C_1 + {}^{2n + 1}C_2 + \ldots + {}^{2n + 1}C_n = 63 = S\) (say)
We know that, \({}^{2n + 1}C_0 + {}^{2n + 1}C_1 + \ldots + {}^{2n + 1}C_n + \ldots + {}^{2n + 1}C_{2n + 1} = 2^{2n + 1}\)
We also know that, \({}^nC_r = {}^nC_{n - r}\)
\(1 + 2S + 1 = 2^{2n + 1}\)
\(1 + S = 2^{2n} = 64 \Rightarrow n = 3\)
\(k\) flowers can be chosen from first bag in \({}^kC_k\) ways.
\(k\) flowers can be chosen from second bag in \({}^{k + 1}C_k\) ways.
\(k\) flowers can be chosen from third bag in \({}^{k + 2}C_k\) ways.
\(\ldots\)
\(k\) flowers can be chosen from mth bag in \({}^{k + m - 1}C_k\) ways.
\(therefore\) Desired answer \(S = {}^kC_k + {}^{k + 1}C_k + {}^{k + 2}C_k + \ldots + {}^{k + m - 1}C_k\)
\(S = 1 + (k + 1) + \frac{(k + 1)(k + 2)}{2!} + \ldots + \frac{(k + m - 1)!}{(m - 1)!(k!)}\)
\(S = {}^{k + 1}C_0 + {}^{k + 1}C_1 + {}^{k + 2}C_2 + \ldots + {}^{k + m - 1}C_{m - 1}\)
[ The above could also be rewritten using \({}^nC_r = {}^nC_{n - r}\) and \({}^nC_0 = {}^mC_0 = 1\) ]
Now we know that \({}^nC_r + {}^nC_{r - 1} = {}^{n + 1}C_r\)
Applying the above on the series we get, \(S = {}^{k + m}c_{m - 1} = {}^{k + m}c_{k + 1}\)
Total no. of ways of choosing \(11\) persons out of \(50 = {}^{50}C_{11}\)
Treating three persons as one, no. of ways of choosing \(11\) when all three stay together in committee \(= {}^{47}C_8\)
Thus, desired answer \(= {}^{50}C_{11} - {}^{47}C_8\)
Let \(S_1, S_2, S_3\) be the three intermediate stations where the train stops.
\(a, S_1, b, S_2, c, S_3, d\)
Let \(a, b, c, d\) be the number of stations between starting station and \(S_1\), \(S_1\) and \(S_2\), \(S_2\) and \(S_3\) and \(S_3\) and final destination.
Thus, \(a + b + c + d = m - 3\) where \(a \geq 0, b\geq 1, c\geq 1, d\geq 0\)
Let \(x = a, y = b - 1, z = c - 1, w = d\)
\(x + y + z + w = a + b + c + d - 2 = m - 5\)
Desired answer is non-negative solution of above equation \(= {}^{m - 2}C_3\)
Let us solve these one by one:
\(2\) elements have to be part of both. No. of ways of choosing \(2\) out of \(n = {}^nC_2\)
Rest of elements should be either part of \(P\) or \(Q\) or should not be there at all. Thus, there are three possibilities for each number. Total possibilites for \(n - 2\) numbers \(= 3^{n - 2}\)
Thus, desired answer \(= {}^nC_23^{n - 2}\)
There are three ways this can be satisfied for an element. The element can be member or \(P\) or \(Q\) or not a member of either. Thus, there are three possibilities for each element. Thus, total no. of possibilities for \(n\) elements is \(3^n\)
Let us solve these one by one.
Let \(A = {a_1, a_1, \ldots, a_n}\)
For element \(a_1\) and one subset \(P_1\) there are two posiibilities.
Either \(a_1\in P_1\) or \(a_1\notin P_1\)
\(\therefore\) Total no. of ways for one element \(a_1\) of \(A\) and one subset \(P_1 = 2\)
No. of ways in which \(a_1\) does not belong to \(P_1 = 1\)
\(\therefore\) Total no. of ways for \(a_1\) and \(m\) subsets \(= 2^m\)
Total no. of ways \(a_1\) belongs to all of the \(m\) subsets \(=1^m\)
Total no. of ways \(a_1\) belongs to none of the \(m\) subsets \(=1^m\)
\(\therefore a_1 \in (P_1\cap P-2\cap\ldots P_m) = 1^m\)
\(\therefore a_1\notin (P_1\cap P-2\cap\ldots\cap P_m) = 2^m - 1^m\)
\(\therefore a_1\in (P_1\cup P-2\cup\ldots\cup P_m) = 2^m - 1^m\)
Now, this has to be applied for \(n - 1\) elements. Thus, no. of ways in which \(n - 1\) elements belong to \(P_1\cup P-2\cup\ldots\cup P_m\) is \((2^m - 1^m){n - 1}\)
The element which is not found can be chosen in \(n\) ways. Thus, desired answer \(=n(2^m - 1^m)^{n - 1}\)
We have already computed that \(\therefore a_1\notin (P_1\cap P-2\cap\ldots\cap P_m) = 2^m - 1^m\)
Thus, for \(n\) elements to not belong to the intersection of \(m\) subsets \(= (2^m - 1^m)^n\)
No. of possible choices are \((3, 1, 1), (1, 3, 1), (1, 1, 3), (2, 2, 1), (2, 1, 2), (1, 2, 2)\) where each number represents no. of choices from a paper.
For \((3, 1, 1)\) no. of choices \(= {}^5C_3\times {}^5C_1\times {}^5C_1\)
\(= 250\)
For three such sets no. of choices \(= 750\)
For \((2, 2, 1)\) no. of choices \(= {}^5C_2\times {}^5C_2\times {}^5C_1\)
\(= 500\)
For three such sets no. of choices \(= 1500\)
\(\therefore\) Total no. of ways in which questions can be answered \(= 2250\)
The product will be divisible by \(3\) if one of the numbers is divisible by \(3\).
Case I: When one of the numbers choses is divisible by \(3\)
Total no. of ways \(= 33*67\)
Case I: When both of the numbers choses is divisible by \(3\)
Total no. of ways \(= {}^{33}C_2\)
Thus, desired answer \(= 33*(16 + 67) = 33*83 = 2739\)
No. of ways of selecting \(2\) husbands \(= {}^5C_2 = 10\)
After selecting two husbands we have only \(3\) wives to choose from. Thus, no. of ways of choosing wives \(= {}^3C_2 = 3\)
However, wives can be part of either side thus total no. of wasy \(= 10\times 3\times 2 = 60\)
The line which is parallel to \(n\) concurrent line has to be part of all triangles. Also, the line which is parallel to it will be part of no triangle. Thus, total no. of possible triangles \(= {}^{n - 1}C_2\)
Total no. of points of intersection \({}^nC_2 = m\) (say)
If these points are not collinear then total no. of triangles formed \(= {}^mC_3\)
One line will have \(n - 1\) collinear points. These lines will not form any triangle among themselves. Thus, total no. of such triangles \({}^{n - 1}C_3\)
However, there are \(n\) such lines. Thus total no. of triangles not formed by collinear points of these lines \(= n{}^{n - 1}C_3\)
Thus, answer is \(= {}^mC_3 - n{}^{n - 1}C_3\)
There can be \(3, 4\) or \(5\) bowlers in the team.
Thus total no. of selecting team \(= {}^5C_3*{}^{10}C_8 + {}^5C_4*{}^{10}C_7 + {}^5C_5*{}^{10}C_6\)
From each bag \(1, 2, 3\) up to \(m\) balls can be selected.
No. of ways of selecting \(1\) ball from each bag \(= {}^mC_1*{}^mC_1\)
No. of ways of selecting \(2\) balls from each bag \(= {}^mC_2*{}^mC_2\)
\(\ldots\)
No. of ways of selecting \(m\) balls from each bag \(= {}^mC_m*{}^mC_m\)
\(\therefore\) answer is \(= ({}^mC_1)^2 + ({}^mC_2)^2 + \ldots + ({}^mC_m)^2\)
\(= {}^{2m}C_m - 1\) \([\because({}^mC_0)^2 + ({}^mC_1)^2 + ({}^mC_2)^2 + \ldots + ({}^mC_m)^2 = {}^{2m}C_m]\)
Let us solve this part by part.
For women to be in majority there can be \(7, 8, 9\) women.
Thus no. of possible committees \(= {}^9C_7*{}^8C_5 + {}^9C_8*{}^8C_4 + {}^9C_9*{}^8C_3\)
This is similar to part one and has been left as an exercise.
Let the distance between lines be \(1\) unit. For squares with side \(1\) unit: Along the \(m\) horizontal lines \(m - 1\) squares can be formed and along the \(n\) vertical lines \(n - 1\) sqaures can be formed. Thus, total no. of such squares \(= (m - 1)(n - 1)\)
For squares with side \(2\) unit: Along the \(m\) horizontal lines \(m - 2\) squares can be formed and along the \(n\) vertical lines \(n - 2\) sqaures can be formed. Thus, total no. of such squares \(= (m - 2)(n - 2)\)
Since \(m < n,\) total no. of squares \(= \sum_{i = 1}^{m - 1}(m - i)(n - i)\)
\(= \sum_{i = 1}^{m - 1}(mn - (m + n)i - i^2)\)
This gives us our desired answer.
The set of lines given are parallel. The two sets are perpendicular to each other as we know from co-ordinate geometry. Thus, following from previous exercise we arrive at the same answer.
Total no. of ways of dividing \(3n\) elements in three groups which contain equal no. of elements \(= \frac{2n!}{6(n!)^3}\)
No. of ways in which \(50\) different things can be divided in \(5\) sets three of them having \(12\) things and two of them having \(7\) things each \(= \frac{50!}{(12!)^3(7!)^23!2!}\)
This problem is same as previous.
\(\frac{n!}{a!b!\ldots k!}\) is no. of ways of dividing \(n\) different things in groups of \(a, b, \ldots, k\) things.
\(\frac{(ab)!}{a!(b!)^a}\) is no. of ways of distributing \(ab\) different things in \(a\) groups of \(b\) things each. Thus, it is an integer.
\(\frac{(n^2)!}{(n!)^{n + 1}}\) can be rewritten as \(\frac{(n^2)!}{n!(n!)^{n}}\) which is distributing \(n^2\) different things into \(n\) groups each containing \(n\) things.