Combinatorics

Question 1

If the ordinary generating function of a sequence is , then a3 - a0 is equal to ________.

A
15
B
16
C
17
D
18
       Engineering-Mathematics       Combinatorics       GATE 2017 [Set-2]       Video-Explanation
Question 1 Explanation: 
Question 2

Which one of the following is a closed form expression for the generating function of the sequence {an}, where an = 2n+3 for all n = 0, 1, 2, …?

A
3/(1-x)2
B
3x/(1-x)2
C
2-x/(1-x)2
D
3-x/(1-x)2
       Engineering-Mathematics       Combinatorics       GATE 2018       Video-Explanation
Question 2 Explanation: 
Question 3

The number of integers between 1 and 500 (both inclusive) that are divisible by 3 or 5 or 7 is _________.

A
271
B
272
C
273
D
274
       Engineering-Mathematics       Combinatorics       GATE 2017 [Set-1]       Video-Explanation
Question 3 Explanation: 

Let A = number divisible by 3
B = numbers divisible by 5
C = number divisible by 7
We need to find “The number of integers between 1 and 500 that are divisible by 3 or 5 or 7" i.e., |A∪B∪C|
We know,
|A∪B∪C| = |A|+|B|+C-|A∩B|-|A∩C|-|B∩C|+|A∩B|
|A| = number of integers divisible by 3
[500/3 = 166.6 ≈ 166 = 166]
|B| = 100
[500/5 = 100]
|C| = 71
[500/7 = 71.42]
|A∩B| = number of integers divisible by both 3 and 5 we need to compute with LCM (15)
i.e.,⌊500/15⌋ ≈ 33
|A∩B| = 33
|A∩C| = 500/LCM(3,7) 500/21 = 23.8 ≈ 28
|B∩C| = 500/LCM(5,3) = 500/35 = 14.48 ≈ 14
|A∩B∩C| = 500/LCM(3,5,7) = 500/163 = 4.76 ≈ 4
|A∪B∪C| = |A|+|B|+|C|-|A∩B|-|A∩C|-|B∩C|+|A∩B∩C|
= 166+100+71-33-28-14+4
= 271
Question 4

Let an be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for an?

A
an = a(n-1) + 2a(n-2)
B
an = a(n-1) + a(n-2)
C
an = 2a(n-1) + a(n-2)
D
an = 2a(n-1) + 2a(n-2)
       Engineering-Mathematics       Combinatorics       GATE 2016 [Set-1]       Video-Explanation
Question 4 Explanation: 
an = number of n-bit strings, that do not have two consecutive 1’s.
If n=1, we have {0,1}
# Occurrences = 2
If n=2, we have {00,01,10}
# Occurrences = 3
If n=3, we have {000,001,010,100,101}
# Occurrences = 5
It is evident that a3 = a1 + a2
Similarly, an = an-1 + an-2
Question 5

The coefficient of x12 in (x3 + x4 + x5 + x6 + ...)3 is _________.

A
10
B
11
C
12
D
13
       Engineering-Mathematics       Combinatorics       GATE 2016 [Set-1]       Video-Explanation
Question 5 Explanation: 
Co-efficient of x12 in (x3 + x4 + x5 + x6+...)3
⇒ [x3(1 + x + x2 + x3 + ...)]3
= x9(1 + x + x2 + x3 + ...)3
First Reduction:
As x9 is out of the series, we need to find the co-efficient of x3 in (1 + x + x2 + ⋯)3

Here, m=3, k=3, the coefficient

= 5C3 = 5!/2!3! = 10
Question 6

Consider the recurrence relation a1 = 8, an = 6n2 + 2n + an-1. Let a99 = K × 104. The value of K is ___________.

A
198
B
199
C
200
D
201
       Engineering-Mathematics       Combinatorics       GATE 2016 [Set-1]       Video-Explanation
Question 6 Explanation: 
an = 6n2 + 2n + a(n-1)
Replace a(n-1)

⇒ an = 6n2 + 2n + 6(n-1)2 + 2(n-1) + 6(n-2)2 + 2(n-2) + ⋯ a1
Given that a1 = 8, replace it
⇒ an = 6n2 + 2n + 6(n-1)2 + 2(n-1) + 6(n-2)2 + 2(n-2) + ⋯8
= 6n2 + 2n + 6(n-1)2 + 2(n-1) + 6(n-2)2 + 2(n-2) + ⋯ + 6(1)2 + 2(1)

= 6(n2 + (n-1)2 + (n-2)2 + ⋯ + 22 + 12) + 2(n + (n-1) + ⋯1)
Sum of n2 = (n(n+1)(2n+1))/6
Sum of n = (n(n+1))/2
= 6 × (n(n+1)(2n+1))/6 + 2×(n(n+1))/2
= n(n+1)[1+2n+1]
= n(n+1)[2n+2]
= 2n(n+1)2
Given a99 = k×104
a99 = 2(99)(100)2 = 198 × 104
∴k = 198
Question 7

The number of divisors of 2100 is ______.

A
36
B
37
C
38
D
39
       Engineering-Mathematics       Combinatorics       GATE 2015 [Set-2]
Question 7 Explanation: 
Let N = 2100
= 22+3×52×7 (i.e., product of primes)
Then the number of divisions of 2100 is
(2+1)∙(1+1)∙(2+1)∙(1+1) i.e., (3)(2)(3)(2) i.e., 36.
Question 8

The number of 4 digit numbers having their digits in non-decreasing order (from left to right) constructed by using the digits belonging to the set {1, 2, 3} is _____.

A
15
B
16
C
17
D
18
       Engineering-Mathematics       Combinatorics       GATE 2015 [Set-3]
Question 8 Explanation: 
Just try to write all the four digit numbers containing the digits 1, 2 and 3 only, in decreasing order.
1 1 1 1
1 1 1 2
1 1 1 3
1 1 2 2
1 1 2 3
1 1 3 3
1 2 2 2
1 2 2 3
1 2 3 3
1 2 3 3
1 3 3 3
2 2 2 2
2 2 2 3
2 2 3 3
2 3 3 3
3 3 3 3
Hence, total 15 4-digit no. are possible.
Question 9

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)}and the set of all 3-pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10-pennants is ________.

A
89
B
90
C
91
D
92
       Engineering-Mathematics       Combinatorics       GATE 2014 [Set-1]
Question 9 Explanation: 
No twos: 1111111111 ⇒ 1 pennant
Single two: 211111111 ⇒ 9!/8!1! = 9 pennants
Two twos: 22111111 ⇒ 8!/6!2! = 28
Three twos: 2221111 ⇒ 7!/3!4! = 35
Four twos: 222211 ⇒ 6!/4!2! = 15
Five twos: 22222 ⇒ 1
Total = 89 pennants.
Question 10

The number of distinct positive integral factors of 2014 is _________.

A
0.26
B
0.27
C
8
D
0.29
       Engineering-Mathematics       Combinatorics       GATE 2014 [Set-2]
Question 10 Explanation: 
First lets find prime factorization of 2014
= 2' × 19' × 53'
Now number of distinct integral factors of 2014 will be,
(1+1)×(1+1)×(1+1) = 2×2×2 = 8
Question 11

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).

How many distinct paths are there for the robot to reach the point (10,10) starting from the initial position (0,0)?

A
B
220
C
210
D
None of the above
       Engineering-Mathematics       Combinatorics       GATE 2007
Question 11 Explanation: 
Lets name one unit up movement as 'u' and one unit right movement as 'r'.
So now we have 10 u's and 10 r's, i.e.,
uuuuuuuuuurrrrrrrrrr
So, finally the no. of arrangements of above sequences is,
Question 12

Suppose that a robot is placed on the Cartesian plane. At each step it is allowed to move either one unit up or one unit right, i.e., if it is at (i,j) then it can move to either (i+1,j) or (i,j+1).

Suppose that the robot is not allowed to traverse the line segment from (4,4) to (5,4). With this constraint, how many distinct paths are there for the robot to reach (10,10) starting from (0,0)?

A
29
B
219
C
D
       Engineering-Mathematics       Combinatorics       GATE 2007
Question 12 Explanation: 
So to solve this lets find the no. of paths possible if line segment from (4,4) to (5,4) is taken. And then we will subtract it from the total no. of paths possible.
So, no. of paths possible if line segment from (4,4) to (5,4) is taken is,
= paths possible from (0,0) to (4,4) * paths possible from (5,4) to (10,10)
= {uuuurrrr} * {uuuuuurrrrr}

Hence, the final answer is
Question 13

Given a set of elements N = {1, 2, ..., n} and two arbitrary subsets A⊆N and B⊆N, how many of the n! permutations π from N to N satisfy min(π(A)) = min(π(B)), where min(S) is the smallest integer in the set of integers S, and π(S) is the set of integers obtained by applying permutation π to each element of S?

A
(n-|A ∪ B|) |A| |B|
B
(|A|2+|B|2)n2
C
n!(|A∩B|/|A∪B|)
D
       Engineering-Mathematics       Combinatorics       GATE 2006
Question 13 Explanation: 
Given a set of elements N = {1, 2, 3, ...N}
Two arbitrary subsets A⊆N and B⊆N.
Out of n! permutations π from N to N, to satisfy
min(π(A)) = min (π(B))
*) π(S) is the set of integers obtained by applying permutation π to each element of S.
If min(π(A)) =min (π(B)), say y = π(x) is the common minimum.
Since the permutation π is a 1-to-1 mapping of N,
x ∈ A∩B
∴ A∩B cannot be empty.
⇒ y = π(x)
= π(A∩B) is the minimum of π(A∪B) is the minimum of π(A) and π(B) are to be same.
You can think like
*) If the minimum of π(A) and π(B) are same [min π(A)] = min [π(B)]
then min(π(A∩B)) = min(π(A∪B))
∴ Total number is given by n! |A∩B|/|A∪B|
*) Finally
Considering all possible permutations, the fraction of them that meet this condition |π(A∩B)| / |π(A∪B)|
[The probability of single permutation].
Ex: N = {1, 2, 3, 4} A = {1, 3} B = {1, 2, 4}

Since π is one to one mapping
|π(A∩B)| = |A∩B|
∴ π(A) = {1, 2}
π(B) = {1, 4, 3}
π(A∩B) = {1}
π(A∪B) = {1, 2, 3, 4}
4! × 1/4 = 6
Question 14

Let , where |x|<1. What is g(i)?

A
i
B
i+1
C
2i
D
2i
       Engineering-Mathematics       Combinatorics       GATE 2005
Question 14 Explanation: 

Put g(i) = i+1

S = 1 + 2x + 3x2 + 4x3 + .....
Sx = 1x + 2x2 + 3x3 + 4x4 + ......
S - Sx = 1 + x + x2 + x3 + .....
[Sum of infinite series in GP with ratio < 1 is a/1-r]
S - Sx = 1/(1-x)
S(1-x) = 1/(1-x)
S = 1/(1-x)2
Question 15

Mala has a colouring book in which each English letter is drawn two times. She wants to paint each of these 52 prints with one of k colours, such that the colour-pairs used to colour any two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?

A
9
B
8
C
7
D
6
       Engineering-Mathematics       Combinatorics       GATE 2004
Question 15 Explanation: 
No. of letters from A-Z is = 26
Each is printed twice the no. of letters = 26×2 = 52
If Mala has k colours, she can have k pairs of same colours.
She also can have kC2 different pairs in which each pair is having different colours.
So total no. of pairs that can be coloured = k+kC2
k+kC2 ≥ 26
k+k(k-1)/2 ≥ 26
k(k+1)/2 ≥ 26
k(k+1) ≥ 52
k(k+1) ≥ 7*8
k≥7
Question 16

n couples are invited to a party with the condition that every husband should be accompanied by his wife. However, a wife need not be accompanied by her husband. The number of different gatherings possible at the party is

A
B
C
D
       Engineering-Mathematics       Combinatorics       GATE 2003
Question 16 Explanation: 
The possibilities to attend party is
i) Both husband and wife comes
ii) Only wife comes
iii) Both are not come
The no. of different gatherings possible at party is
= 3 * 3 * 3 * 3 * ... n times
= 3n
Question 17

m identical balls are to be placed in n distinct bags. You are given that m ≥ kn, where, k is a natural number ≥1. In how many ways can the balls be placed in the bags if each bag must contain at least k balls?

A
B
C
D
       Engineering-Mathematics       Combinatorics       GATE 2003
Question 17 Explanation: 
Since we want at least k balls in each bag, so first we put kn balls into bags, k balls in each bag. Now we are left with m - kn balls, and we have to put them into n bags such that each bag may receive 0 or more balls. So applying theorem 2 of stars and bars with m - nk stars and n bars, we get number of ways to be

. So option (B) is correct.
Question 18

(a) In how many ways can a given positive integer n ≥ 2 be expressed as the sum of 2 positive integers (which are not necessarily distinct). For example, for n = 3, the number of ways is 2, i.e., 1+2, 2+1. Give only the answer without any explanation.

(b) In how many ways can a given positive integer n ≥ 3 be expressed as the sum of 3 positive integers (which are not necessarily distinct). For example, for n = 4, the number of ways is 3, i.e., 1+2+1, 2+1+1. Give only the answer without any explanation.

(c) In how many ways can a given positive integer n ≥ k be expressed as the sum of k positive integers (which are not necessarily distinct)? Give only the answer without explanation.

A
Theory Explanation is given below.
       Engineering-Mathematics       Combinatorics       GATE 2002
Question 19

How many 4-digit even numbers have all 4 digits distinct?

A
2240
B
2296
C
2620
D
4536
       Engineering-Mathematics       Combinatorics       GATE 2001
Question 19 Explanation: 
If the last digit is 0 then

If last digit is (2, 4, 6, 8)

Total possibilities = 504 + 1792 = 2296
Question 20

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from some same suit is

A
3
B
8
C
9
D
12
       Engineering-Mathematics       Combinatorics       GATE 2000
Question 20 Explanation: 
No. of cards = 52
No. of suits = 4(P)
Apply pigeon hole principal.
Then number of pigeons = n
floor [(n-1)/P] + 1 = 3
floor [(n-1)/P] = 2
floor [(n-1)] = 8
floor (n) = 8 + 1
n ≥ 9
Minimum no. of cards, n = 9
Question 21

The  number  of  binary  strings  of  n  zeroes  and  k  ones  that  no  two  ones  are adjacent is

A
n-1Ck
B
nCk
C
nCk+1
D
None of the above
       Engineering-Mathematics       Combinatorics       GATE 1999
Question 21 Explanation: 
Since there are n zeroes, so
XOXOXOXOXOXOX
n+1 gaps can be possible, where 1's can be placed so that no two one's are adjacent. So, no. of ways in which k 1's can be placed in n+1 gaps are,
n+1Ck
Question 22

Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the number of ways they can divide the flowers amongst themselves?

A
1638
B
2100
C
2640
D
None of the above
       Engineering-Mathematics       Combinatorics       GATE 1999
Question 22 Explanation: 
Formula for distributing n identical objects into r persons is,
n+r-1Cr-1
So for 10 roses,
10+2-1C2-1 = 11C1 = 11
For 15 sunflowers,
15+2-1C2-1 = 16C1 = 16
For 15 daffodils,
15+2-1C2-1 = 16C1 = 16
∴ The final answer is,
11×16×16 = 2816
Question 23

The number of permutations of the characters in LILAC so that no character appears in its original position, if the two L’s are indistinguishable, is _______.

A
12
       Engineering-Mathematics       Combinatorics       GATE 2020
Question 23 Explanation: 
There are 5 places.
― ― ― ― ―
Given: L I L A C
The derangement formula ⎣n!/e⎦ cannot be directly performed as there are repeated characters.
Let’s proceed in regular manner:
The L, L can be placed in other ‘3’ places as

(1) Can be arranged such that A, I, C be placed in three positions excluding ‘C’ being placed at its own position, which we get only 2×2×1 = 4 ways.
Similarly (2) can be filled as A, I, C being placed such that 4th position is not filled by A, so we have 2×2×1 = 4 ways. Similarly with (3).
Totally, we get 4+4+4 = 12 ways.
Question 24

Choose the correct alternatives (More than one may be correct).

The number of ways in which 5 A's, 5 B's and 5 C's can be arranged in a row is:
A
15!/(5!)3
B
15!
C
(15/5)
D
15!(5!3!)
       Engineering-Mathematics       Combinatorics       GATE 1990
Question 24 Explanation: 
The no. of ways,
Question 25

The exponent of 11 in the prime factorization of 300! is

A
27
B
28
C
29
D
30
       Engineering-Mathematics       Combinatorics       GATE 2008-IT
Question 25 Explanation: 
Question 26

In how many ways can b blue balls and r red balls be distributed in n distinct boxes?

A
B
C
D
       Engineering-Mathematics       Combinatorics       GATE 2008-IT
Question 26 Explanation: 
No. of blue ball distributed to n boxes in
C(n+b-1, b) = (n+b-1)!/ (n-1)!b!
No. of red distributed to n boxes is
(n+r-1, r) = (n+r-1)!/ (n-1)!r!
Total no. of ways = (n+b-1)!/(n-1)!b! * (n+r-1)!/(n-1)!r!
= (n+b-1)!(n+r-1)!/(n-1)!b!(n-1)!r!
Question 27

Consider the sequence <xn>, n>= 0 defined by the recurrence relation xn + 1 = c . xn2- 2, where c > 0.
Suppose there exists a non-empty, open interval (a, b) such that for all x0 satisfying a < x0 < b, the sequence converges to a limit. The sequence converges to the value?

A
B
C
2
D
       Engineering-Mathematics       Combinatorics       GATE 2007-IT
Question 27 Explanation: 
Let c=1, x0=1
Then,
x1 = c ⋅ (x0)2 - 2 = 1 ⋅ (1)2 - 2 = -1
x2 = c ⋅ (x1)2 - 2 = 1 ⋅ (-1)2 - 2 = -1
So, the value converges to -1, which is equal to

Exactly, only (B) is answer. As all the term of x converges to -1.
Question 28

Consider the sequence <xn>, n>= 0 defined by the recurrence relation xn + 1 = c. xn2- 2, where c > 0.
For which of the following values of c, does there exist a non-empty open interval (a,b) such that the sequence xn, converges for all x0 satisfying a < x0

    (i) 0.25
    (ii) 0.35
    (iii) 0.45
    (iv) 0.5
A
(i) Only
B
(i) and (ii) only
C
(i), (ii) and (iii) only
D
(i), (ii), (iii) and (iv)
       Engineering-Mathematics       Combinatorics       GATE 2007-IT
Question 28 Explanation: 
For the series to converge the limit: 'n' tends to infinity of (xn+1 / xn) should be <1.
From the recurrence we should have c(xn)2 - xn - 2 < 0
For all the above values of c we have above equation as negative.
Question 29
A
B
C
D
       Engineering-Mathematics       Combinatorics       GATE 2022
Question 29 Explanation: 

Question 30
Consider solving the following system of simultaneous equations using LU decomposition.
A
B
C
D
       Engineering-Mathematics       Combinatorics       GATE 2022
Question 30 Explanation: 
The LU decomposition of the given matrix is

Given,

(Assume x1,x2,x3 as a,b,c)






Question 31
The number of bit strings of length 8 that will either start with 1 or end with 00 is?
A
32
B
128
C
160
D
192
       Engineering-Mathematics       Combinatorics       ISRO CS 2014
Question 31 Explanation: 
→ Number of bit strings of length 8 that start with 1: 27 = 128.
→ Number of bit strings of length 8 that end with 00: 26 = 64.
→ Number of bit strings of length 8 that start with 1 and end with 00: 25 = 32.
→ Applying the subtraction rule, the number is 128+64−32 = 160
Question 32
Mala has a colouring book in which each english letter is drawn two times. She wants to point each of these 52 prints with one of k colours, such that the colour-pairs used to colour ay two letters are different. Both prints of a letter can also be coloured with the same colour. What is the minimum value of k that satisfies this requirement?
A
9
B
8
C
7
D
6
       Engineering-Mathematics       Combinatorics       Nielit Scientist-B IT 4-12-2016
Question 32 Explanation: 
No. of letters from A-Z is = 26
Each is printed twice the no. of letters = 26×2 = 52
If Mala has k colours, she can have k pairs of same colours.
She also can have k​ C​ 2 different pairs in which each pair is having different colours.
So total no. of pairs that can be coloured = k+​ k ​ C​ 2
k+​ k​ C​ 2​ ≥ 26
k+k(k-1)/2 ≥ 26
k(k+1)/2 ≥ 26
k(k+1) ≥ 52
k(k+1) ≥ 7*8
k≥7
Question 33
What is the minimum number of students needed in a class to guarantee that there are at least 6 students whose birthdays fall in the same month?
A
6
B
23
C
61
D
72
E
91
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2018
Question 34
There are four bus lines between A and B; And three bus lines between B and C The number of way a person roundtrip by bus from A to C by way of B will be
A
12
B
7
C
144
D
264
       Engineering-Mathematics       Combinatorics       Nielit Scientist-B IT 22-07-2017
Question 34 Explanation: 
The number of bus lines between a and b =4
The number of bus lines between b and c =3
The number of possible combinations between a and c going through b are 4 * 3 = 12.
if you're talking about round trip, he has 12 possible ways to get there and 12 possible ways to get back, so the total possible ways is 12 * 12 = 144.
Question 35
The solution of the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2​ with a​ 0​ =2,a​ 1​ =7
A
a​ r​ =(3)​ r​ +(1)​ r
B
2a​ r​ =(2)​ r​ /3 -(1)​ r
C
a​ r​ =3​ r+1​ -(-1)​ r
D
a​ r​ =3(2)​ r​ -(-1)​ r
       Engineering-Mathematics       Combinatorics       Nielit Scientific Assistance IT 15-10-2017
Question 35 Explanation: 
Given the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2 and a​ 0​ =2,a​ 1​ =7.
For r =2, a​ 2=​ a​ 2-1​ +2a​ 2-2​ =a​ 1​ +2a​ 0​ =7+2*2=7+4=11
For r=3,a​ 3=​ a​ 3-1​ +2a​ 3-2​ =a​ 2​ +2a​ 1​ =11+2*7=11+14=25
From the above options , Substitute the r values 0,1,2,3 then option -D gives the solution to recurrence relation.
Question 36

How many ways are there to arrange the nine letters of the word ALLAHABAD?

A
4560
B
4000
C
7560
D
7500
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 36 Explanation: 
Step-1: There are 4A, 2L, 1H, 1B and 1D.
Step-2: Total number of alphabets! / alphabets are repeating using formula (n!) / (r1! r2!..).
Step-3: Repeating letters are 4A's and 2L's
= 9! / (4!2!)
= 7560
Question 37

How many bit strings of length eight (either start with a 1 bit or end with the two bits 00) can be formed?

A
64
B
255
C
160
D
128
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 37 Explanation: 
Use the subtraction rule.
1. Number of bit strings of length eight that start with a 1 bit: 27 = 128
2. Number of bit strings of length eight that end with bits 00: 26 = 64
3. Number of bit strings of length eight that start with a 1 bit and end with bits 00: 25 = 32
The number is 128+64+32 = 160
Question 38

What is the solution of the recurrence relation an = 6an-1 - 9an-2 with initial conditions a0=1 and a1=6?

A
an = 3n + 3n2
B
an = 3n + n3n
C
an = 3n + 3nn
D
an = n3 + n3n
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 38 Explanation: 
→ Let c1, c2, ..., ck be real numbers.
→ Suppose that the characteristic equation rk −c1rk−1 −···−ck = 0 has k distinct roots r1, r2, ..., rk.
→ Then, a sequence {an} is a solution of the recurrence relation: an = c1an−1 + c2an−2 + ··· + ckan−k
→ if and only if an = α1rn1 + α2rn2 + ··· + αk rnk for n = 0,1,2,..., where α1, α2, ..., αk are constants.
→ r2 − 6r + 9 = 0 has only 3 as a root.
→ So the format of the solution is an = α13n + α2n3n.
→ Need to determine α1 and α2 from initial conditions:
a0 = 1 = α1
a1 = 6 = α13 + α23
Solving these equations we get α1=1 and α2=1
Therefore, an = 3n + n3n.
Question 39

What is the minimum number of students in a class to be sure that three of them are born in the same month?

A
24
B
12
C
25
D
13
       Engineering-Mathematics       Combinatorics       JT(IT) 2018 PART-B Computer Science
Question 39 Explanation: 
With the help of Pigeonhole principle we can get the solution. The idea is that if you n items and m possible containers. If n > m, then at least one container must have two items in it. So, total 15 minimum number of students.
Question 40
The solution of the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2​ with a​ 0​ =2,a​ 1​ =7
A
a​ r​ =(3)​ r​ +(1)​ r
B
2a​ r​ =(2)​ r​ /3 -(1)​ r
C
a​ r​ =3​ r+1​ -(-1)​ r
D
a​ r​ =3(2)​ r​ -(-1)​ r
       Engineering-Mathematics       Combinatorics       Nielit Scientific Assistance CS 15-10-2017
Question 40 Explanation: 
● Given the recurrence relation a​ r​ =a​ r-1​ +2a​ r-2 and a​ 0​ =2,a​ 1​ =7.
● For r =2, a​ 2=​ a​ 2-1​ +2a​ 2-2​ =a​ 1​ +2a​ 0​ =7+2*2=7+4=11 ● For r=3,a​ 3=​ a​ 3-1​ +2a​ 3-2​ =a​ 2​ +2a​ 1​ =11+2*7=11+14=25
● From the above options ,Substitute the r values 0,1,2,3 then option -D gives the solution to recurrence relation.
Question 41

How many 3 digit numbers are there with all different odd digits?

A
16
B
48
C
54
D
60
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 41 Explanation: 
• Three digit odd numbers implies the numbers would only be made of digits 1 , 3 , 5 , 7 , 9 With repetition of digits we would have had 5 * 5 * 5 = 125
• But for every hundreds, maximum of 4 tens is possible (avoiding the duplicate of digit used in hundreds)
• And each of these 4 tens, maximum of 3 units is possible (avoiding the duplicate of digits used in tens)
• 5 * 4 * 3 = 60
Question 42

In how many ways can a committee of 4 people be chosen from a group of 12?

A
495
B
595
C
395
D
295
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 42 Explanation: 
As the order of people does not matter, it is C4 12
C(n,r) = C(12,4)
= 12! / [(4!(12−4)!)]
= 495
Hence, a committee of 4 people be selected from a group of 12 people in 495 ways.
Question 43

The sum of n terms of 1/(1*2) + 1/(2*3) + 1/(3*4) + ... is

A
(n+1)/n
B
n/(n+1)
C
n/(2n+1)
D
(2n+1)/n
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 43 Explanation: 
Sum upto n terms = 1/(1*2) + 1/(2*3) + 1/(3*4) + ........ + 1/(n*(n+1))
where
1st term = 1/(1*2)
2nd term = 1/(2*3)
3rd term = 1/(3*4)
.
.
.
.
n-th term = 1/(n*(n+1))
n-th term = 1/(n*(n+1))
i.e. the k-th term is of the form 1/(k*(k+1))
which can further be written as k-th term = 1/k - 1/(k+1)
So, sum upto n terms can be calculated as:
(1/1 - 1/1+1) + (1/2 - 1/2+1) + (1/3 - 1/3+1) + ......... + (1/n-1 - /1n) + (1/n - 1/n+1)
= (1 - 1/2) + (1/2 - 1/3) + (1/3 - 1/4) + ......... + (1/n-1 - 1/n) + (1/n - 1/n+1)
= 1 - 1/n+1
= ((n+1) - 1)/n+1
= n/n+1
Question 44

How many integers are between 1 and 200 which are divisible by any one of the integers 2,3 and 5(Hint: use set operation)?

A
125
B
145
C
146
D
136
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 44 Explanation: 
A) numbers divisible by 2: 200/2 = 100
B) numbers divisible by 3: 200/3 = 66
C) numbers divisible by 5: 200/5 = 40
Counting twice:
AB) numbers divisible by 6: 200/6 = 33
AC) numbers divisible by 10: 200/10 = 20
BC) numbers divisible by 15: 200/15 = 13
Counting 3 times:
ABC) numbers divisible by 30: 200/30 = 6
Total of numbers = A + B + C - AB - AC - BC + ABC = 100 + 66 + 40 - 33 - 20 -13 + 6 = 146
Question 45

The number of two digit numbers divisible by the product of digits is:

A
8
B
14
C
13
D
5
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 45 Explanation: 
11=1*1=1 which is a factor of 11
12=1*2=2 which is a factor of 12
15=1*5=5 which is a factor of 15
24=2*4=8 which is a factor of 24
36=3*6=12 which is a factor of 36
Question 46

The sum of the series: (1/2) + (1/3) + (1/4) - (1/6) + (1/8) + (1/9) + (1/16) - (1/12) + ... + α is:

A
(1/2) - log(√2)3
B
1 + log(√2)3
C
3/2
D
1/2 + log(√2)3
       Engineering-Mathematics       Combinatorics       JT(IT) 2016 PART-B Computer Science
Question 46 Explanation: 
The sum of the series: (1/2) + (1/3) + (1/4) - (1/6) + (1/8) + (1/9) + (1/16) - (1/12) + ... + α is 1 + log(√2)3.
Question 47
Consider a sequence F​ 00​ defined as : F​ 00​ (0) = 1, F​ 00​ (1) = 1
F​ 00​ (n) = ((10 ∗ F​ 00​ (n – 1) + 100)/ F​ 00​ (n – 2)) for n ≥ 2 Then what shall be the set of values of the sequence F​ 00​ ?
A
(1, 110, 1200)
B
(1, 110, 600, 1200)
C
(1, 2, 55, 110, 600, 1200)
D
(1, 55, 110, 600, 1200)
       Engineering-Mathematics       Combinatorics       UGC NET CS 2017 Jan -paper-2
Question 47 Explanation: 
Given data,
Sequence F​ 00​ defined as
F​ 00​ (0) = 1,
F​ 00​ (1) = 1,
F​ 00​ (n) = ((10 ∗ F​ 00​ (n – 1) + 100)/ F​ 00​ (n – 2)) for n ≥ 2
Let n=2
F​ 00​ (2) = (10 * F​ 00​ (1) + 100) / F​ 00​ (2 – 2)
= (10 * 1 + 100) / 1
= (10 + 100) / 1
= 110
Let n=3
F​ 00​ (3) = (10 * F​ 00​ (2) + 100) / F​ 00​ (3 – 2)
= (10 * 110 + 100) / 1
= (1100 + 100) / 1
= 1200
Similarly, n=4
F​ 00​ (4) = (10 * F​ 00​ (3) + 100) / F​ 00​ (4 – 2)
= (12100) / 110
= 110
F​ 00​ (5) = (10 * F​ 00​ (4) + 100) / F​ 00​ (5 – 2)
= (10*110 + 100) / 1200
= 1
The sequence will be (1, 110, 1200,110, 1).
Question 48
How many multiples of 6 are there between the following pairs of numbers ?
0 and 100 and –6 and 34
A
16 and 6
B
17 and 6
C
17 and 7
D
16 and 7
       Engineering-Mathematics       Combinatorics       UGC NET CS 2017 Jan -paper-2
Question 48 Explanation: 
Method-1:
0 and 100 → Counting sequentially:
0,6,12,18,24,30,36,42,48,54,60,66,72,78,84,90,96 Total=17
–6 and 34 → Counting sequentially: -6,0,6,12,18,24,30
Total=7
Method-2: 0 and 100 → Maximum number is 100. Divide ⌊100/6⌋ = 16+1 =17
Here, +1 because of 0.
–6 and 34 → Maximum number is 34. Divide ⌊34/6⌋ = 5+1+1 =7
Here, +1 because of 0 and +1 for -6
Question 49
Which of the following arguments are not valid ?
(a) “If Gora gets the job and works hard, then he will be promoted. If Gora gets promotion, then he will be happy. He will not be happy, therefore, either he will not get the job or he will not work hard”.
(b) “Either Puneet is not guilty or Pankaj is telling the truth. Pankaj is not telling the truth, therefore, Puneet is not guilty”.
(c) If n is a real number such that n >1, then n​ 2 ​ >1. Suppose that n​ 2 ​ >1, then n >1.
A
(a) and (c)
B
(b) and (c)
C
(a), (b) and (c)
D
(a) and (b)
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Dec- paper-2
Question 50
How many strings of 5 digits have the property that the sum of their digits is 7?
A
66
B
330
C
495
D
99
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Jun- paper-2
Question 50 Explanation: 
→ From the given question, there should be string with 5 digits and sum of that digits should be 7
→ There is no specification about positive,negative digits and also repetition of digits.
→ We are assuming the positive digits which is greater than or equal to 0.
→ The starting digit of the string should not be zero. We will also consider the repetition of digits.
→ Example of such strings are 70000,61000,60100,60010..,
→ The possible number of strings are C((n+r-1),(r-1))
→ From the given data n=7,r=5 then We have to fine C(11,4) which is equal to 330
Question 51
In how many ways can 15 indistinguishable fish be placed into 5 different ponds, so that each pond contains at least one fish ?
A
1001
B
3876
C
775
D
200
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Jun- paper-2
Question 51 Explanation: 
→ We know that if we have “n” identical items which will be distributed in “r” distinct groups where each must get at least one then the number of way is C(n−1,r−1)
→ From the given question, n=15, r=5 We need to calculate C(14,4) and it’s value is 1001.
Question 52
Consider a proposition given as :
“ x ≥ 6, if x​ 2​ ≥ 5 and its proof as:
If x ≥ 6, then x​ 2​ = x.x ≥ 6.6 = 36 ≥ 25
Which of the following is correct w.r.to the given proposition and its proof?
(a)The proof shows the converse of what is to be proved.
(b)The proof starts by assuming what is to be shown.
(c)The proof is correct and there is nothing wrong.
A
(a) only
B
(c) only
C
(a) and (b)
D
(b) only
       Engineering-Mathematics       Combinatorics       UGC NET CS 2015 Jun- paper-2
Question 52 Explanation: 
The proof which is described in the question is wrong because for a given “x” value , x​ 2​ >=5 but in the proof they mentioned 36>=25 which is wrong.
Question 53
Minimum number of individual shoes to be picked up from a dark room ( containing 10 pair of shoes) if we have to get at least one proper pair :
A
2
B
20
C
11
D
None of these
       Engineering-Mathematics       Combinatorics       UGC NET CS 2005 june-paper-2
Question 53 Explanation: 
→ There are 10 pair of shoes available in the dark room which means 20 individual shoes are available in the room.
→ If you pick shoes from one to ten individual shoes, there may be chance of getting same individual shoes.
→ There is no guarantee that getting one proper pair from 10 individual shoes.
→ If You pick 11 shoes, then there may chance of 10 individual shoes of same type and one individual shoe of another type. So we will get at least one proper pair shoe from 11 individual shoes.
Question 54
The logic of pumping lemma is a good example of :
A
pigeon hole principle
B
recursion
C
divide and conquer technique
D
iteration
       Engineering-Mathematics       Combinatorics       UGC NET CS 2006 June-Paper-2
Question 54 Explanation: 
→ A pumping lemma (or) pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language.
→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle.
Question 55
How many cards must be chosen from a deck to guarantee that at least I. two aces of two kinds are chosen. II. two aces are chosen. III. two cards of the same kind are chosen. IV. two cards of two different kinds are chosen.
A
50, 50, 14, 5
B
51, 51, 15, 7
C
52, 52, 14, 5
D
51, 51, 14, 5
       Engineering-Mathematics       Combinatorics       UGC NET CS 2014 June-paper-2
Question 56
The number of eight-bit strings beginning with either 111 or 101 is______.
A
64
B
128
C
265
D
None of the above
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 Sep-paper-2
Question 56 Explanation: 
Given data,
-- Total number of bits=8
-- Beginning with either 111 or 101
-- Total number of strings=?
Step-1: First consider 111 as beginning numbers. It look like

Possibility to get combinations are 25 =32 Step-2: Second consider 101 as beginning numbers. It look like

Possibility to get combinations are 25 =32 Step-3: Total number of strings are 32+32
=64
Question 57
Find the number of ways to paint 12 offices so that 3 of them will be green, 2 of them pink, 2 of them yellow and the rest ones white.
A
55,440
B
1,66,320
C
4.790E+08
D
39,91,680
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 Sep-paper-2
Question 57 Explanation: 
Given data,
-- Total number of offices=12
-- Colours are Green=3, Pink=2, Yellow=2 and White=5
white= 12-7
= 5
-- Total number of ways to paint 12 offices=?
Step-1: Total number of offices are 12 then we get maximum 12!
12!=479001600
Step-2: Green=3, Pink=2, Yellow=2 and White=5
maximum possibilities of individual colours are
= 3! * 2! * 2! * 5!
= 2880
Step-3: Total number of ways to paint 12 offices= (12! / (3! * 2! * 2! * 5!))
= 479001600 / 2880
= 166320
Question 58
The number of bit strings of length eight that will either start with a 1 bit or end with two bits 00 shall be
A
32
B
64
C
128
D
160
       Engineering-Mathematics       Combinatorics       UGC NET CS 2012 Dec-Paper-2
Question 58 Explanation: 
→ Number of bit strings of length 8 that start with 1: 27 = 128.
→ Number of bit strings of length 8 that end with 00: 26 = 64.
→ Number of bit strings of length 8 that start with 1 and end with 00: 25 = 32.
→ Applying the subtraction rule, the number is 128+64−32 = 160
Question 59
Suppose that someone starts with a chain letter. Each person who receives the letter is asked to send it on to 4 other people. Some people do this, while some do not send any letter. How many people have seen the letter, including the first person, if no one receives more than one letter and if the chain letter ends after there have been 100 people who read it but did not send it out ? Also find how many people sent out the letter ?
A
122 & 22
B
111 & 11
C
133 & 33
D
144 & 44
       Engineering-Mathematics       Combinatorics       UGC NET CS 2012 Dec-Paper-2
Question 59 Explanation: 
→ Notice that since every person who sends out the letter sends it to exactly 4 other people, and no two people receive the letter twice, this situation can be modeled using a full rooted 4-ary tree.
→ The root represents the person who first sends out the letter, and the children of any vertex represent the 4 people that the related person sent letters.
→ From the question, total people are 100, The total number of people who received the letter can be found by computing the number total number of vertices in the rooted tree.
3n+1=100
n=100-⅓
=33
The number of people who read it but did not send it out is 100+33=133
The number of people sent out the letter is 33
Question 60
If n and r are non-negative integers and n ≥ r, then p(n + 1, r) equals to
A
(p(n, r)(n + 1)) / (n + 1 – r)
B
(p(n, r) (n + 1)) / (n – 1 + r)
C
(p(n, r) (n – 1)) / (n + 1 – r)
D
(p(n, r) (n + 1)) / (n + 1 + r)
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 Dec-paper-2
Question 61
Any integer composed of 3n identical digits divisible by
A
2n
B
3n
C
5n
D
7n
       Engineering-Mathematics       Combinatorics       UGC NET CS 2011 June-Paper-2
Question 61 Explanation: 
Identical digits means similar(same) digits.
Any integer composed of 3n identical digits.
For example n=1, 3n= 31=3 which means three identical digits (111,222,333,444 and so on)
n=2, 32 =9 which means nine identical digits (111111111, 222222222 and so on)
The above numbers are is divisible by 3
111 is divisible by 3.
222, 333 and 444 are multiple of 3
Question 62
The middle term in the expansion of ( x/3 + 9 y )10
A
1 890 x 5 y 5
B
6 1236 x 5 y 5
C
3 77810 x 5 y 5
D
6 2136 x 5 y 5
       Engineering-Mathematics       Combinatorics       NIELIT Junior Teachnical Assistant_2016_march
Question 63
The second, third and fourth terms in the binomial expansion (x + a ) and 240, 720 and 1080 respectively. Then, x , a and n are :
A
x = 3 , a = 3 , n = 5
B
x = 2 , a = 3 , n = 4
C
x = 2 , a = 3 , n = 5
D
x = 3 , a = 2 , n = 5
       Engineering-Mathematics       Combinatorics       NIELIT Junior Teachnical Assistant_2016_march
Question 64
A test contains 100 true/false questions. How many different ways can a student answer the questions on the test, if the answer may be left blank also.
A
100P2
B
100C2
C
2100
D
3100
       Engineering-Mathematics       Combinatorics       UGC NET CS 2013 June-paper-2
Question 64 Explanation: 
Given data,
-- Total number of questions=100
-- Total possibilities for each question=3 (Note: BLANK or TRUE or FALSE)
Step-1: 1 question= 3 possibilities.

Question 65
The coefficient of x 2 in the expansion of is
A
-405/16
B
405/16
C
405/128
D
None of the above
       Engineering-Mathematics       Combinatorics       NIELIT Technical Assistant_2016_march
Question 66
The number of integers between 1 and 250 that are divisible by 2, 5 and 7 is
A
2
B
3
C
5
D
8
       Engineering-Mathematics       Combinatorics       UGC NET CS 2010 Dec-Paper-2
Question 66 Explanation: 
Here, we have to find all possible integers between 250 which was divisible by 2,5 and 7.
Solving this problem by 2 methods:
1. Venn diagram
2. Mathematical substitution.
In this problem, we are using Mathematical substitution method.
Step-1: According to condition, we can perform least common multiple(LCM) of 2,5 and 7=70
Step-2: Total number of integers= ⌊250/70⌋
= 3
Note: Divisible numbers are 70,140 and 210.
Question 67
The value of the following expression (13 / 4 * 3) % 5 + 1 is
A
5.75
B
2.95
C
1.4875
D
5
       Engineering-Mathematics       Combinatorics       UGC NET CS 2010 Dec-Paper-2
Question 67 Explanation: 
(13 / 4 * 3) % 5 + 1
Step-1: (13 / 4 * 3) % 5 + 1
Step-2: (3.25*3)%5+1
Step-3: 9.75%5+1
Step-4: 4.75+1
Step-5: 5.75
Note: ( ) having highest precedence then *,/ and % have same precedence order.
Question 68
The school athletics coach has to choose 4 students for the relay team. He calculates that there are 3876 ways of choosing the team if the order in which the runners are placed is not considered. How many ways are there of choosing the team if the order of the runners is to be taken into account?
A
Between 12,000 and 25,000
B
Between 30,000 and 60,000
C
Between 75,000 and 99,999
D
More than 100,000
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 68 Explanation: 
The actual answer is 3876 × 4! = 3876 × 24 = 93024.
Question 69
Consider a social network with n persons. Two persons A and B are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons F 1 , . . . , F m such that A and F 1 are friends, F 1 and F 2 are friends, . . . , F m−1 and F m are friends, and finally F m and B are friends. It is known that there are k persons such that no pair among them is connected. What is the maximum number of friendships possible?
A
Descriptive Explanation
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 69 Explanation: 
To solve the above question, consider an illustrative scenario where k is 2. Given that the graph has two connected components, what is the maximum number of edges possible.
To solve the above question, consider an illustrative scenario where k is 2. Given that the graph has two connected components, what is the maximum number of edges possible. Let the first connected component be G 1 with n 1 vertices and the other be G 2 with n 2 vertices. Further assume that n 1 ≥ n 2 . Note that there are no edges between a vertex from G 1 and a vertex from G 2 . Therefore, each vertex in G 2 can be connected by an edge to at most n 2 − 1 vertices. If a vertex from G 2 is moved to G 1 , then this vertex can potentially be part of n 1 edges. Since n 1 ≥ n 2 , moving vertices from G 2 to G 1 would increase the number of edges. The maximum number of edges would be obtained when n 2 is 1 and n 1 = n − 1.
Coming back to our original question: suppose the graph is made of k connected components, then the maximum number of edges is obtained when one of the components has n − (k − 1) vertices and the other components have 1 vertex each.
Hence the maximum number of edges possible is n−k+1 C 2 .
Question 70
A cook has a kitchen at the top of a hill, where she can prepare rotis. Each roti costs one rupee to prepare. She can sell rotis for two rupees a piece at a stall down the hill. Once she goes down the steep hill, she can not climb back in time make more rotis. (a) Suppose the cook starts at the top with R rupees. What are all the possible amounts of money she can have at the end? (b) Suppose the cook can hitch a quick ride from her stall downhill back to the kitchen uphill, by offering a paan to a truck driver. If she starts at the top with P paans and 1 rupee, what is the minimum and maximum amount of money she can have at the end?
A
Descriptive Explanation
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 70 Explanation: 
(a). R − M + 2S, where M ≤ R is the number of rotis made and S ≤ M is the number of rotis sold. The set of possible values is {0, 1, 2, . . . , 2R}.
(b) Minimum 0 rupees, by preparing 1 roti and doing nothing else. Maximum 2 P +1 rupees: she can first make one roti and sell it to get 2 rupees. She can then make P trips to the kitchen, doubling her money with every trip.
Question 71
An airline runs flights between several cities of the world. Every flight connects two cities. A millionaire wants to travel from Chennai to Timbuktu by changing at most k − 1 flights. Being a millionaire with plenty of time and money, he does not mind revisiting the same city multiple times, or even taking the same flight multiple times in his quest. Can you help the millionaire by describing how to compute the number of ways he can make his journey? How many steps does your procedure take if there are n cities and he can change flights at most k − 1 times. You can assume that the procedure can add or multiply two numbers in a single operation.
A
Descriptive Explanation
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE(M.Sc. / Ph.D. Programme in Computer Science) 18May 2015
Question 71 Explanation: 
Let c denote Chennai and t denote Timbuktu. We are asked to find the number of c, t-walks with at most k edges. For any city v, let N (v, i) denote the number of c, v-walks with exactly i edges. It is clear that N (c, 0) = 1 and N (v, 0) = 0 for any v 6 = c. To go from c to v in exactly i + 1 steps, one can choose to go to any u such that (u, v) ∈ E in exactly i steps, and then go to v in one more step. The following recurrence is thus easy to see.

We can create a two-dimensional with nk entries, and fill them in according to the above recurrence. The desired answer is given by N (t, 0) + N (t, 1) + · · · + N (t, k).
We need to fill in nk entries, and we add at most n numbers to compute each entry. Since adding two numbers is assumed to take unit time, we can add n numbers in O(n) time. Thus the overall time taken by the algorithm is O(n 2 k).
Question 72
In a set of 8 positive integers, there always exists a pair of numbers having the same remainder when divided by :
A
7
B
11
C
13
D
15
       Engineering-Mathematics       Combinatorics       UGC NET CS 2008-june-Paper-2
Question 72 Explanation: 
Given data,
-- Set of positive integers=8
-- A pair of numbers having the same remainder when divided by=?
Step-1: This problem, we can use pigeonhole principle.
Pigeonhole Principle: If there are ‘X’ positive integers to be placed in ‘Y’ possible remainder where Y < X, then there is at least one possible remainder which receives more than one positive integer.
Option-A: Total number of possible remainders, divided by 7 is 0,1,2,3,4,5,6.
These numbers are less than 8 only.
Option-B,C and D: Total number of possible remainders,
divided by 11, 13, 15 is greater than 8
Question 73
In a party there are 2n participants, where n is a positive integer. Some participants shake hands with other participants. It is known that there are no three participants who have shaken hands with each other. Prove that the total number of handshakes is not more than n 2 .
A
Descriptive Explanation
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE M.Sc. / Ph.D. Programme in Computer Science (18 May 2017)
Question 73 Explanation: 
Model this as a graph problem, we are looking for a graph without a triangle. We show that the maximum number of edges that a triangle-free graph on 2n vertices can have is n 2 .
The proof by induction on n.
The base cases n = 1, 2 are easy to see by inspection.
For the inductive step, let n ≥ 3. If the graph G has no edges then there is nothing to prove. Otherwise, take an edge {x, y}, and consider the graph G' on 2(n − 1) vertices obtained by deleting both the vertices {x, y} from G.
By the inductive hypothesis, G' has at most (n − 1) 2 edges. Since graph G is triangle- free and {x, y} is an edge in G, there is no vertex v in G' such that both {v, x} and {v, y} are edges in G. So the number of edges with one end-point in the set {x, y} and the other in the set of vertices of G 0 is at most the number of vertices in G' , namely 2(n − 1).
Now the set of edges of G consists of (i) all the edges in G' , plus (ii) the one edge {x, y}, plus (iii) the at most 2(n − 1) edges with exactly one end-point in {x, y}. So the number of edges of G is at most (n − 1) 2 + 1 + 2(n − 1) ≤ n 2 .
Question 74
For the inter-hostel six-a-side football tournament, a team of 6 players is to be chosen from 11 players consisting of 5 forwards, 4 defenders and 2 goalkeepers. The team must include at least 2 forwards, at least 2 defenders and at least 1 goalkeeper. Find the number of different ways in which the team can be chosen.
A
260
B
340
C
720
D
1440
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 74 Explanation: 
5 positions are fixed. The 6th can be forward/defender/goalkeeper.
Question 75
Let M be the maximum number of unit disks (disks of radius 1) that can be placed inside a disk of radius 10 so that each unit disk lies entirely within the larger disk and no two unit disks overlap. Then:
A
M < 25
B
25 ≤ M < 40
C
40 ≤ M < 55
D
M ≥ 55
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 75 Explanation: 
A 14 × 14 square can be inscribed that holds 49 unit disks To this you can add (at least) 4 more disks on each side, so at least 65 unit disks fit inside the big circle.
Question 76
Avinash is taller than Abhay. Bharat is taller than Vinu and Vinay is taller than Bharat. Which of the following is a minimal set of additional information that can determine the tallest person?
A
Vinay is taller than Avinash and Abhay is taller than Bharat.
B
Avinash is taller than Vinay
C
Abhay is shorter than Vinay.
D
None of the above.
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 76 Explanation: 
Given: Avinash > Abhay, Vinay > Bharat > Vinu.
The minimal extra information we need to decide the tallest is a comparison between Avinash and Vinay.
(a) decides the tallest but is not minimal since it gives an extra condition.
(b) decides that Avinash is tallest, so (b) is the correct answer.
(c) does not decide the tallest.
(d) (none of the above) is wrong since (b) is a valid answer.
Question 77
There are n students in a class. The students have formed k committees. Each committee consists of more than half of the students. Show that there is at least one student who is a member of more than half of the committees.
A
Explanation
       Engineering-Mathematics       Combinatorics       CHENNAI MATHEMATICAL INSTITUTE - M.Sc. / Ph.D. Programme in Computer Science ( 15 May 2014 )
Question 77 Explanation: 
Consider a table with one row for each student and one column for each committee. The table has 1 in the row corresponding to a student s and the column corresponding to a committee c if the student s is a member of the committee c. The table has 0 in the row corresponding to a student s' and the column corresponding to a committee c 0 if the student s' is not a member of the committee c' . Since each committee consists of more than half of the students, each column of the table has more than half its entries as 1. Hence, there are more than (n x k)/2 entries in the table that are 1. Hence, there is at least one row in the table with more than half its entries as 1 (otherwise, it is not possible to have more than (n x k)/2 entries in the table that are 1). This row corresponds to a student who is a member of more than half of the committees.
Question 78
The logic of pumping lemma is an example of __________.
A
iteration
B
recursion
C
the divide and conquer principle
D
the pigeonhole principle
       Engineering-Mathematics       Combinatorics       UGC NET CS 2017 Nov- paper-3
Question 78 Explanation: 
→ A pumping lemma (or) pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language.
→ The proofs of these lemmas typically require counting arguments such as the pigeonhole principle.
→ Hence, the logic of pumping lemma is a good example of the pigeonhole principle.
Question 79
How many are there to place 8 indistinguishable balls into four distinguishable bins?
A
70
B
165
C
8​ C​ 4
D
8​ P​ 4T
       Engineering-Mathematics       Combinatorics       UGC NET June-2019 CS Paper-2
Question 79 Explanation: 
This is precisely the problem we saw to solve the r-combination with repetition:
= C(8+4-1,8)
= 11 C​ 8
= 11! / (8!(11-8)!)
= 165
Question 80
Consider an LPP given as

Max Z=2x1 - x2 + 2x3

Subject to the constraints

2x1 + x2 ≤ 10

x1 + 2x2 - 2x3 ≤ 20

x1 + 2x3 ≤ 5

x1, x2, x3 ≥ 0

What shall be the solution of the LPP after applying first iteration of the Simplex Method?

A
x1=5/2, x2=0, x3=0, Z=5
B
x1=0, x2=0, x3=5/2, Z=5
C
x1=0, x2=5/2, x3=0, Z= -5/2
D
x1=0, x2=0, x3=10, Z=20
       Engineering-Mathematics       Combinatorics       UGC NET June-2019 CS Paper-2
Question 81
How many cards must be selected from a standard deck of 52 cards to guarantee that at least three hearts are present among them?
A
9
B
13
C
17
D
42
       Engineering-Mathematics       Combinatorics       UGC NET June-2019 CS Paper-2
Question 82
What is the remainder when 44444444 is divided by 9?
A
1
B
2
C
5
D
7
E
8
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2018
Question 83
Consider the following Linear programming problem (LPP) :
Maximize z = x1 + x2
Subject to the constraints:


The solution of the above LPP is:
A
x1=750, x2=750, z=1500
B
x1=500, x2=100, z=1500
C
x1=1000, x2=500, z=1500
D
x1=900, x2=600, z=1500
       Engineering-Mathematics       Combinatorics       UGC-NET DEC-2019 Part-2
Question 84
Let a2e mod n = (ae)2 mod n and a2e+1 mod n = a (ac)2 mod n. For a = 7, b = 17 and n = 561, what is the value of ab(mod n)?
A
160
B
166
C
157
D
67
       Engineering-Mathematics       Combinatorics       UGC-NET DEC-2019 Part-2
Question 85
If x+2y=30, then
((2y/5) + (x/3)) + ((x/5) + (2y/3))
Will be equal to
A
8
B
16
C
18
D
20
       Engineering-Mathematics       Combinatorics       ISRO CS 2020       Video-Explanation
Question 85 Explanation: 
Question 86
How many different 6-member committees can be formed from 6 men and 4 women with a restriction that each committee should include an equal number of men and women
A
120
B
80
C
420
D
6045
       Engineering-Mathematics       Combinatorics       APPSC-2016-DL-CS
Question 86 Explanation: 
Given data,
Committee members=6,
Mens=6
Women=4
Equal numbers of men and women are= ?
3 men out of 6, 3 women out of 4
6C3 * 4C3 ways
⇒ 20 * 4
⇒ 80
Note: There are 3 possibilities to consider an equal number of men and women.
Choose 4 men and 4 women then we get 6C4 * 4C4 ways = 15
Choose 2 men and 2 women then we get 6C2 * 4C2 ways = 90
Choose 3 men and 3 women then we get 6C3 * 4C3 ways = 80
Question 87
Consider 4-character long codes generated by using an alphabet consisting of 8-characters with no restriction on the number of repetitions of a character in a code. How many codes at least one character repeated?
A
2416
B
6720
C
1680
D
4096
       Engineering-Mathematics       Combinatorics       APPSC-2016-DL-CS
Question 88

Pigeonhole principle states that if A→B and |A|>|B| then _______

A
f is not onto
B
f is not one-one
C
f is neither one-one nor onto
D
f may be one-one
       Engineering-Mathematics       Combinatorics       APPSC-2016-DL-CA
Question 88 Explanation: 
From the given question we can clearly say that the given relation is not one-one because for the given relation to be one-one |A|<=|B|.
Question 89

Two girls have picked 10 roses, 15 sunflowers and 14 daffodils. What is the number of ways they can divide the flowers amongst themselves?

A
1,638
B
2,640
C
2,100
D
None of the given options
       Engineering-Mathematics       Combinatorics       APPSC-2016-DL-CA
Question 89 Explanation: 
The formula for distributing n identical objects among m person is = C(n+m-1,m-1)
So for roses = C(10+2-1,2-1) = 11
For sunflowers = C(15+2-1,2-1) = 16
For daffodils = C(14+2-1,2-1) = 15
So final answer is = 11*16*15 = 2640
Question 90
How many 10 digit numbers can be written by using the digits 1 and 2?
A
10 C1 + 9 C2
B
210
C
10 C2
D
10 1
       Engineering-Mathematics       Combinatorics       TNPSC-2012-Polytechnic-CS
Question 90 Explanation: 
For each digit we have two choices ‘1 or 2’. So no. of possible 10 digits nos.
2*2*2*2*2*2*2*2*2*2 = 210
Question 91
How many 4 digit even numbers have all 4 digits distinct?
A
2240
B
2296
C
2620
D
4536
       Engineering-Mathematics       Combinatorics       TNPSC-2012-Polytechnic-CS
Question 91 Explanation: 
For the no. to be even last digit should be even,
Case-3: Last digit contains ‘0’,

= 9 × 8 × 7
= 504
Case-2: Last digit does not contains ‘0’,

= 8 × 8 × 7 × 4C1
= 1792
∴ Answer is = 1792 + 504 = 2296
Question 92
The number of different signals which can be given from 6 flags of different colours taken one or more at a time, is
A
1958
B
1956
C
16
D
64
       Engineering-Mathematics       Combinatorics       TNPSC-2012-Polytechnic-CS
Question 92 Explanation: 
The no. of different signals which can be given from 6 flags of different colours taking n colours at a time,

where,
1 ≤ n ≤ 6
when n=1,
6C1 × ∠1 = 6
when n=2,
6C6 × ∠2 = 30
when n=3,
6C3 × ∠3 = 120
when n=4,
6C4 × ∠4 = 360
when n=5,
6C5 × ∠5 = 720
when n=6,
6C6 × ∠6 = 720
Total no. of ways
= 6 + 30 + 120 + 360 + 720 + 720
= 1956
Question 93
How many proper divisors (that is, divisors other than 1 or 7200) does 7200 have?
A
18
B
20
C
52
D
54
E
60
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2019
Question 94
Asha and Lata play a game in which Lata first thinks of a natural number between 1 and 1000. Asha must find out that number by asking Lata questions, but Lata can only reply by saying “yes” or “no”. Assume that Lata always tells the truth. What is the least number of questions that Asha needs to ask within which she can always find out the number Lata has thought of?
A
10
B
32
C
100
D
999
E
None of the above
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2019
Question 95
What are the last two digits of 1! + 2! + . . . + 100!?
A
00
B
13
C
30
D
33
E
73
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2019
Question 96
A row of 10 houses has to be painted using the colours red, blue, and green so that each house is a single colour, and any house that is immediately to the right of a red or a blue house must be green. How many ways are there to paint the houses?
A
199
B
683
C
1365
D
310 − 210
E
310
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2019
Question 97
How many distinct ways are there to split 50 identical coins among three people so that each person gets at least 5 coins?
A
335
B
350 − 250
C
(35 2)
D
(50 15)*335
E
(37 2)
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2017
Question 98
How many distinct words can be formed by permuting the letters of the word ABRACADABRA ?
A
11! / (5! 2! 2!)
B
11! / (5! 4!)
C
11! 5! 2! 2!
D
11!
E
11! 5! 4!
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2017
Question 99
Let S be the 4X4 square grid {(x, y) : x, y ε { 0, 1, 2, 3 }}. A monotone path in this grid starts at (0, 0) and at each step either moves one unit up or one unit right. For example, from the point (x, y) one can in one step either move to (x + 1, y) ε S or (x, y + 1) ε S, but never leave S. Let the number of distinct monotone paths to reach point (2, 2) starting from (0, 0) be z. How many distinct monotone paths are there to reach point (3, 3) starting from (0, 0)?
A
2Z+6
B
3Z+6
C
2Z+8
D
3Z+8
E
3Z+4
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2016
Question 100
Consider the sequence (sn : n ≥ 0) defined as follows: s0 = 0, s1 = 1, s2 = 1, and sn = sn-1 + sn-2 + sn-3, for n ≥ 3. Which of the following statements is FALSE?
A
s4k is even, for any k ≥ 0
B
s4k+1 is odd, for any k ≥ 0
C
s4k+2 is odd, for any k ≥ 0
D
sn is a multiple of 3, for only finitely many values of n
E
s4k+3 is even, for any k ≥ 0
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2016
Question 101
Let n ≥ 2 be any integer. Which of the following statements is not necessarily true?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2016
Question 102
There is a set of 2n people: n male and n female. A good party is one with equal number of males and females (including the one where none are invited). The total number of good parties is
A
2n
B
n2
C
D
E
none of the above
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2015
Question 103
The Fibonacci sequence is defined as follows: F0 = 0, F1 = 1, and for all integers n ≥ 2,
Fn = Fn-1 + Fn-2. Then which of the following statements is FALSE?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2014
Question 104
Consider numbers greater than one that satisfy the following properties:
(a) they have no repeated prime factors;
(b) for all primes p ≥ 2, p divides the number if and only if p − 1 divides the number.
The number of such numbers is
A
0
B
5
C
100
D
Infinite
E
None of the above
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2014
Question 105
The rules for the University of Bombay five-a-side cricket competition specify that the members of each team must have birthdays in the same month. What is the minimum number of mathematics students needed to be enrolled in the department to guarantee that they can raise a team of students?
A
23
B
91
C
60
D
49
E
None of the above
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2014
Question 106
Consider a sequence of non-negative numbers {xn : n = 1, 2,...}. Which of the following statements cannot be true?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2014
Question 107
Consider the polynomial p(x)=c0 + c1x + c2x^2 + c3x^3, where no coefficient is 0. The minimum number of multiplications required to evaluate p on an input x is
A
6
B
4
C
3
D
8
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2019
Question 107 Explanation: 
Given, p(x)=c0 + c1x + c2x^2 + c3 x^3
For minimum number of multiplications, lets modify above equation,
p(x)= c0 + x(c1 + c2x + c3 x^2)
=c0+x(c1+x(c2+c3x)
=c0+x*(c1+x*(c2+c3*x)
Hence minimum number of multiplications required is 3
Question 108
It is required to divide the 2n members of a club into n disjoint teams of 2 members each. The teams are not labelled. The number of ways in which this can be done is:
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2012
Question 109
In how many different ways can r elements be picked from a set of n elements if
(i) Repetition is not allowed and the order of picking matters?
(ii) Repetition is allowed and the order of picking does not matter?
A
a
B
b
C
c
D
d
E
e
       Engineering-Mathematics       Combinatorics       TIFR PHD CS & SS 2012
Question 110
The minimum number of cards to e dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are with same number is
A
14
B
27
C
30
D
39
E
None of the above
       Engineering-Mathematics       Combinatorics       HCU PHD CS 2018 December
Question 110 Explanation: 
We know that in a deck of 52 cards there are 4 suits.
Now to guarantee that three cards are from same suit,
⇒ Let's first draw 4 cards of different sizes.
⇒ Now again draw 4 cards of different suits. Now we have 8 cards of 2 cards from each suit.
⇒ Now take 1 card from any suit, which will guarantee that 3 cards are from the same suit.
So, in total 9 cards are required.
Question 111
The president and treasurer are to be chosen from a student club consisting of 50 people. How many different choices of officers are possible if there are no restrictions?
A
2450
B
2500
C
1225
D
1250
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2017
Question 111 Explanation: 
We are picking 2 out of a field of 50, and order does matter.So
answer is P(50,2) = 2450
Question 112
In a college football training session, the defensive coordinator needs to have 10 players standing in a row. Among these 10 players, there are 1 freshman, 2 sophomore, 4 juniors and 3 seniors. How many different ways can they be arranged in a row if only their class level will be distinguished?
A
14600
B
12600
C
12800
D
None of the above
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2017
Question 112 Explanation: 
Since only their class level will be distinguished. So 2 sophomore will be treated same, 4 juniors will be treated same, and 3 seniors will be treated same.
Hence the no. of ways they can be arranged in a row,

=12600
Question 113
In how many ways can 5 different trees be planted in a circle?
A
24
B
12
C
6
D
120
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2017
Question 113 Explanation: 
There are a total of 5! (=120) ways to plant five different trees. However, the trees are in a circle, in which each "way" is counted five times, due to rotations. This leaves us 5!/5 = 4! = 24 ways to plant five different trees in a circle.
Question 114
How many 0's are at the end of 20! when represented in octal?
A
4
B
5
C
6
D
7
       Engineering-Mathematics       Combinatorics       HCU PHD CS 2018 June
Question 114 Explanation: 
Count up the number of factors of 5 and the number of factors of 2 in 20!. Since we get a zero for every pair of factors 5x2, then the minimum of these will answer your question. More simply, 5 happens less often as a factor (since it's bigger than 2), so we need only count up the number of 5's. In particular, there's one each in 5,10,15,20, so there are 4 zeroes at the end.
Question 115
The format for car number plates in a country is two digits followed by three vowels, e.g. 04 IOU. A license plate is called "confusing" if the digit 0 (zero) and the vowel o are both present on it. For example 04 IOU is confusing but 20 AEI is not. How are many distinct number plates possible that are not confusing?
A
12500
B
6400
C
11341
D
None of these
       Engineering-Mathematics       Combinatorics       HCU PHD CS 2018 June
Question 115 Explanation: 
102 × 43 plates without vowel O + 92 × (53 − 43 ) plates with vowel O but without 0. This gives 6400 + 4941 = 11341.
Question 116
In one year, three awards (research, teaching and service) will be given to a class of 25 graduate students in a Statistics Department. If each student can receive at most one award, how many possible selections are there?
A
18,800
B
13,800
C
12,800
D
14,800
       Engineering-Mathematics       Combinatorics       HCU PHD CS 2018 June
Question 116 Explanation: 
The correct answer is that we will select 3 students out of 25 students and give awards one to each three of them.Also after selecting three students, the three awards can be distributed in 3! ways. So the correct answer is C(25,3)*3! =13800.
Question 117
In how many ways can nine students be partitioned into three teams containing four, three and two students respectively
A
9!
B
630
C
315
D
None of the above
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2015
Question 117 Explanation: 
The answer is
C(9,4)*C(5,3)*C(2,2) = 1260
Question 118
The general expression for the sequence an where an=4an-1 + 5an-2 , a1=2 and a2=6 is
A
B
C
D
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2016
Question 118 Explanation: 


Question 119

Let n denote a positive integer. suppose a function L is defined recursively as follows (here ⌊k⌋ denotes the “floor” of k).



What does L find?
A
L= ⌊log 2 n⌋
B
L=(n2/4)+1
C
L=2n
D
None of the above
       Engineering-Mathematics       Combinatorics       HCU PHD CS MAY 2012
Question 119 Explanation: 


Question 120
How many ways are there to pack six copies of the same book into four identical boxes, where a box can contain as many as six books?
A
4
B
6
C
7
D
9
       Engineering-Mathematics       Combinatorics       UGC NET JRF November 2020 Paper-2
Question 121
Consider the difference below for m ≥ 5:

Which statement about the difference is TRUE?
A
It is positive for infinitely many m ≥ 5 and negative for infinitely many m ≥ 5
B
It is positive for all m ≥ 5, and is increasing as m increases
C
It is negative for finitely many m ≥ 5 and is positive for infinitely many m
D
It is positive for all m ≥ 5, and is decreasing as m increases
E
It is negative for all m ≥ 5
       Engineering-Mathematics       Combinatorics       TIFR PHD 2022
There are 121 questions to complete.