Computer Science Combinatorics Questions and Answers

Explanation:

(a) T(n) = T(n – 1) + n

T₂ – T_{n – 1} n
For Homogeneous solution:
T_n -T_{n – 1} = 0
t- 1 = 0
t = 1
Therefore, homogenous solution is
T_n = C(1)ⁿ = C
For Particular solution:
Let particular solution be (d₀ + d₁n)n
⇒ (d₀ + d₁n)n – (d₀ + d₁n – 1))(n – 1) = n
⇒ d₀n + d₁n² – d₀n + d₀ – d₁(n – 1)² = n
⇒ d₀n + d₁n² – d₀n + d₀ – d₁(n²– 2n + 1) = n
⇒ d₀ + 2d₁n – d₁ = n
d₀ – d₁ = 0 and 2d₁ = 1
⇒ d₀ = d₁ and d₁ = \(\frac{1}{2}\)
∴ d₀ = d₁ = \(\frac{1}{2}\)
So particular solution is,
\(\left(\frac{1}{2}+\frac{1}{2} n\right)\) × n = \(\frac{n(n+1)}{2}\) = \(\frac{n^{2}+n}{2}\)
So complete solution is,
T(n) C +\(\frac{1}{2}\)n{n +1)
Given, T( 1) = 1
1 = C + \(\frac{1}{2}\) × 1 × (1 + 1)
1 = C+ 1
C= 0
Therefore complete solution of the recurrence relation is T(n) = \(\frac{n(n+1)}{2}\).

(b) The Fibonacci numbers are defined as a₀ = 1, a₁ = 1
a_r = a_{r – 1} + a_{r – 2} r ≥ 2

⇒ A(x) – a₀ – a₁ x = (A(x) – a₀) + x²A(x)
Since, a₀ = 1 and a₁ = 1
⇒ A(x) – 1 – x = x(A(x) – 1) + x²A(x)
⇒ A(x) = \(\frac{1}{1-x-x^{2}}\)

Explanation:
T(n) = T\(\left(\frac{\mathrm{n}}{2}\right)\) + 1
⇒ T(n) – T\(\left(\frac{\mathrm{n}}{2}\right)\) = 1
Let, n = 2^k.
⇒ T(2^k) – T\(\left(\frac{2^{\mathrm{k}}}{2}\right)\) = 1
⇒ T(2^k) – T(2^{k – 1} = 1
Let, T(2^k) – x_k
x_k – x_{k – 1} = 1
For Homogeneous solution:
x_k – x_{k – 1} = 0
t – 1 = 0
t = 1
So homogeneous solution is: x_k = C(1)^k = C
For Particular solution:
Let particular solution be d₁k
d₁k – d₁(k- 1) = 1
⇒ d₁ = 1
Particular solution is k
∴ Complete solution is
x_k = C + k
T(2^k) = C + k
T(n) = C + log₂n
Given, T(1) = 1
⇒ C= 1
∴ Complete solution is: T(n) = log₂n + 1

Explanation:
Let the string be of length 4 : abcd
Number of substrings of length 0=1 (only ε )
Number of substrings of length 1 = 4
a, b, c, d
Number of substrings of length 2 = 3
ab, bc, cd
Number of substrings of length 3 = 2
abc, bcd
Number of substrings of length 4=1
abcd
∴ Total number of substrings = 1 +(4+ 3 + 2 + 1)
= 1 + (Sum of 4 natural number)
= 1 + \(\frac{4 \times(4+1)}{2}\)
= 11
Therefore, total number of substrings (maximum) that can be formed from a character string of
length 1 + \(\frac{n(n+1)}{2}\).

Answer: (a) ⁿ⁺¹C_K
Explanation:
First arranging all n zeros in a row. There is only 1 way for arranging n zeros in a row. By arranging n zeros in a row, we get (n + 1) positions to place ones.
So number of ways arranging k ones in (n + 1) positions = ^{n + 1}C_k
∴ Required number of binary strings of n zeroes and k ones that no two ones are adjacent = 1 × ^{n + 1}C_k = ^{n + 1}C_k.

Answer: (d) \(\frac{n(n+1)}{2}\)
Explanation:
For a string of length n:
The number of substrings of length 1 = n
The number of substrings of length 2 = n – 1
The number of substrings of length 3 = n – 2 and so on…
The number of substrings of length n is 1 So total number of substrings ; = n + (n-1) + …+1
= Sum of n natural numbers.
= \(\frac{\mathrm{n}(\mathrm{n}+1)}{2}\)

Answer: (d) 6
Explanation:
E : Persons speaks English
H : Persons speaks Hindi
K : Persons speaks Kannada
Assume that everyone in the room speaks at least one of the languages.
Given, n(E ∪ H ∪ K) = 28
n(E) = 18
n(H) =15
n(K) = 22
n(E ∩ H) = 9
n(H ∩ K) = 11
n(K ∩ E) = 13
n(K ∩ E ∩ H) = ?
By principle of inclusion and exclusion
n(E ∪ H ∪ K) = n(E) + n(H) + n(K) – n(E ∩ H) – n(H ∩ E) – n(K ∩ E) + n(K ∩ E ∩ H)
28 = 18 + 15 + 22 – 9 – 11 – 13 + n(K ∩ E ∩ H) n(k ∩ E ∩ H) = 28 – 55 + 33 = 61 – 55 = 6
Therefore, the number of people who speak all three languages are 6.

Explanation:
x_n = 2x_{n – 1} – 1
For Homogeneous solution:
x_n = 2x_{n – 1} = 0
t – 2 = 0
t= 2
So homogeneous solution is
x_n = C(2)ⁿ
For Particular solution:
Let particular solution be d_o.
d₀ = 2d₀ – 1
d₀ = 1
So particular solution is 1
∴ Complete solution = Homogeneous solution + Particular solution
Complete solution = C(2)ⁿ + 1
⇒ x_n = C(2)ⁿ + 1
Given initial condition is x₁ = 2
2 = C(2)¹ + 1
1 = 2C
C = \(\frac { 1 }{ 2 }\)
x_n = \(\frac { 1 }{ 2 }\)(2)ⁿ + 1
∴ x_n = 2^{n – 1} + 1

Answer: (c) 2640
Explanation:
Number of ways for distributing r similar things among n different things = ^{(n – 1 + r)}C_r
The number of ways for distributing 10 roses among the two girls = ^{(2 – 1 + 10)}C₁₀ =11.
Similarly number of ways for distributing 15 sunflowers among two girls = ^{(2 – 1 + 15)}C₁₅
= ¹⁶C₁₅ = ¹⁶C₁ = 16
Number of ways for distributing 14 daffodils among the two girls = ^{(2 – 1 + 14)}C₁₄ = ¹⁵C₁₄ = ¹⁵C₁ =15
∴ Total number of ways = 11 × 16 × 15 = 2640

Answer: (c) 9
Explanation:
Let the number of cards to be dealt from an arbitrarily shuffled deck of 52 cards be n.
Number of suits = 4
Required number of cards from the same suit = 3.
So by the pigeonhole principle

So the minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from the same suit is 9.

Answer: (b) 2296
Explanation:
The digits are given to be distinct i.e. no repetition. 4 digit even numbers cannot start with 0 and must end with 0, 2, 4, 6 or 8.
Since there is a condition for 0 in starting as well as ending we will count the even numbers ending with 0 separately.
So the total number of 4 digits even number = 4 digit even numbers ending with zero + 4 digit even numbers ending with 2, 4, 6, 8.
4 digit even numbers ending with 0

4 digit even numbers ending with 2, 4, 6, 8

So the total number of 4 digit even numbers = 504+1792 = 2296.

Answer: (b) \(\frac{\left(3^{\mathrm{k}+1}-1\right)}{2}\)
Explanation:
T(2^k) = 3T(2^{k – 1}) + 1
Let, T(2^k) = x_n
⇒ x_n = 3x_{n – 1} + 1
⇒ x_n – 3x_{n – 1} = 1
So for Homogenous solution
x_n – 3x_{n – 1} = 0
n – 3 = 0
n = 3
Homogenous solution is
x_n = C₁(3)ⁿ
T(2^k) = C₁(3)^k
For Particular solution
Let d be the particular solution
d – 3d = 1
2d = -1
d = \(-\frac{1}{2}\)
Therefore, the complete solution is
T(2^k) = C₁(3)^k \(-\frac{1}{2}\)
Given T(1) = 1
1 = C₁(3)⁰ \(-\frac{1}{2}\)
1 = C₁ \(-\frac{1}{2}\)
C₁ = \(\frac { 3 }{ 2 }\)
So the complete solution is
T(2^k) = C₁ (3)^k \(-\frac{1}{2}\)
Given, T(1) = 1
1 = C₁(3)⁰ \(-\frac{1}{2}\)
1 = C₁ \(-\frac{1}{2}\)
C₁ = \(\frac { 3 }{ 2 }\)
So the complete solution is
T(2^k) = \(\frac { 3 }{ 2 }\)(3)^k \(-\frac{1}{2}\)
T(2^k) = \(\frac{3^{\mathrm{k}+1}-1}{2}\)

Answer: (d) n – 2\(\left[\frac{n}{2}\right\rfloor\)+2
Explanation:
The minimum number of colors required to color the vertices of a cycle with n nodes = 2, when n is even = 3, when n is odd
Therefore n – 2 \(\left\lfloor\frac{\mathrm{n}}{2}\right\rfloor\) +2 gives 2 when n is even. and 3 when n is odd.

Answer: (c) 56
Explanation:
This corresponds to an ordered partition of 8 elements into two groups, the first with 5 elements and second with 3 elements. The number of ways of doing this is p(8; 5, 3) = \(\frac{8 !}{5 ! 3 !}\) = 56

Answer: (b) 3ⁿ
Explanation:
For each of the n couples invited to the party one of three things is possible:
1. Both husband and wife attend the party.
2. Wife only attends the party.
3. Neither husband nor wife attends the party. Since there are n such couples, a total number of possibilities = 3ⁿ.

Answer: (d) 6
Explanation:
The problem reduces to finding how many distinct ordered color pairs (C₁, C₂) are possible with k colors.
Since the first color C₁ can be any one of the k colors and the second color C₂ also can be any one of the k colors (both prints of a letter can be colored with the same color), the total no. of such order color pairs is equal to k × k = k₂.
Since each pair of letters must be colored with different color pairs, at least 26 color pairs are required to do this.
Therefore the requirement is k² ≥ 26.
The minimum value of k that satisfies this equation is k = 6.

Answer: (a) 44
Explanation:
We want every one of the 5 balls to be in the wrong box. This is nothing but the number of derangements of a set of 5 elements = D₅. i.e. we need to compute D₅

Answer: (d) p(p – 1)(q – 1)
Explanation:
The number of numbers from 1 to n, which are relatively prime to n i.e., gcd (m, n) = 1, is given by the Euler Totient function Φ(n). If n is broken down into its prime factors as n = p₁^n₁ . p₂^n₂ ……
where p₁,p₂ etc. are distinct prime numbers, then

Φ(n) = Φ( p₁^n₁) Φ(p₂^n₂)
Here, n = p² q
So, Φ(n) = Φ(p²) × Φ(q)
Now, using the property Φ(p^k) = p^k – p^{k – 1}
Φ(p²) = p² – p¹ = p² – p and
Φ(q) = q¹ – q⁰ = q – 1
Substituting these in eq. (i), we get
Φ(n) = (p² – p) (q – 1)
= p(p – 1) (q – 1)

Answer: (c) 16
Explanation:
The number of combinations of pairs (a mod 3, b mod 5) is 3 × 5 = 15 (since a mod 3 can be 0, 1, or 2) and b mod 5 can be 0, 1, 2, 3 or 4)
∴ If 16 different ordered pairs are chosen at least 2 of them must have (a mod 3, b mod 5) as same (basic pigeon hole principle).
Let such two pairs be (a, b) and (c, d) then
a mod 3 ≡ c mod 3 ⇒ a ≡ c mod 3, and b mod 5 ≡ d mod 5 ⇒ b ≡ d mod 5

Answer: (b) i + 1
Explanation:

Answer:
(a) \(\left(\begin{array}{c}
2 n \\
\mathrm{n}
\end{array}\right) / 4^{\mathrm{n}}\)
Explanation:
The probability that exactly n elements are chosen = The probability of getting n heads out of 2n tosses
= ²ⁿC_n (1/2)ⁿ (1/2)^{2n – n}(Binomial formula)
= ²ⁿC_n (1/2)ⁿ (1/2)ⁿ
= \(\frac{{ }^{2 \mathrm{n}} \mathrm{C}_{\mathrm{n}}}{2^{2 \mathrm{n}}}\) = \(\frac{{ }^{2 n} \mathrm{C}_{\mathrm{n}}}{\left(2^{2}\right)^{\mathrm{n}}}\) = \(\frac{{ }^{2 \mathrm{n}} \mathrm{C}_{\mathrm{n}}}{4^{\mathrm{n}}}\)

Answer:
(a) \(\left(\begin{array}{l}
20 \\
10
\end{array}\right)\)
Explanation:
Consider the following diagram:

The robot can move only right or up as defined in the problem. Let us denote the right move by ‘R’ and the up move by ‘U’. Now to reach (3, 3) from (0, 0), the robot has to make exactly 3 ‘R’ moves and 3 ‘U’ moves in any order. Similarly to reach (10, 10) from (0, 0), the robot has to make 10 ‘R’ moves and 10 ‘U’ moves in any order. The number of ways this can be done is the same as the number of permutations of a word consisting of 10 ‘R’s and 10 ‘U’s.
Applying formula of permutation with limited repetitions we get the answer as \(\frac{20 !}{10 ! 10 !}\) = ²⁰C₁₀.

Answer:
Explanation:
The robot can reach (4, 4) from (0,0) in ⁸C₄ ways as argued in the previous problem. Now after reaching (4,4), the robot is not allowed to go to (5,4). Let us count how many paths are there from (0,0) to (10, 10) if the robot goes from (4, 4) to (5, 4) and then we can subtract this from a total number of ways to get the answer.
Now there are 8C₄ ways for robot to reach (4, 4) from (0, 0) and then robot takes the ‘U’ move from (4, 4) to (5, 4). Now from (5, 4) to (10, 10) the robot has to make 5 ‘U’ moves and 6 ‘R’ moves
in any order which can be done in \(\frac{11 !}{5 ! 6 !}\) ways = ¹¹C₅ ways.

∴ The number of ways robot can move from (0,0) (10, 10) via (4, 4) – (5, 4) move is
⁸C₄ × ¹¹C₅ = \(\left(\begin{array}{l}
8 \\
4
\end{array}\right)\) × \(\left(\begin{array}{c}
11 \\
5
\end{array}\right)\)

∴ Number of ways robot can move from (0,0) to (10, 10) without using (4, 4) to (5, 4) move is

\(\left(\begin{array}{l}
20 \\
10
\end{array}\right)\) – \(\left(\begin{array}{l}
8 \\
4
\end{array}\right)\) x \(\left(\begin{array}{l}
11 \\
5
\end{array}\right)\) ways.
Which is an option (d).

Answer:
Common Data for Q.24 & Q.25
Let x_n denote the number of binary strings of length n that contain no consecutive 0s.
Explanation:
P = Σ i = 1 + 3 + 5 + 7 + … + (2k – 1)
1 ≤ i ≤ 2k, i is odd
Q= Σ i=2+4+ 6+…2k, 1 < i < 2k, 1 ≤ i ≤ 2k, i is even.
P is in A.P with a = 1, d = 2 and n = k
Q is in A.P with a = 2, d = 2 and n = k

Answer: (d) x_n = x_{n – 1} + x_{n – 2}
Explanation:
The ✓ represents those strings with no consecutive 0’s.

Now, substituting n = 3 in all of the answers only choice (d) x_n = x_{n – 1} + x_{n – 2} satisfies the numbers obtained from the tree counting.

Answer: (d) 13
Explanation:
x₁ = 2
x₂ = 3
⇒ x₃ = x₁ + x₂ = 2 + 3 = 5
⇒ x₄ = ₂ + x₃ = 3 + 5 = 8
⇒ x₅ = ₃ + x₄ = 5 + 8 = 13
So option (d) is correct.

Answer: (c) 29
Explanation:
In 300!, distinct numbers divisible by 11 = \(\left[\frac{300}{11}\right\rfloor\) = 27.
Since these 27 numbers contain, the same number which can be further divisible by 11 i.e.
\(\left[\frac{27}{11}\right\rfloor\) = 2(121 and 242)
So, total number of 11’s = 27 + 2 = 29 Hence exponent of 11 is 29.

Answer: (a) \(\frac{(n+b-1) !(n+r-1) !}{(n-1) ! b !(n-1) ! r !}\)
Explanation:
A number of ways to distribute ‘b’ blue balls in n distinct boxes:

Since each box can contain 0 to n blue balls, so number of ways
= ^{( n + b – 1)}C_{(n – 1)}
=\(\frac{(n+b-1) !}{(n-1) ! \times b !}\)

Number of ways to distribute ‘r’ red balls in n distinct boxes:

Since each box can contain 0 to n red balls. So number of ways = ^{( n + r – 1)}C_{(n – 1)}

=\(\frac{(n+r-1) !}{(n-1) ! \times r !}\)

Since both are independent of each other So total ways = Number of ways to distribute ‘b’ blue balls x Number of ways to distribute ‘r’ red balls

= \(\frac{(n+b-1) !(n+r-1) !}{(n-1) ! \times b !(n-1) ! \times r !}\)

Explanation:
In a 10-pennant let there we x₁ ones and x₂ twos. So we need to find all the solutions of
x₁ + 2x₂ = 10

put, x₁ = 0 ⇒ x₂ = \(\frac { 10 }{ 2 }\) = 5

So, (0, 5) is a solution i.e. a 10-pennant could have 0 ones and 5 twos. The number of ordered permutations of 0 ones and 5 twos = 5!/ 5! = 1

Now x₁ cannot be 1 since in that case x₂ = \(\frac { 10 }{ 2 }\) = 4.5
(is not an integer).

put, x₁ = 2 ⇒ x₂ = \(\frac { 8 }{ 2 }\) = 4

So, (2, 4) is a solution i.e. a 10-pennant could have 2 ones and 4 twos. The number of ordered permutations of 2 ones and 4 twos

\(\frac{6 !}{2 ! 4 !}\) = 15

Similarly (4, 3), (6, 2), (8, 1) and (10,0) are the other four solutions and the number of pennants for each is respectively

\(\frac{7 !}{4 ! 3 !}\) = 35, \(\frac{8 !}{6 ! 2 !}\) =28, \(\frac{9 !}{8 ! 1 !}\) = 9, \(\frac{10 !}{10 ! 10 !}\) = 1 = 89

So the total number of 10-pennants = 1 + 15 + 35 + 28 + 9 + 1 = 89

Explanation:
“The quick brown fox jumps over the lazy dog” (3) (5) (5) (3) (5) (4) (3) (4) (3)
Now let x be the number of letters in the word that is randomly picked.
Now, we make a probability distribution table for x

From this table we can easily find the expected value of x.

E(x) = Σx p(x)
= 3 × \(\frac { 4 }{ 9 }\) + 4 × \(\frac { 2 }{ 9 }\) + 5 × \(\frac { 3 }{ 9 }\) = \(\frac { 35 }{ 9 }\) = 3.88 = 3.9
(after rounding to one decimal accuracy).

Explanation:
Factorizing 2014 in primes by successively dividing by primes, we get
2014 = 2¹ × 19¹ × 53¹
Now We use the formula:
If n = p₁^n₁ . p₂^n₂…..p_r^n_r is the prime factorization of n, then the number of distit factors of n is given by (n₁ + 1) × (n₂ + 1) …….. (n_r + 1).
Now since 2014 = 2¹ × 19¹ × 53¹, the number of distinct factors of 2014 = (1 + 1) (1 + 1) (1 + 1) = 2 × 2 × 2 = 8

Explanation:

= 1 – \(\frac { 1 }{ 100 }\) (all the terms in above series except the first and last terms cancels out)
= \(\frac { 99 }{ 100 }\) = 0.99

Answer: (a) a_{n -2} + a_{n – 1} + 2^{n – 2}
Explanation:
a₁ = 0 [n0 strings of length 1 contain two consecutive 1’s]
a₂ = 1 [∴ strings = 11]
a₃ = 3 [∴ strings are : 011, 110, 111]
a₄ = 8 [∴ strings are : 0011, 0110, 0111, 1011, 1100, 1101, 1110, 1111]

Option (a):
a_n = a_{n – 2} + a_{n – 1} + 2^{n – 2}
⇒ a₄ = a_{4 – 2} + a_{4 – 1} + 2^{4 – 2}
= a₂ + a₃ + 2²
= 1 + 3 + 4 = 8 which is true.

Option (b):
a_n = a_{n – 2} + 2a_{n – 1} + 2^{n – 2}
⇒ a₄ = a₂ + 2a₃ + 2²
= 1 + 2 × 3 + 4 = 11 which is False.

Option (c):
a_n = 2a_{n – 2} + a_{n – 1} + 2^{n – 2}
⇒ a₄ = 2a₂ + a₃ + 2²
= 2 × 1 + 3 + 4 = 9 which is false.

Option (d):
a_n = 2a_{n – 2} + 2a_{n – 1} + 2^{n – 2}
⇒ a₄ = 2a₂ + 2a₃ + 2²
= 2 × 1 + 2 × 3 + 4 = 12 which is false.

∴ Option (a) : a_n = a_{n – 2} + a_{n – 1} + 2^{n – 2} is correct.

Explanation:
Dividing 2100 successively by prime numbers, we get that, the prime factors of 2100 are 2 × 2 × 3 × 5 × 5 × 7
⇒ 2² × 3¹ × 5² × 7¹
If N = p^k₁ × q^k₂ × r^k₃…… × y^k_n
then the number of factors of N are (k₁+1) (k₂+1) … (k_n+1)
∴ For 2100 we have (2 + 1) (1 + 1) (2 + 1) (1 + 1) = 36 factors.

Explanation:
To satisfy the non-decreasing order condition allow 1, 2, 3 after 1, allow only 2, 3 after 2 and allow only 3 after 3. The following tree diagram gives all the allowed numbers satisfying the given condition.

All the tick-marked numbers satisfy the non-decreasing order condition.
⇒ A number of 4-digit numbers = Number of tick marks = 15.

Answer: (d) a_n = 2a_{n – 1} + 2a_{n – 2}
Explanation:
Let a_n be the number of n-bit strings that do not contain two consecutive 1’s. we wish to develop a recurrence relation for a_n.
Consider 1 bit strings 0, 1 So, a₁ = 2
Consider 2 bit strings 00, 01, 10, 11
Out of minimum only 00, 01, 10 do not contain two consecutive 1’s.
So, a₂ = 3

Out of minimum six strings only 000, 001, 010, 100 and 101 five strings satisfy do not contain two consecutive 1’s. So, a₃ = 5. Three numbers a₁, a₂, a₃ satisfy clearly only (b) a_n = a_{n – 1} + a_{n – 2} is correct.

Explanation:
We wish to find coefficient of x¹² in (x³ + x⁴ + x⁵ +…)³

Now to make x¹² we need to put r = 3 So coefficient of x¹² is ^{3 + 2}C₃ = ⁵C₃ = ⁵C₂ = 10

Explanation:
Given, a_n = 6n² + 2 n + a_{n – 1} and a₁ = 8
We wish to find a₉₉
Now,
a₂ = 6 × 2₂ + 2 × 2 + a₁
a₃ = 6 × 3₂ + 2 × 3 + a₂
= 6 × 3₂ + 2 × 3 + 6 × 2₂ + 2 × 2 + a₁………
a₉₉ = 6 × 99₂ + 2 × 99 + 6 × 98² + 2 + 98 ….
…. + 6 × 2² + 2 × 2 + a₁
Since,
a₁ = 8
a₉₉ = 6 × 99² + 2 × 99 + 6 × 98² + 2 × 98…….
……+ 6 × 22 + 2 × 2 + 8
= 6 × 99² + 2 × 99 + 6 × 98² + 2 × 98…
…6 × 2² + 2 × 2 + 6 × 1² + 2 × 1
= 6(1²+2²+3²… 99²)+ 2.(1 + 2 + 3…99)
= 6. \(\frac{(99(99+1)(2 \times 99+1))}{6}\) + 2 \(\left(\frac{99(99+1)}{2}\right)\)
= 99 × 100 × 199 + 99 × 100
= 100 × 99 (199 + 1) = 100 × 99 × 200
= 2 × 99 × 10⁴ = 198 × 10⁴
So if a₉₉ = K × 10⁴ then K = 198.

Explanation:
Given that generating function:

Now we read to find a₀ and ₃ which are nothing but the coefficient of x⁰ and x³ respectively.
a₀ = coefficient x⁰ = ^{(0 + 2)}C₂ = ²C₂ = 1
a₃ = coefficient x³ = ^{(3 + 2)}C₂ = ^{(2 + 2)}C₂
= ⁵C₂ + ⁴C₂ = 16
So, a₃ – a₀ = 16 – 1 = 15

Answer: (d) \(\frac{3-x}{(1-x)^{2}}\)
Explanation:
Given, a_n = 2n + 3
Since generating function for 1 is \(\frac{1}{1-x}\) and n is \(\frac{x}{(1-x)^{2}}\), the generating function for a_n is
A(x) = \(\frac{2 x}{(1-x)^{2}}\) + \(\frac{3}{1-x}\)
= \(\frac{2 x+3(1-x)}{(1-x)^{2}}\) = \(\frac{3-x}{(1-x)^{2}}\)
which is option (d).

Answer: (a) Both I and II
Explanation:
A – {(x, X), x ∈ X and X ⊆ U}
The number of k element subsets of a set U with n elements = \(\begin{aligned}
&n \\
&k
\end{aligned}\) = ⁿC_k
The number of possible ordered pairs (x, X) where x ∈ X is k. ⁿC_k for a given value of k from 1 to n.
So total number of ordered pairs in A

So II is correct, (Note that k = 0 is excluded since the empty set has no elements and cannot form an ordered pair such as (x, X)).
But since by the combinational identity

So I am also correct.
So both I and II are correct.

Explanation:
Since both L’s are indistinguishable.
First L’s can be arranged in 3 positions 2, 3, or 5 in ³C₂ = 3 ways as follows:
_ L _ L _
or _ L _ _ L
or _ _ _ L L
Now the letters I, A, C can be deranged in 2 x 2! ways. Example in _ L _ L _. C cannot occupy 5^th position, so only 2 ways.
The remaining I and A can be arranged in the remaining 2 positions in 2! ways = 2 ways.
So answer is 3 × 2 × 2! = 12.

Explanation:
Let computers be A, B, and C
The toughest job assigned to the fastest computer (Say, A) is 1 way.
The easiest job assigned to the shortest computer (Say, B) is 1 way.
The remaining 4 jobs are to be assigned to 3 computers so that computer C gets at least one job since A and B have already been assigned a job.
A number of ways 4 jobs assigned to 3 computers = 3⁴.
The number of ways 4 jobs assigned to 3 computers so that computer C does not get any job = 2⁴. Required number of ways = 3⁴ – 2⁴ = 81 – 16 = 65 ways