## Combinatorics

Question 1 |

Which one of the following is a closed form expression for the generating function of the sequence {a

_{n}}, where a_{n}=2n+3 for all n=0,1,2,…?3/(1-x) ^{2} | |

3x/(1-x) ^{2} | |

2-x/(1-x) ^{2} | |

3-x/(1-x) ^{2} |

Question 1 Explanation:

Question 2 |

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

271 | |

272 | |

273 | |

274 |

Question 2 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 a

_{n}be the number of n-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for a_{n}?a _{n} = a_{(n-1)}+2a_{(n-2)} | |

a _{n} = a_{(n-1)}+a_{(n-2)} | |

a _{n} = 2a_{(n-1)}+a_{(n-2)} | |

a _{n} = 2a_{(n-1)}+2a_{(n-2)} |

Question 4 Explanation:

a

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 a

Similarly, a

_{n}= 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 a

_{3}= a_{1}+ a_{2}Similarly, a

_{n}= a_{n-1}+ a_{n-2}Question 5 |

The coefﬁcient of x

^{12}in (x^{3 }+ x^{4 }+ x^{5 }+ x^{6 }+ ...)^{3}is ___________.10 | |

11 | |

12 | |

13 |

Question 5 Explanation:

Co-efficient of x

⇒[x

= x

First Reduction:

As x

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

^{12}in (x^{3}+x^{4}+x^{5}+x^{6}+...)^{3}⇒[x

^{3}(1+x+x^{2}+x^{3}+...)]^{3}= x

^{9}(1+x+x^{2}+x^{3}+...)^{3}First Reduction:

As x

^{9}is out of the series, we need to find the co-efficient of x^{3}in (1+x+x^{2}+⋯)^{3}Here, m=3,k=3, the coefficient =

^{5}C_{3}=5!/2!3!=10Question 6 |

Consider the recurrence relation a

_{1 }= 8, a_{n }= 6n^{2 }+ 2n + a_{n-1}. Let a_{99 }= K × 10^{4}. The value of K is ___________.198 | |

199 | |

200 | |

201 |

Question 6 Explanation:

a

Replace a

⇒a

Given that a

⇒a

=6n

=6(n

Sum of n

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)

Given a

a

∴k=198

_{n}= 6n^{2}+2n+a_{(n-1)}Replace a

_{(n-1)}⇒a

_{n}=6n^{2}+2n+6(n-1)^{2}+2(n-1)+6(n-2)^{2}+2(n-2)+⋯a_{1}Given that a

_{1}=8, replace it⇒a

_{n}=6n^{2}+2n+6(n-1)^{2}+2(n-1)+6(n-2)^{2}+2(n-2)+⋯8=6n

^{2}+2n+6(n-1)^{2}+2(n-1)+6(n-2)^{2}+2(n-2)+⋯+6(1)^{2}+2(1)=6(n

^{2}+(n-1)^{2}+(n-2)^{2}+⋯+2^{2}+1^{2})+2(n+(n-1)+⋯1)Sum of n

^{2}=(n(n+1)(2n+1))/6Sum 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 a

_{99}=k×10^{4}a

_{99}=2(99) (100)^{2}=198×10^{4}∴k=198

Question 7 |

The number of divisors of 2100 is ______.

36 | |

37 | |

38 | |

39 |

Question 7 Explanation:

Let N = 2100

=2

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

=2

^{2}+3×5^{2}×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 _____ .

15 | |

16 | |

17 | |

18 |

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.

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 ______________.

89 | |

90 | |

91 | |

92 |

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.

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 _________

0.26 | |

0.27 | |

8 | |

0.29 |

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

= 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 |

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

27 | |

28 | |

29 | |

30 |

Question 11 Explanation:

300/11 = 27

27/11 = 2

2/11 = 0

-------------------

29

-------------------

The exponent of 11 in the prime factorization of 300! = 29

27/11 = 2

2/11 = 0

-------------------

29

-------------------

The exponent of 11 in the prime factorization of 300! = 29

Question 12 |

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

Question 12 Explanation:

Question 13 |

2 ^{20}
| |

2 ^{10} | |

None of the above |

Question 13 Explanation:

At each move, robot can move either 1 unit right, or 1 unit up, and there will be 20 such moves required to reach (10,10) from (0,0). So we have to divide these 20 moves, numbered from 1 to 20, into 2 groups : right group and up group. Right group contains those moves in which we move right, and up group contains those moves in which we move up. Each group contains 10 elements each. So basically, we have to divide 20 things into 2 groups of 10 10 things each, which can be done in 20! / (10!∗10! )=

^{20}C_{10}ways.Question 14 |

2 ^{9} | |

2 ^{19} | |

Question 14 Explanation:

Since we are not allowed to traverse from (4,4) to (5,4). So we will subtract all those paths which were passing through (4,4) to (5,4).

To count number of paths passing through (4,4) to (5,4), we find number of paths from (0,0) to (4,4), and then from (5,4) to (10,10).

From (0,0) to (4,4), number of paths =

From (5,4) to (10,10), number of paths =

So total number of paths required :

To count number of paths passing through (4,4) to (5,4), we find number of paths from (0,0) to (4,4), and then from (5,4) to (10,10).

From (0,0) to (4,4), number of paths =

^{8}C_{4}(found in same way as in previous question).From (5,4) to (10,10), number of paths =

^{11}C_{5}.So total number of paths required :

^{20}C_{10}−^{8}C_{4}∗^{11}C_{5}Question 15 |

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?

(n-|A ∪ B|) |A| |B| | |

(|A| ^{2}+|B|^{2})n^{2}
| |

n!(|A∩B|/|A∪B|) | |

Question 15 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

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 16 |

i
| |

i+1
| |

2i | |

2 ^{i} |

Question 16 Explanation:

Put g(i) = i+1

S = 1 + 2x + 3x

^{2}+ 4x

^{3}+ .....

Sx = 1x + 2x

^{2}+ 3x

^{3}+ 4x

^{4}+ ......

S - Sx = 1 + x + x

^{2}+ x

^{3}+ .....

[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 17 |

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?

9 | |

8 | |

7 | |

6 |

Question 17 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

So total no. of pairs that can be coloured = k+

k+

k+k(k-1)/2 ≥ 26

k(k+1)/2 ≥ 26

k(k+1) ≥ 52

k(k+1) ≥ 7*8

k≥7

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}≥ 26k+k(k-1)/2 ≥ 26

k(k+1)/2 ≥ 26

k(k+1) ≥ 52

k(k+1) ≥ 7*8

k≥7

Question 18 |

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

Question 18 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

= 3

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

= 3

^{n}Question 19 |

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?

Question 19 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

. So option (B) is correct

Question 21 |

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

3 | |

8 | |

9 | |

12 |

Question 21 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

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 22 |

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

^{n-1}C_{k} | |

^{n}C_{k} | |

^{n}C_{k+1} | |

None of the above |

Question 22 Explanation:

If n zeros are present then n+1 gaps are possible. So we have to fill (n+1) number of k's.

So, total possible ways is

^{(n+1)}C

_{k}.

Question 23 |

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

1638 | |

2100 | |

2640 | |

None of the above |

Question 23 Explanation:

Formula for distributing n identical objects into r persons is,

So for 10 roses,

For 15 sunflowers,

For 15 daffodils,

∴ The final answer is,

11×16×16 = 2816

^{n+r-1}C_{r-1}So for 10 roses,

^{10+2-1}C_{2-1}=^{11}C_{1}= 11For 15 sunflowers,

^{15+2-1}C_{2-1}=^{16}C_{1}= 16For 15 daffodils,

^{15+2-1}C_{2-1}=^{16}C_{1}= 16∴ The final answer is,

11×16×16 = 2816

Question 24 |

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

2240 | |

2296 | |

2620 | |

4536 |

Question 24 Explanation:

If the last digit is 0 then

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

Total possibilities = 504 + 1792 = 2296

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

Total possibilities = 504 + 1792 = 2296

There are 24 questions to complete.