## Combinatorics

Question 1 |

_{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 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 |

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)} |

_{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 |

^{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! = 10

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

_{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))/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 a

_{99}= k×10

^{4}

a

_{99}= 2(99)(100)

^{2}= 198 × 10

^{4}

∴k = 198

Question 7 |

36 | |

37 | |

38 | |

39 |

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

15 | |

16 | |

17 | |

18 |

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 |

89 | |

90 | |

91 | |

92 |

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 |

0.26 | |

0.27 | |

8 | |

0.29 |

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

27 | |

28 | |

29 | |

30 |

Question 12 |

Question 13 |

2 ^{20}
| |

2 ^{10} | |

None of the above |

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

2 ^{9} | |

2 ^{19} | |

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

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

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

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

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

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 |

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

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 |

. So option (B) is correct

Question 21 |

3 | |

8 | |

9 | |

12 |

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 |

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

^{n}C_{k} | |

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

None of the above |

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+1}C

_{k}

Question 23 |

1638 | |

2100 | |

2640 | |

None of the above |

^{n+r-1}C

_{r-1}

So for 10 roses,

^{10+2-1}C

_{2-1}=

^{11}C

_{1}= 11

For 15 sunflowers,

^{15+2-1}C

_{2-1}=

^{16}C

_{1}= 16

For 15 daffodils,

^{15+2-1}C

_{2-1}=

^{16}C

_{1}= 16

∴ The final answer is,

11×16×16 = 2816

Question 24 |

2240 | |

2296 | |

2620 | |

4536 |

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

Total possibilities = 504 + 1792 = 2296