GATE Engineering Mathematics - Combinatorics
Exam Duration: 45 Mins Total Questions : 10
How many ways are there to arrange the nine letters in the word ALLAHABAD?
- (a)
7500
- (b)
7560
- (c)
4000
- (d)
2000
Since, the word ALLAHABAD contains 4 A's and 2 L's therefore, there are
= \(\frac { 9! }{ 4!2! } =7560\quad ways\)
The number of diagonals which can be drawn by joining the angular points of a heptagon is
- (a)
14
- (b)
7
- (c)
10
- (d)
12
A heptagon has seven angular points (vertices) sides.
The join of two angular points is either a side or a diagonal.
The number of line joining the angular points
\(^{ 7 }{ C }_{ 2 }=\frac { 7! }{ 2!5! } \) = 21
At certain college the housing office has decided to appoint, for each floor, one male and one female residental advisor. The pairs of advisors can be selected for a seven story building from 12 male and 15 female candidates are
- (a)
40000
- (b)
5096520
- (c)
568400
- (d)
70000
From 12 male candidates, 7 candidates can be selected in 12C7 ways. From 15 females candidates, 7 candidates can be selected in 15C7 ways. Therefore, the total number of possible pairs of advisors of the required type is
\(^{ 7 }{ C }_{ 2 }\times ^{ 15 }{ C }_{ 7 }=\frac { 12! }{ 7!5! } \times \frac { 15! }{ 7!8! } \\ \)
= 792 \(\times \) 6435
= 5096520
Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences B and C are there such that (i) each is sorted in ascending order (ii) B has 5 and c has 3 elements and (iii) the result of merging B ans C given A?
- (a)
2
- (b)
30
- (c)
56
- (d)
256
This corresponding to an ordered partition of 8 elements into two groups, the first with 5 elements and seconds with 3 elements. The number of ways of doing this is
P (8 , 5, 3) = \(\frac { 8! }{ 5!3! } \) = 56
A person deposiits Rs 300 in a saving account of SBI at an interest rate of 5% per annum compounded annually. The obatin amount in his account at the end of r yeras is
- (a)
300(1.05)r
- (b)
200
- (c)
100(1.02)r+1
- (d)
50\(\times \) (1.00)r
The amount after one year
a1 = 300 \(\left( 1+\frac { 5 }{ 100 } \right) ^{ 1 }\) = Rs 300 (1.05)1
The amount after two years
a2 = 300 \(\left( 1+\frac { 5 }{ 100 } \right) ^{ 2 }\) = Rs 300 (1.05)2
Similarly, the amount after r years
ar = 300 \(\left( 1+\frac { 5 }{ 100 } \right) ^{ r }\) = Rs 300 (1.05)r
Thus, the required numeric function
ar = 300 (1.05)r
The generating function for thr sequence 2, 2, 2, 2, 2, 2 is
- (a)
\(\frac { { z }^{ 2 }+1 }{ (z-1) } \)
- (b)
\(\frac { 18(z-1) }{ { z }^{ 2 }+1 } \)
- (c)
\(\frac { 2({ z }^{ 5 }-1) }{ z-1 } \)
- (d)
None of these
ar = 2, 2, 2, 2, 2
\(A(z)=\frac { 2({ z }^{ 5 }-1) }{ z-1 } \)
The generating function for the sequence 0, 1, 2, 4, 8, ...... is
- (a)
\(\frac { 2z }{ 1+{ z }^{ 2 } } \)
- (b)
\(\frac {1+3z }{ 1+{ 8}{ z } } \)
- (c)
\(\frac { { Z }^{ 2 }+1 }{ { Z }^{ 2 }-1 } \)
- (d)
\(\frac {z }{ 1+{ 2}{ z } } \)
A(z) = 0 + z - 2x2 + 4z3 - 8z4+......
= z(1 - 2z + 4z3 - 8z4+......) = z(1 + 2z)-1
= \(\frac { z }{ 1+2z } |2z|<1\)
The solution of the recurrence relation
ar + 6ar-1 + 12ar-2 - 8ar-3 = 0 is
- (a)
ar = (A1r + A2r + 2A3 r3)(2)r
- (b)
ar = (A1 + A2r2 + A3r3)(3)r
- (c)
ar = (A1 + A2r + A3r2)(-2)r
- (d)
None of these
The characteristic equation is
a3 - 5a2 + 8a - 4 = 0
a = -2, -2, -2
The solution equation is
ar = (A1 + A2 + A3r2)(-2)r
The sum of the series
12 + 22 + 32 + ...+r2 is
- (a)
\(\frac { r(r+1)(2r+1) }{ 6 } \)
- (b)
\(\frac { r(2r+1)(3r+1) }{ 6 } \)
- (c)
\(\frac { 2{ r }^{ 2 }9r+1)(2r+1) }{ 8 } \)
- (d)
None of these
\(\frac { 1 }{ 1-z } \) = 1 + z + z2 + ...+ zr + ... ......(i)
Differentiating w,r,t,z we get
\(\frac { 1 }{ (1-z)^{ 2 } } \) = 1 + 2z + 3z2 + 4z3 + ....+ rzr-1 + ... ......(ii)
Multiplying both sides of Eq. (ii) by z
\(\frac { z }{ (1-z)^{ 2 } } \) = z + 2z2 + 3z3 + 4z4 + .....+ rzr + .... ......(iii)
Differentiating both side of (iii) w,r,t,z we get
\(\frac { 1+z }{ (1-z)^{ 3 } } \) = 0 + 12z + 32z3+.....+r2zr-1+.... ......(iv)
Multiplying by z, we get
\(\frac { z(1+z) }{ (1-z)^{ 3 } } \) = 0 + 12z + 32z3+.....+r2zr
So, ,\(\frac { z(1+z) }{ (1-z)^{ 3 } } \) is the generating function of the numeric function 02, 12, 22.....,r2,.......
It follows that , \(\frac { z(1+z) }{ (1-z)^{ 4 } } \) is the generating function of the numeric function
(02, 02+ 12, 02 + 12 + 22,.......,02 + 12 + 22 +......+ r2,.....)
According to the binominal theroem thecoefficient of zr in \(\frac { 1 }{ (1-z)^{ 4 } } \) is
\(\frac { (-4)(-4-1)(-4-2)...(-4-r+1) }{ r! } \)
\(=\frac { 4.5.6...(r+3) }{ r! } =\frac { (r+1)(r+2)(r+3) }{ 1.2.3 } \)
So, the coefficient of zr in the expression of \(\frac { z(1+z) }{ (1-z) } \)is
\(\frac { r(r+1)(r+2) }{ 1.2.3 } +\frac { (r-1)9r+1) }{ 1.2.3 } =\frac { r(r+1)(2r+1) }{ 6 } \)
So, 12 + 22 + 32 + ......+ r2 = \(\frac { r(r+1)(2r+1) }{ 6 } \)
The solution of the recurrence relation ar = ar-1 + 2ar-2 with a0 = 2,a1 = 7 is
- (a)
ar = (3)r + (1)r
- (b)
2ar = \(\frac { (2{ ) }^{ r } }{ 3 } \)- (1)r
- (c)
ar = 3r+1 - (-1)r
- (d)
ar = 3(2)r - (-1)r
Given, ar - ar-1 -2ar-2 = 0
The characteristic of Eq. (i) is
a2 - a - 2 = 0
a = 2, -1
(ar)h = A1(2)r + A2(-1)r
Is the solution with A1 and A2 as constants.
From the given conditions, we have
a0 = 2 = A1(2)0 + A2(-1)0
a1 = 7 = A1A1(2)1 + A2(-1)1
2 = A1 + A2 .....(ii)
7 = 2A1 - A2 ....(iii)
Solving Eqs. (ii) and (iii), we have
A1 = 3, A2 = -1
The solution to the recurrence relation wih initial condition is
ar = 3(2)r - (-1)r