chapter

Combinatorial Counting and Bijections Notes for GATE DA

Combinatorial Counting and Bijections notes for GATE DA: 11 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

combinatorial counting and bijections notes

Chapter Roadmap: Combinatorial Counting and Bijections

Chapter Roadmap Combinatorial Counting and Bijections Topic 1: Digit-Based Counting Forming numbers from restricted sets using divisibility rules (mod 3/9). Topic 2: Bijections & Involutions Counting self-inverse mappings f (f (n)) = n . Goal: Master modular arithmetic for filtering combinations and permutation adjustments for leading zeros.

The Core Idea: Divisibility by 3

The Core Idea: Divisibility by 3 Number is divisible by 3 ⟺ Sum of digits is divisible by 3 This rule allows us to ignore digit positions initially. We only care about which combination of digits sums to a multiple of 3. Digits {1, 3, 4, 7} \to Sum 1 + 3 + 4 + 7 = 15

Step-by-Step Method for Digit Counting

Step-by-Step Method Categorize by Remainder: R_{0} : 0, 3, 6, 9 R_{1} : 1, 4, 7 R_{2} : 2, 5, 8 Select Valid Combinations: Ensure sum of remainders \equiv 0 (mod 3) . Permute & Adjust: Calculate n! . If 0 is present, subtract cases starting with 0. Valid = Total Perms - Starts with 0

8 more cards in this chapter

Try a question

Answer it here to see how it works. Nothing is recorded until you sign in.

Question 1

Level 1: Warm-up

Which of the following sets of three digits has a sum that is exactly divisible by 3?

Question 2

Level 1: Warm-up

When forming 4-digit numbers from a selected set of 4 distinct digits that includes 0, which of the following correctly describes the adjustment needed for the total permutations?

Question 3

Level 1: Warm-up

Which of the following 4-digit numbers is divisible by 3?

Question 4

Level 1: Warm-up

Consider the formation of 4-digit numbers from the set {0, 2, 4, 6}. Which of the following statements correctly bounds the number of valid 4-digit numbers?

Question 5

Level 1: Warm-up

Consider the following statements regarding the recurrence relation for counting involutions. \textbf{Assertion (A):} The term accounts for the cases where the -th element is part of a swap. \textbf{Reason (R):} There are choices for the element to swap with, and the remaining elements form an involution. Which of the following is correct?

Question 6

Level 1: Warm-up

When manually counting the number of self-inverse mappings for n = 4 with exactly two swaps, a student calculates (2 4) \times (2 2) = 6 . What is the correct number of such mappings after accounting for overcounting?

Question 7

Level 1: Warm-up

What is the sum of the digits of the number 2458, and is it divisible by 3?

Question 8

Level 1: Warm-up

A student claims that selecting 2 digits from the group R_{1} = {1, 4, 7} is enough to make their sum of remainders divisible by 3. What is the minimum number of digits you must actually select from R_{1} to contradict this claim and reach a sum of remainders of at least 3?

Question 9

Level 1: Warm-up

To form a 4-digit number divisible by 3 from the set {1, 2, 3, 4, 5, 6, 7, 8, 9}, a student claims they only need to pick digits from R_{1} and R_{2} . What is the minimum number of digits from R_{1} required if they pick exactly two digits from R_{2}, such that the total sum of remainders is divisible by 3?

Question 10

Level 1: Warm-up

A bijection f : S \to S is called a self-inverse mapping if applying it twice returns every element to itself. Which of the following equations correctly defines this property for all n \in S ?

Free preview ends here

Login to view the complete notes

Creating an account is free. You get the rest of this chapter, step-by-step solutions, and a study plan built around the topics you are actually weak at.

Why MastersUp

Personalised first. High quality throughout.

Most platforms hand everyone the same content. Here the content moves with your performance, topic by topic.

Built around you, not around a syllabus PDF

Every answer you give moves your topic-level intelligence rate. The next question, the next revision card and tomorrow's plan all change with it.

Revision that hits your weak spots

We only revise topics you have actually attempted and are still below the safe bar on — never the same chapter on repeat.

Questions calibrated to the real exam

Each question carries a measured toughness. You are served a rung above your current level, so practice keeps stretching you.

Notes written for recall, not for volume

Full lesson cards for first study, curated short-note cards for the last mile — with derivations, traps and exam patterns marked.

One place for everything

Notes, chapter practice, previous-year questions, test series and full-length papers — all feeding one picture of your preparation.

Honest progress

No vanity streaks. Progress here means chapters mastered and accuracy that held up on harder questions.

Unlock the whole course

Full notes and short notes, the complete question bank with worked solutions, mock tests, full-length papers, and an adaptive plan that rebuilds itself as you improve.

View all plans Start free

Combinatorial Counting and Bijections Notes for GATE DA

Combinatorial Counting and Bijections notes for GATE DA: 11 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Chapter Roadmap: Combinatorial Counting and Bijections

Chapter Roadmap

Combinatorial Counting and Bijections

Topic 1: Digit-Based Counting

Forming numbers from restricted sets using divisibility rules (mod 3/9).

Topic 2: Bijections & Involutions

Counting self-inverse mappings $f (f (n)) = n$ .

Goal: Master modular arithmetic for filtering combinations and permutation adjustments for leading zeros.

The Core Idea: Divisibility by 3

Number is divisible by 3

$⟺$

Sum of digits is divisible by 3

This rule allows us to ignore digit positions initially. We only care about which combination of digits sums to a multiple of 3.

Digits

{1, 3, 4, 7}

→

Sum

1 + 3 + 4 + 7 = 15

Step-by-Step Method for Digit Counting

Step-by-Step Method

Categorize by Remainder:
$R_{0} : 0, 3, 6, 9$ $R_{1} : 1, 4, 7$ $R_{2} : 2, 5, 8$
Select Valid Combinations: Ensure sum of remainders $\equiv 0 (mod 3)$ .
Permute & Adjust: Calculate $n!$ . If $0$ is present, subtract cases starting with 0.

Valid = Total Perms - Starts with 0

Forming 4-Digit Numbers Divisible by 3

Example: 4-Digit Numbers

Set:

{1, 3, 4, 6, 7}

$R_{0} = {3, 6}, R_{1} = {1, 4, 7}, R_{2} = \emptyset$

Logic: Need 4 digits. Sum of remainders $\equiv 0 (mod 3)$ .

Only solution: 1 from $R_{0}$ , 3 from $R_{1}$ .
Ways: $(1 2) \times (3 3) = 2$ sets.

Sets:

{3, 1, 4, 7}, {6, 1, 4, 7}

2 \times 24 = 48

Combinatorial Counting and Bijections: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Quantitative Aptitude MCQ

Which of the following sets of three digits has a sum that is exactly divisible by 3?

A.
{1, 2, 4}
B.
{1, 3, 5}
C.
{2, 3, 5}
D.
{2, 4, 5}

Correct Answer:

Step-by-Step Solution

Key idea: Direct application of the digit sum rule for divisibility by 3.

Step 1: Calculate the sum of digits for each option.

Option A: 1 + 2 + 4 = 7 (Not divisible by 3)
Option B: 1 + 3 + 5 = 9 (Divisible by 3)
Option C: 2 + 3 + 5 = 10 (Not divisible by 3)
Option D: 2 + 4 + 5 = 11 (Not divisible by 3)

Step 2: Identify the set with a sum divisible by 3.

Answer: {1, 3, 5}

Question 2 · Quantitative Aptitude MCQ

When forming 4-digit numbers from a selected set of 4 distinct digits that includes 0, which of the following correctly describes the adjustment needed for the total permutations?

A.
No adjustment is needed; all $4!$ permutations form valid 4-digit numbers.
B.
We must subtract 4 because 0 cannot be in any of the 4 positions.
C.
We must subtract $3!$ because 0 cannot be the leading digit.
D.
We must multiply by 3 because 0 can only be in the last 3 positions.

Correct Answer:

Step-by-Step Solution

Key idea: A 4-digit number cannot start with 0.

Step 1: Calculate total permutations of 4 distinct digits, which is $4! = 24$ .

Step 2: Identify invalid permutations. If 0 is the leading digit, the remaining 3 digits can be arranged in $3! = 6$ ways. These form 3-digit numbers, not 4-digit numbers.

Step 3: Subtract the invalid permutations from the total.

Valid = $4! - 3! = 24 - 6 = 18$ .

Answer: We must subtract $3!$ because 0 cannot be the leading digit.

Question 3 · Quantitative Aptitude MCQ

Which of the following 4-digit numbers is divisible by 3?

A.
1235
B.
2346
C.
3458
D.
4579

Correct Answer:

Step-by-Step Solution

Key idea: A number is divisible by 3 if the sum of its digits is divisible by 3.

Step 1: Calculate the sum of digits for each option.

1235: 1 + 2 + 3 + 5 = 11 (Not divisible)
2346: 2 + 3 + 4 + 6 = 15 (Divisible by 3)
3458: 3 + 4 + 5 + 8 = 20 (Not divisible)
4579: 4 + 5 + 7 + 9 = 25 (Not divisible)

Step 2: Identify the number with a digit sum divisible by 3.

Answer: 2346

Question 4 · Quantitative Aptitude MCQ

Consider the formation of 4-digit numbers from the set {0, 2, 4, 6}. Which of the following statements correctly bounds the number of valid 4-digit numbers?

A.
It is exactly $4! = 24$ , because there are 4 distinct digits.
B.
It is $4! - 3! = 18$ , because 0 cannot be the leading digit.
C.
It is $4! - 4 = 20$ , because 0 cannot be in any of the 4 positions.
D.
It is $4 im es 3! = 24$ , because 0 can be placed in any of the 4 positions.

Correct Answer:

Step-by-Step Solution

Key idea: A 4-digit number cannot start with 0.

Step 1: Calculate total permutations of 4 distinct digits, which is $4! = 24$ .

Step 2: Identify invalid permutations. If 0 is the leading digit, the remaining 3 digits can be arranged in $3! = 6$ ways.

Step 3: Subtract the invalid permutations from the total.

Valid = $4! - 3! = 24 - 6 = 18$ .

Answer: It is $4! - 3! = 18$ , because 0 cannot be the leading digit.

Question 5 · Quantitative Aptitude MCQ

Consider the following statements regarding the recurrence relation $I (n) = I (n - 1) + (n - 1) I (n - 2)$ for counting involutions.

\textbf{Assertion (A):} The term $(n - 1) I (n - 2)$ accounts for the cases where the $n$ -th element is part of a swap.

\textbf{Reason (R):} There are $n - 1$ choices for the element to swap with, and the remaining $n - 2$ elements form an involution.

Which of the following is correct?

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is NOT the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: Evaluating Assertion-Reason statements on the derivation of the recurrence relation.

Step 1: Evaluate Assertion (A). The term $(n - 1) I (n - 2)$ indeed represents the cases where the $n$ -th element swaps with one of the other $n - 1$ elements. A is true.

Step 2: Evaluate Reason (R). If the $n$ -th element swaps, there are $n - 1$ choices for its partner. Once paired, both are accounted for, leaving $n - 2$ elements to form an involution, which gives $I (n - 2)$ . R is true.

Step 3: Check if R explains A. Yes, the logic in R directly derives the term $(n - 1) I (n - 2)$ described in A.

Answer: Both A and R are true and R is the correct explanation of A.

Question 6 · Quantitative Aptitude MCQ

When manually counting the number of self-inverse mappings for $n = 4$ with exactly two swaps, a student calculates $(2 4) \times (2 2) = 6$ . What is the correct number of such mappings after accounting for overcounting?

A.
1
B.
3
C.
6
D.
12

Correct Answer:

Step-by-Step Solution

Key idea: Two swap pairs of the same length are indistinguishable in order.

Step 1: The student calculated the raw combinations: $6 \times 1 = 6$ .

Step 2: Since there are $k = 2$ identical swap pairs, we must divide by $k! = 2! = 2$ .

Step 3: Correct count = $6/2 = 3$ .

Answer: 3

Question 7 · Quantitative Aptitude MCQ

What is the sum of the digits of the number 2458, and is it divisible by 3?

A.
19, Yes
B.
19, No
C.
20, Yes
D.
20, No

Correct Answer:

Step-by-Step Solution

Key idea: Direct calculation of the digit sum and checking divisibility.

Step 1: Sum the digits of 2458: 2 + 4 + 5 + 8 = 19.

Step 2: Check if 19 is divisible by 3. Since 19 = 3 * 6 + 1, it is not divisible by 3.

Answer: 19, No

Question 8 · Quantitative Aptitude MCQ

A student claims that selecting 2 digits from the group $R_{1} = {1, 4, 7}$ is enough to make their sum of remainders divisible by 3. What is the minimum number of digits you must actually select from $R_{1}$ to contradict this claim and reach a sum of remainders of at least 3?

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: Evaluating a claim and finding the minimum counter-value.

Step 1: The student claims 2 digits from $R_{1}$ give a sum of remainders divisible by 3. Each digit in $R_{1}$ has remainder 1, so 2 digits give a sum of 2. This is not divisible by 3, so the claim is false.

Step 2: To contradict the claim and reach a sum of at least 3, we need $k$ digits such that $k \times 1 \geq 3$ .

Step 3: The minimum integer $k$ satisfying this is 3.

Answer: 3

Question 9 · Quantitative Aptitude MCQ

To form a 4-digit number divisible by 3 from the set {1, 2, 3, 4, 5, 6, 7, 8, 9}, a student claims they only need to pick digits from $R_{1}$ and $R_{2}$ . What is the minimum number of digits from $R_{1}$ required if they pick exactly two digits from $R_{2}$ , such that the total sum of remainders is divisible by 3?

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: Evaluating a claim and finding the minimum counter-value using modular arithmetic.

Step 1: Each digit in $R_{2}$ has a remainder of 2. Picking two digits from $R_{2}$ gives a sum of remainders: 2 + 2 = 4.

Step 2: The remainder 4 is equivalent to 1 modulo 3 (since 4 = 3*1 + 1).

Step 3: To make the total sum of remainders divisible by 3 (i.e., 0 modulo 3), we need the remaining digits from $R_{1}$ (each with remainder 1) to sum to 2 modulo 3.

Step 4: Since each digit from $R_{1}$ contributes 1, we need exactly 2 digits from $R_{1}$ to get a sum of 2.

Answer: 2

Question 10 · Quantitative Aptitude MCQ

A bijection $f : S \to S$ is called a self-inverse mapping if applying it twice returns every element to itself. Which of the following equations correctly defines this property for all $n \in S$ ?

A.
$f (n) = n$
B.
$f (f (n)) = n$
C.
$f (f (n)) = - n$
D.
$f (n) = 2 n$

Correct Answer:

Step-by-Step Solution

Key idea: Direct recall of the definition of a self-inverse mapping (involution).

Step 1: Recall the definition of a self-inverse mapping. It is a function where applying the function twice yields the original input.

Step 2: Translate this into mathematical notation: $f (f (n)) = n$ .

Answer: $f (f (n)) = n$

combinatorial counting and bijections notes

Chapter Roadmap: Combinatorial Counting and Bijections

Chapter Roadmap

Topic 1: Digit-Based Counting

Topic 2: Bijections & Involutions

The Core Idea: Divisibility by 3

The Core Idea: Divisibility by 3

Step-by-Step Method for Digit Counting

Step-by-Step Method

Try a question

Login to view the complete notes

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

Combinatorial Counting and Bijections Notes for GATE DA

Chapter Roadmap: Combinatorial Counting and Bijections

Chapter Roadmap

Topic 1: Digit-Based Counting

Topic 2: Bijections & Involutions

The Core Idea: Divisibility by 3

The Core Idea: Divisibility by 3

Step-by-Step Method for Digit Counting

Step-by-Step Method

Forming 4-Digit Numbers Divisible by 3

Example: 4-Digit Numbers

Combinatorial Counting and Bijections: Solved Questions with Step-by-Step Explanations (10 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

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More notes in this unit