Advanced Counting Theorems Questions with Solutions: 10 Worked Problems

Choose the counting model before reaching for a formula. Solve six MCQs and four numerical-answer questions, with worked explanations of overlaps, initial conditions and identical objects.

KnowledgeGate Team

Exam prep & CS education

Updated 6 Nov 20268 min read
Advanced Counting Theorems Questions with Solutions: 10 Worked Problems

Advanced counting becomes manageable when you identify what is being counted: forbidden assignments, valid strings, coefficients or unordered arrangements. Some questions offer options, while others require a numerical answer without cues. Attempt each problem before reading its solution.

Choose the counting model before calculating

Pigeonhole proves that a collision is forced. Inclusion-exclusion removes bad cases while correcting their overlaps. Recurrences split an object into smaller valid objects, and generating functions collect counts by total size.

Before calculating, ask whether objects and containers are labelled, whether repetition is allowed, and whether order changes an outcome. The strings 112 and 121 are different, but they represent the same multiset of digits. That distinction decides whether a factorial belongs in your answer.

Pigeonhole and inclusion-exclusion: two different jobs

Q1. Residue classes (MCQ)

What is the minimum number of ordered pairs of non-negative integers that should be chosen to ensure that there are two pairs (a, b) and (c, d) in the chosen set such that a and c have the same remainder modulo 3 and b and d have the same remainder modulo 5?

  • (a) 4

  • (b) 6

  • (c) 16

  • (d) 24

Answer: (c), 16. There are three possibilities for the first remainder and five for the second. Thus there are 3 x 5 = 15 remainder-pair boxes.

The set {(r, s): 0 <= r <= 2, 0 <= s <= 4} has 15 pairs, all in different boxes. So 15 does not guarantee a collision, but the sixteenth pair must share a box.

Check the residue-class solved question after your attempt.

Q2. Forbidden shirt assignments (MCQ)

Arun, Gulab, Neel and Shweta must choose one shirt each from a pile of four shirts coloured red, pink, blue and white respectively. Arun dislikes the colour red and Shweta dislikes the colour white. Gulab and Neel like all the colours. In how many different ways can they choose the shirts so that no one has a shirt with a colour he or she dislikes?

  • (a) 21

  • (b) 18

  • (c) 16

  • (d) 14

Answer: (d), 14. Start with 4! = 24 assignments. Arun wearing red accounts for 3! = 6; Shweta wearing white accounts for another six.

Assignments violating both restrictions number 2! = 2. Subtracting both bad sets removes these twice, so add them back once: 24 - 6 - 6 + 2 = 14. Gulab and Neel have no colour restriction.

Read Pigeonhole & Inclusion-Exclusion: 2 GATE Problems Solved.

Recurrences: strings, Lucas numbers and pennants

These three questions share a recurrence shape. Their starting values make them different sequences.

Q3. Binary strings without consecutive ones (MCQ)

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) a(n) = a(n-1) + 2a(n-2)

  • (b) a(n) = a(n-1) + a(n-2)

  • (c) a(n) = 2a(n-1) + a(n-2)

  • (d) a(n) = 2a(n-1) + 2a(n-2)

Answer: (b). For n >= 2, a valid string ends either in 0 or in 01. Removing that suffix leaves any valid string of length n-1 or n-2, respectively. The cases are disjoint and exhaustive.

Therefore a(n) = a(n-1) + a(n-2), with a(0) = 1 for the empty string and a(1) = 2 for 0 and 1. Then a(2) = 3, a(3) = 5, and a(4) = 8.

Check the binary-string recurrence solution after your attempt.

Q4. Lucas sequence (MCQ)

The Lucas sequence L_n is defined by the recurrence relation:

L_n = L_(n-1) + L_(n-2), for n >= 3,

with L_1 = 1 and L_2 = 3.

Which one of the options given is TRUE?

  • (a) L_n = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n

  • (b) L_n = ((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/3)^n

  • (c) L_n = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/3)^n

  • (d) L_n = ((1 + sqrt(5))/2)^n - ((1 - sqrt(5))/2)^n

Answer: (a). Substituting a trial term r^n gives r^2 - r - 1 = 0. Its roots are alpha = (1 + sqrt(5))/2 and beta = (1 - sqrt(5))/2.

Both root powers obey the recurrence, so their sum does too. Also alpha + beta = 1 and alpha * beta = -1, giving alpha^2 + beta^2 = (alpha + beta)^2 - 2 alpha beta = 3. These match both starting values, establishing L_n = alpha^n + beta^n. The next terms are L_3 = 3 + 1 = 4 and L_4 = 4 + 3 = 7.

Q5. Pennants with a fixed sum (numerical answer)

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

Answer: 89. Let p(0) = 1 represent the empty continuation and p(1) = 1. A final 1 leaves sum n-1; a final 2 leaves sum n-2. Hence p(n) = p(n-1) + p(n-2) for n >= 2.

For sums 1 through 10, the counts are 1, 2, 3, 5, 8, 13, 21, 34, 55, 89. Order matters here: (1,2) and (2,1) remain separate pennants.

Generating functions: read the required coefficient

Check the first few coefficients before trusting a generating function.

Q6. Odd-index corrections (MCQ)

Which of the following is the closed form of the ordinary generating function G(x) = sum a(n)x^n for n from 0 to infinity, for the sequence a(n) defined by a(n) = n + 1 when n is odd, and a(n) = 1 otherwise?

  • (a) x(1 + x^2)/(1 - x^2)^2 + 1/(1 - x)

  • (b) x(3 - x^2)/(1 - x^2)^2 + 1/(1 - x)

  • (c) 2x/(1 - x^2)^2 + 1/(1 - x)

  • (d) x/(1 - x^2)^2 + 1/(1 - x)

Answer: (a). Begin with 1/(1-x), which supplies coefficient 1 everywhere. At an odd index n = 2k+1, the required coefficient is n+1, so the extra amount is n = 2k+1.

Using the sum (2k+1)t^k for k from 0 to infinity, which equals (1+t)/(1-t)^2, the correction is x(1+x^2)/(1-x^2)^2. Add this to the baseline to obtain option (a).

The resulting coefficients start 1, 2, 1, 4, 1, 6. Option (c) instead gives odd-index coefficients 3, 5, 7 because it adds one too many at every odd index.

Check the generating-function solved question after your attempt.

Q7. Shift the minimum exponent (numerical answer)

The coefficient of x^12 in (x^3 + x^4 + x^5 + x^6 + ...)^3 is ________.

Answer: 10. Each factor is x^3/(1-x), so the cube is x^9/(1-x)^3. We need the coefficient of x^3 in (1-x)^(-3), which is C(5, 2) = 10.

Equivalently, write the three chosen exponents as 3+y1, 3+y2 and 3+y3. Their sum is 12 exactly when y1+y2+y3 = 3, with all yi non-negative. Stars and bars gives the same ten choices.

Separate two sets without forcing contiguous blocks

Q8. Relative order of disjoint sets (MCQ)

Let U = {1, 2, ..., n}, where n is a large positive integer greater than 1000. Let k be a positive integer less than n. Let A and B be subsets of U with |A| = |B| = k and A intersection B = empty set. We say that a permutation of U separates A from B if one of the following is true.

  • All members of A appear in the permutation before any of the members of B.

  • All members of B appear in the permutation before any of the members of A.

How many permutations of U separate A from B?

  • (a) n!

  • (b) C(n, 2k) (n-2k)!

  • (c) C(n, 2k) (n-2k)! (k!)^2

  • (d) 2 C(n, 2k) (n-2k)! (k!)^2

Answer: (d). Choose the 2k positions occupied by A union B in C(n, 2k) ways. Choose which set occupies the first k selected positions: two choices. Arrange the members within each set in k! ways and the remaining elements in (n-2k)! ways.

Multiplication gives 2 C(n, 2k) (n-2k)! (k!)^2. Elements outside A union B can appear between selected positions, so contiguous blocks are unnecessary.

For n = 1002 and k = 2, the fraction of all permutations is 2(2!)^2/4! = 8/24 = 1/3. The count is therefore 1002!/3.

Review position selection and ordering in Permutations and Combinations for GATE CS: One Method.

Repetition and identical bins: decide what is distinguishable

Q9. Non-decreasing digits (numerical answer)

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

Answer: 15. Let c1, c2 and c3 count appearances of digits 1, 2 and 3. Then c1+c2+c3 = 4, with each count non-negative. Stars and bars gives C(4+3-1, 3-1) = C(6, 2) = 15.

Each count triple determines exactly one sorted number. For example, (2,1,1) gives 1123 only. Multiplying by 4! would count arrangements that violate the required order.

Q10. Identical balls and bins (numerical answer)

Seven rows show the partitions of six identical balls among three identical bins.

The number of arrangements of six identical balls in three identical bins is______.

Answer: 7. Empty bins are allowed. Because the bins are identical, record occupancies in non-increasing order to count each arrangement once:

(6,0,0), (5,1,0), (4,2,0), (4,1,1), (3,3,0), (3,2,1), (2,2,2).

These are the seven partitions of six into at most three parts. For labelled bins, stars and bars would give C(8,2) = 28. Dividing 28 by 3! does not fix the distinction: (6,0,0) has three distinct reorderings, (3,2,1) has six, and (2,2,2) has one. There is no common divisor for all arrangements.

Seven occupancy rows show partitions of six identical balls across three identical bins, from (6,0,0) through (2,2,2), with row rotations equivalent.

Review the error, then choose the next practice step

Answer recap: Q1 (c); Q2 (d); Q3 (b); Q4 (a); Q5 89; Q6 (a); Q7 10; Q8 (d); Q9 15; Q10 7.

Classify each mistake: wrong model, missed overlap, wrong initial condition or mistaken distinguishability. Redo Q2 and Q10 without notes, explaining why the overlap correction works in one and equal-size division fails in the other.

For structured preparation, explore GATE Guidance by Sanchit Sir. Compare GATE preparation courses.