Combinatorics and Counting PYQs for GATE CS

Solve 7+ Combinatorics and Counting previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Combinatorics and Counting

Orientation Level 1

Chapter Roadmap: Combinatorics and Counting

Step 1 (Current)

Stars and Bars & Integer Partitions

Distributing identical items into distinct or identical bins.

Step 2

String Counting & Complementary Counting

Arrangements with restrictions and total minus unwanted.

Step 3

Permutations & Order Constraints

Assigning distinct tasks with priority or capacity rules.

Step 4

Subset & Binary Matrix Counting

Counting subset pairs and matrices with parity constraints.

Why this order? Stars and Bars teaches you how to handle indistinguishability, the hardest conceptual leap. The rest builds on it by adding order and distinctness.

The Core Intuition: Stars and Bars

Concept Level 1

The Core Intuition: Stars and Bars

Distributing $n$ identical items into $k$ distinct bins.

Visual Model: 5 items, 3 bins

Bin 1: 2 Bin 2: 0 Bin 3: 3

The Logic

Total positions in sequence: $n + k - 1$
Choose positions for bars: $(k - 1 n + k - 1)$
Or choose positions for stars: $(n n + k - 1)$

Key Condition: This standard formula assumes bins can be empty (

x_{i} \geq 0

Combinatorics and Counting: Solved Questions with Step-by-Step Explanations (7 Problems)

Question 1 · Engineering Mathematics · 2026_Set1 MCQ

Consider $4 \times 4$ matrices with their elements from ${0, 1}$ . The number of such matrices with even number of $1$ s in every row and every column is

A.
512
B.
1025
C.
1023
D.
255

Correct Answer:

Step-by-Step Solution

Key idea: This is a binary matrix counting problem with parity constraints, recognizable by the requirement of an "even number of 1s in every row and every column". We solve this by determining the degrees of freedom in the matrix.

Step 1: Consider the top-left $3 \times 3$ submatrix (rows 1-3, columns 1-3). The entries in this submatrix can be chosen completely freely.

Number of ways to fill this $3 \times 3$ block = $2^{3 \times 3} = 2^{9} = 512$ .

Step 2: Determine the remaining cells in the first 3 rows.

For each of the first 3 rows, the entry in the 4th column is uniquely forced to make the row sum even.

Step 3: Determine the remaining cells in the first 3 columns.

For each of the first 3 columns, the entry in the 4th row is uniquely forced to make the column sum even.

Step 4: Determine the bottom-right cell (row 4, column 4).

This cell must satisfy both the 4th row parity and the 4th column parity. In a binary matrix, the sum of all row parities equals the sum of all column parities (both equal the total sum of all elements mod 2). Thus, the two constraints on the bottom-right cell are perfectly consistent, and it is uniquely determined.

Step 5: Calculate the total.

Since all other cells are uniquely determined by the free choices in the $3 \times 3$ submatrix, the total number of valid matrices is exactly 512.

Answer: A

Question 2 · Engineering Mathematics · 2025_Set1 MCQ

A shop has 4 distinct flavors of ice-cream. One can purchase any number of scoops of any flavor. <b>The order in which the scoops are purchased is inconsequential.</b> If one wants to purchase 3 scoops of ice-cream, in how many ways can one make that purchase?

A.
4
B.
20
C.
24
D.
48

Correct Answer:

Step-by-Step Solution

Key idea: This is a Stars and Bars problem, recognizable by the distribution of identical items (scoops of the same flavor are indistinguishable) into distinct categories (the 4 distinct flavors), with the phrase "order is inconsequential" confirming we are choosing a multiset.

Step 1: Identify the parameters for the Stars and Bars formula.

Number of identical items to distribute: $n = 3$ (scoops).

Number of distinct bins: $k = 4$ (flavors).

Step 2: Apply the standard Stars and Bars formula for non-negative integer solutions.

The number of ways is given by $(k - 1 n + k - 1)$ .

Step 3: Substitute the values and calculate.

$(4 - 1 3 + 4 - 1) = (3 6)$ .

$(3 6) = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$ .

Answer: B

Question 3 · Engineering Mathematics · 2025_Set1 NAT

Let $S$ be the set of all ternary strings defined over the alphabet ${a, b, c}$ . Consider all strings in $S$ that contain at least one occurrence of two consecutive symbols, that is, “aa”, “bb” or “cc”. The number of such strings of length 5 that are possible is _______. (Answer in integer)

Correct Answer:

195

Step-by-Step Solution

Key idea: This is a complementary counting problem, recognizable by the phrase "at least one occurrence". Counting the desired strings directly involves messy overlapping cases, so we count the complement (strings with NO consecutive identical symbols) and subtract from the total.

Step 1: Calculate the total number of ternary strings of length 5.

The alphabet is ${a, b, c}$ , so there are 3 choices for each of the 5 positions.

Total strings = $3^{5} = 243$ .

Step 2: Calculate the number of strings with NO consecutive identical symbols.

Position 1: 3 choices (any of a, b, c).
Position 2: 2 choices (must be different from Position 1).
Position 3: 2 choices (must be different from Position 2).
Position 4: 2 choices (must be different from Position 3).
Position 5: 2 choices (must be different from Position 4).

Number of such strings = $3 \times 2 \times 2 \times 2 \times 2 = 3 \times 2^{4} = 48$ .

Step 3: Subtract the complement from the total.

Strings with at least one consecutive pair = Total - Strings with no consecutive pairs

$= 243 - 48 = 195$ .

Answer: 195

Question 4 · Engineering Mathematics · 2023 MCQ

Let

U = {1, 2, \dots, n}

, where

n

is a large positive integer greater than 1000. Let

k

be a positive integer less than

n

. Let

A, B

be subsets of

U

with

∣ A ∣ = ∣ B ∣ = k

and

A \cap B = \emptyset

. 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.
$(2 k n) (n - 2 k)!$
C.
$(2 k n) (n - 2 k)! (k!)^{2}$
D.
$2 (2 k n) (n - 2 k)! (k!)^{2}$

Correct Answer:

Step-by-Step Solution

Key idea: This is a permutation problem with relative order constraints, recognizable by the condition "All members of A appear... before... B". We use the symmetry division technique by focusing on the relative ordering of the specific subsets.

Step 1: Consider the total number of permutations of $U$ , which is $n!$ .

Step 2: Focus only on the $2 k$ elements belonging to $A \cup B$ . In any random permutation of $U$ , these $2 k$ elements can appear in any of their $(2 k)!$ internal relative orders.

Step 3: Count the favorable relative orders.

We need either all of $A$ before all of $B$ , or all of $B$ before all of $A$ .

Case 1 (A before B): The first $k$ positions among the $2 k$ elements must be occupied by $A$ , and the last $k$ by $B$ . The elements of $A$ can be arranged in $k!$ ways, and $B$ in $k!$ ways. Total = $k! \times k! = (k!)^{2}$ .
Case 2 (B before A): By symmetry, this also gives $(k!)^{2}$ ways.

Total favorable relative orders = $2 (k!)^{2}$ .

Step 4: Calculate the fraction of favorable permutations.

The probability of a random permutation having a favorable relative order is $\frac{2 ( k ! ) ^{2}}{( 2 k )!}$ .

Step 5: Multiply by the total permutations.

Favorable permutations = $n! \times \frac{2 ( k ! ) ^{2}}{( 2 k )!}$ .

We can rewrite $n!$ as $\frac{n !}{( 2 k )! ( n - 2 k )!} \times (2 k)! \times (n - 2 k)! = (2 k n) (2 k)! (n - 2 k)!$ .

Substituting this in:

$= (2 k n) (2 k)! (n - 2 k)! \times \frac{2 ( k ! ) ^{2}}{( 2 k )!} = 2 (2 k n) (n - 2 k)! (k!)^{2}$ .

Answer: D

Question 5 · Engineering Mathematics · 2022 NAT

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

Correct Answer:

Step-by-Step Solution

Key idea: This is an integer partition problem, recognizable because both the items (balls) and the bins are identical. We need to find the number of ways to write 6 as a sum of at most 3 non-negative integers, where the order of the summands does not matter.

Step 1: Since the bins are identical, a distribution like (4, 1, 1) is the same as (1, 4, 1). We only care about the multiset of counts. We list the partitions of 6 into at most 3 parts systematically, keeping the parts in non-increasing order: $n_{1} \geq n_{2} \geq n_{3} \geq 0$ .

Step 2: List the partitions by the largest part $n_{1}$ :

If $n_{1} = 6$ : (6, 0, 0) $\to$ 1 way
If $n_{1} = 5$ : (5, 1, 0) $\to$ 1 way
If $n_{1} = 4$ : (4, 2, 0), (4, 1, 1) $\to$ 2 ways
If $n_{1} = 3$ : (3, 3, 0), (3, 2, 1) $\to$ 2 ways
If $n_{1} = 2$ : (2, 2, 2) $\to$ 1 way

Step 3: Sum the number of ways.

Total = 1 + 1 + 2 + 2 + 1 = 7.

Answer: 7

Question 6 · Engineering Mathematics · 2021_Set2 NAT

Let $S$ be a set consisting of 10 elements. The number of tuples of the form $(A, B)$ such that $A$ and $B$ are subsets of $S$ , and $A \subseteq B$ is __________.

Correct Answer:

59049

Step-by-Step Solution

Key idea: This is a subset counting problem using the element-wise independence principle, recognizable by the condition $A \subseteq B \subseteq S$ . Instead of counting subsets globally, we evaluate the choices for each element of $S$ independently.

Step 1: Consider an arbitrary element $x \in S$ . We must decide its membership in $A$ and $B$ .

Step 2: Since $A \subseteq B$ , if $x \in A$ , then $x$ must also be in $B$ .

The valid choices for $x$ are:

$x \in A$ and $x \in B$
$x \in / A$ and $x \in B$
$x \in / A$ and $x \in / B$

The choice $x \in A$ and $x \in / B$ is invalid. Thus, there are exactly 3 valid choices for each element.

Step 3: Since there are 10 elements in $S$ , and each element makes an independent choice from 3 options, the total number of tuples $(A, B)$ is $3^{10}$ .

Step 4: Calculate $3^{10} = 59049$ .

Answer: 59049

Question 7 · Engineering Mathematics · 2021_Set1 NAT

There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that:
- The fastest computer gets the toughest job and the slowest computer gets the easiest job.
- Every computer gets at least one job.
The number of ways in which this can be done is __________.

Correct Answer:

Step-by-Step Solution

Key idea: This is a constrained assignment problem, recognizable by the specific forced allocations (fastest gets toughest, slowest gets easiest) combined with a global "at least one" constraint. We first satisfy the forced assignments, then handle the remaining items using complementary counting for the residual constraint.

Step 1: Identify the forced assignments.

Let the jobs be $J_{1}$ (easiest) to $J_{6}$ (toughest), and computers be $C_{1}$ (fastest), $C_{2}$ (middle), $C_{3}$ (slowest).

$C_{1}$ must get $J_{6}$ .

$C_{3}$ must get $J_{1}$ .

Step 2: Check the "at least one job" constraint.

$C_{1}$ has 1 job ( $J_{6}$ ).

$C_{3}$ has 1 job ( $J_{1}$ ).

$C_{2}$ currently has 0 jobs.

Step 3: Assign the remaining jobs.

The remaining 4 jobs ( $J_{2}, J_{3}, J_{4}, J_{5}$ ) can be assigned to any of the 3 computers.

Total unrestricted ways to assign these 4 jobs = $3^{4} = 81$ .

Step 4: Apply the residual constraint.

$C_{2}$ must get at least one job. We subtract the cases where $C_{2}$ gets NO jobs.

If $C_{2}$ gets no jobs, all 4 remaining jobs must go to either $C_{1}$ or $C_{3}$ .

Ways for this to happen = $2^{4} = 16$ .

Step 5: Calculate the valid assignments.

Valid ways = Total unrestricted - (Ways $C_{2}$ gets no jobs) = $81 - 16 = 65$ .

Answer: 65

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Combinatorics and Counting PYQs for GATE CS

Chapter Roadmap: Combinatorics and Counting

Chapter Roadmap: Combinatorics and Counting

The Core Intuition: Stars and Bars

The Core Intuition: Stars and Bars

Combinatorics and Counting: Solved Questions with Step-by-Step Explanations (7 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit