chapter

Counting, Sets and Elementary Probability Short Notes for GATE CS

Counting, Sets and Elementary Probability short notes for GATE CS: 3 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice q

counting sets and elementary probability short notes

Quick Reference: Sets and Inclusion-Exclusion

Core Formulas Two Sets: n (A \cup B) = n (A) + n (B) - n (A \cap B) Three Sets: n (A \cup B \cup C) = n (A) + n (B) + n (C) - n (A \cap B) - n (A \cap C) - n (B \cap C) + n (A \cap B \cap C) Complement: n (A^{'}) = n (U) - n (A) Neither (for two sets): n (neither) = n (U) - n (A \cup B) Key Relationships Quantity Formula Union n (A \cup B) = n (A) + n (B) - n (A \cap B) Intersection n (A \cap B) = n (A) + n (B) - n (A \cup B) Only A n (A) - n (A \cap B) Only B n (B) - n (A \cap B) At least one n (A \cup B) Neither n (U) - n (A \cup B) Problem-Solving Method Identify the universal set U Define sets A, B, C clearly List all given information Apply inclusion-exclusion formula Solve for the unknown Verify the answer makes sense Common Traps to Avoid ❌ Confusing "neither" with intersection ❌ Forgetting to subtract n (A \cap B) when finding union ❌ Assuming "neither" means A \cap B = \emptyset ❌ Not checking if answer fits within n (U) Memory Hooks Two sets: "Add both, subtract overlap" Three sets: "Add singles, subtract pairs, add triple" Neither: "Total minus union" Only A: "A minus both"

Quick Revision: Permutations

Essential Formulas Permutation formula:^{n} P_{r} = \frac{n !}{( n - r )!} Arrange all n objects: n! Circular arrangement: (n - 1)! Decision Checklist Does order matter? \to Yes = Permutation Are all objects used? \to Yes = n! Must objects be together? \to Treat as unit, multiply by internal arrangements Circular arrangement? \to Use (n - 1)! Avoid These Mistakes Forgetting to arrange objects within a group Using permutation when order doesn't matter Treating identical objects as distinct Forgetting 0! = 1

Dice Probability Checklist

Dice Probability Checklist Summary 1 A fair six-faced die has equally likely outcomes. 2 Two rolls give ordered outcomes. 3 Use 4 For conditions involving "multiple", "factor", "divisor", or "greater than", fix one roll and count the other roll case by case. 5 "Integer multiple" includes the equal case unless the problem says "proper multiple". 6 Sums of two dice are not equally likely. Their ordered counts are 7 Final answer: count carefully, divide by , and simplify the fraction.

Try a question

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

Question 1

Level 1: Warm-up

In a group of 50 people, 30 like tea and 25 like coffee. What is the minimum number of people who like both tea and coffee?

Question 2

Level 1: Warm-up

A fair die is rolled twice. Let a be the first roll and b be the second. Which of the following is the exact number of outcomes where b \geq a ?

Question 3

Level 1: Warm-up

Assertion (A): The number of outcomes where the second roll is an integer multiple of the first roll is 14. Reason (R): For each first roll a, the number of valid second rolls b is the count of multiples of a in {1, 2, 3, 4, 5, 6}, which sums to 6 + 3 + 2 + 1 + 1 + 1 = 14 .

Question 4

Level 1: Warm-up

Let U be the set of integers from 1 to 30. Let A be the set of all multiples of 4 in U . What is the maximum possible number of elements in A \cap B, where B is a subset of U with exactly 5 elements?

Question 5

Level 1: Warm-up

Assertion (A): The number of distinct arrangements of the letters in the word "BOOK" is 24. Reason (R): The formula^{4} P_{4} = 4! gives the number of ways to arrange 4 distinct objects in a row.

Question 6

Level 1: Warm-up

A fair six-faced die is rolled twice. What is the maximum possible number of ordered outcomes where the first roll is strictly greater than the second roll?

Question 7

Level 1: Warm-up

Let S be a set containing 20 elements. If a subset A contains 8 elements, what is the cardinality of the complement of A with respect to S ?

Question 8

Level 1: Warm-up

For any non-negative integers n and r such that r \leq n, which of the following inequalities is always true?

Question 9

Level 1: Warm-up

In how many ways can 3 distinct books be arranged on a shelf from a collection of 5 distinct books?

Question 10

Level 1: Warm-up

A fair die is rolled twice. What is the minimum number of outcomes that must be removed from the sample space of 36 to ensure that no outcome contains a 6?

Free preview ends here

Login to view the complete short 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

Counting, Sets and Elementary Probability Short Notes for GATE CS

Counting, Sets and Elementary Probability short notes for GATE CS: 3 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Quick Reference: Sets and Inclusion-Exclusion

Core Formulas

Two Sets:
$n (A \cup B) = n (A) + n (B) - n (A \cap B)$

Three Sets:
$n (A \cup B \cup C) = n (A) + n (B) + n (C) - n (A \cap B) - n (A \cap C) - n (B \cap C) + n (A \cap B \cap C)$

Complement:
$n (A^{'}) = n (U) - n (A)$

Neither (for two sets):
$n (neither) = n (U) - n (A \cup B)$

Key Relationships

Quantity	Formula
Union	$n (A \cup B) = n (A) + n (B) - n (A \cap B)$
Intersection	$n (A \cap B) = n (A) + n (B) - n (A \cup B)$
Only A	$n (A) - n (A \cap B)$
Only B	$n (B) - n (A \cap B)$
At least one	$n (A \cup B)$
Neither	$n (U) - n (A \cup B)$

Problem-Solving Method

Identify the universal set $U$
Define sets $A$ , $B$ , $C$ clearly
List all given information
Apply inclusion-exclusion formula
Solve for the unknown
Verify the answer makes sense

Common Traps to Avoid

❌ Confusing "neither" with intersection
❌ Forgetting to subtract $n (A \cap B)$ when finding union
❌ Assuming "neither" means $A \cap B = \emptyset$
❌ Not checking if answer fits within $n (U)$

Memory Hooks

Two sets: "Add both, subtract overlap"
Three sets: "Add singles, subtract pairs, add triple"
Neither: "Total minus union"
Only A: "A minus both"

Quick Revision: Permutations

Essential Formulas

Permutation formula:

^{n} P_{r} = \frac{n !}{( n - r )!}

Arrange all n objects:

n!

Circular arrangement:

(n - 1)!

Decision Checklist

Does order matter? → Yes = Permutation

Are all objects used? → Yes =

n!

Must objects be together? → Treat as unit, multiply by internal arrangements

Circular arrangement? → Use $(n - 1)!$

Avoid These Mistakes

Forgetting to arrange objects within a group
Using permutation when order doesn't matter
Treating identical objects as distinct
Forgetting $0! = 1$

Dice Probability Checklist

Summary

A fair six-faced die has

6

equally likely outcomes.

Two rolls give

6^{2} = 36

ordered outcomes.

Use

P (E) = \frac{favourable outcomes}{total outcomes} .

For conditions involving "multiple", "factor", "divisor", or "greater than", fix one roll and count the other roll case by case.

"Integer multiple" includes the equal case unless the problem says "proper multiple".

Sums of two dice are not equally likely. Their ordered counts are

1, 2, 3, 4, 5, 6, 5, 4, 3, 2, 1.

Final answer: count carefully, divide by

36

, and simplify the fraction.

Counting, Sets and Elementary Probability: Solved Questions with Step-by-Step Explanations (10 Problems)

Question 1 · Quantitative Aptitude MCQ

In a group of 50 people, 30 like tea and 25 like coffee. What is the minimum number of people who like both tea and coffee?

A.
5
B.
15
C.
25
D.
55

Correct Answer:

Step-by-Step Solution

Key idea: Use the inclusion-exclusion principle and the fact that the union cannot exceed the total population.

Step 1: Let $T$ be the set of tea lovers and $C$ be the set of coffee lovers. We have $n (T) = 30$ , $n (C) = 25$ , and the total population $n (U) = 50$ .

Step 2: The inclusion-exclusion formula is $n (T \cup C) = n (T) + n (C) - n (T \cap C)$ .

Step 3: Since $n (T \cup C) \leq n (U)$ , we have $30 + 25 - n (T \cap C) \leq 50$ .

Step 4: Simplify the inequality: $55 - n (T \cap C) \leq 50 ⟹ n (T \cap C) \geq 5$ .

Answer: 5

Question 2 · Quantitative Aptitude MCQ

A fair die is rolled twice. Let $a$ be the first roll and $b$ be the second. Which of the following is the exact number of outcomes where $b \geq a$ ?

A.
15
B.
18
C.
21
D.
36

Correct Answer:

Step-by-Step Solution

Key idea: Fix the first roll $a$ and count the valid second rolls $b$ that satisfy $b \geq a$ .

Step 1: If $a = 1$ , $b$ can be 1, 2, 3, 4, 5, 6 (6 outcomes).

Step 2: If $a = 2$ , $b$ can be 2, 3, 4, 5, 6 (5 outcomes).

Step 3: If $a = 3$ , $b$ can be 3, 4, 5, 6 (4 outcomes).

Step 4: If $a = 4$ , $b$ can be 4, 5, 6 (3 outcomes).

Step 5: If $a = 5$ , $b$ can be 5, 6 (2 outcomes).

Step 6: If $a = 6$ , $b$ can be 6 (1 outcome).

Step 7: Sum the cases: $6 + 5 + 4 + 3 + 2 + 1 = 21$ .

Answer: 21

Question 3 · Quantitative Aptitude MCQ

Assertion (A): The number of outcomes where the second roll is an integer multiple of the first roll is 14.

Reason (R): For each first roll $a$ , the number of valid second rolls $b$ is the count of multiples of $a$ in ${1, 2, 3, 4, 5, 6}$ , which sums to $6 + 3 + 2 + 1 + 1 + 1 = 14$ .

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: Verify the assertion by performing the case count described in the reason.

Step 1: Evaluate Assertion (A). We need to count pairs $(a, b)$ where $b$ is an integer multiple of $a$ .

Step 2: If $a = 1$ , $b \in {1, 2, 3, 4, 5, 6}$ (6 outcomes).

Step 3: If $a = 2$ , $b \in {2, 4, 6}$ (3 outcomes).

Step 4: If $a = 3$ , $b \in {3, 6}$ (2 outcomes).

Step 5: If $a = 4, 5, 6$ , $b$ can only be $a$ itself (1 outcome each).

Step 6: Sum the cases: $6 + 3 + 2 + 1 + 1 + 1 = 14$ . Thus, A is true.

Step 7: Evaluate Reason (R). The reason correctly describes the exact case-counting method and sum that proves A. Thus, R is true and is the correct explanation.

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

Question 4 · Quantitative Aptitude MCQ

Let $U$ be the set of integers from 1 to 30. Let $A$ be the set of all multiples of 4 in $U$ . What is the maximum possible number of elements in $A \cap B$ , where $B$ is a subset of $U$ with exactly 5 elements?

A.
5
B.
7
C.
12
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: The intersection $A \cap B$ cannot be larger than the smaller of the two sets $A$ and $B$ .

Step 1: Find the elements of $A$ . Multiples of 4 from 1 to 30 are ${4, 8, 12, 16, 20, 24, 28}$ .

Step 2: Count the elements in $A$ . There are 7 elements, so $n (A) = 7$ .

Step 3: We are given that $B$ has exactly 5 elements, so $n (B) = 5$ .

Step 4: The maximum size of $A \cap B$ occurs when all elements of $B$ are also in $A$ . Since $n (B) = 5$ and $n (A) = 7 \geq 5$ , the maximum intersection is 5.

Answer: 5

Question 5 · Quantitative Aptitude MCQ

Assertion (A): The number of distinct arrangements of the letters in the word "BOOK" is 24.

Reason (R): The formula $^{4} P_{4} = 4!$ gives the number of ways to arrange 4 distinct objects in a row.

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 false but R is true
D.
A is false but R is false

Correct Answer:

Step-by-Step Solution

Key idea: The permutation formula $^{n} P_{n} = n!$ applies only to distinct objects.

Step 1: Evaluate Assertion (A). The word "BOOK" has 4 letters, but the letter 'O' repeats twice.

Step 2: The number of distinct arrangements is $\frac{4 !}{2 !} = \frac{24}{2} = 12$ . Thus, A is false.

Step 3: Evaluate Reason (R). The statement " $^{4} P_{4} = 4!$ gives the number of ways to arrange 4 distinct objects" is a mathematically true statement.

Step 4: Since A is false and R is true, the correct option is C.

Answer: A is false but R is true

Question 6 · Quantitative Aptitude MCQ

A fair six-faced die is rolled twice. What is the maximum possible number of ordered outcomes where the first roll is strictly greater than the second roll?

A.
12
B.
15
C.
18
D.
21

Correct Answer:

Step-by-Step Solution

Key idea: Use symmetry and the boundary condition where the two rolls are equal.

Step 1: The total number of ordered outcomes for two rolls is $6 \times 6 = 36$ .

Step 2: The outcomes can be split into three categories: first > second, first < second, and first = second.

Step 3: The number of outcomes where first = second is exactly 6: (1,1), (2,2), (3,3), (4,4), (5,5), (6,6).

Step 4: The remaining outcomes are $36 - 6 = 30$ . By symmetry, exactly half of these have first > second.

Step 5: Calculate the result: $30/2 = 15$ .

Answer: 15

Question 7 · Quantitative Aptitude MCQ

Let $S$ be a set containing 20 elements. If a subset $A$ contains 8 elements, what is the cardinality of the complement of $A$ with respect to $S$ ?

A.
12
B.
28
C.
160
D.
-12

Correct Answer:

Step-by-Step Solution

Key idea: The complement of a subset $A$ with respect to a universal set $S$ contains all elements in $S$ that are not in $A$ .

Step 1: Identify the total number of elements in the universal set $S$ , which is $n (S) = 20$ .

Step 2: Identify the number of elements in the subset $A$ , which is $n (A) = 8$ .

Step 3: Apply the complement formula: $n (A^{'}) = n (S) - n (A)$ .

Step 4: Calculate the result: $20 - 8 = 12$ .

Answer: 12

Question 8 · Quantitative Aptitude MCQ

For any non-negative integers $n$ and $r$ such that $r \leq n$ , which of the following inequalities is always true?

A.
$^{n} P_{r} \geq n!$
B.
$^{n} P_{r} \leq n!$
C.
$^{n} P_{r} \geq (n + 1)!$
D.
$^{n} P_{r} = (n - r)!$

Correct Answer:

Step-by-Step Solution

Key idea: The permutation formula $^{n} P_{r}$ is a product of $r$ decreasing terms starting from $n$ .

Step 1: Recall the formula: $^{n} P_{r} = n \times (n - 1) \times \dots \times (n - r + 1)$ .

Step 2: Notice that $n! = n \times (n - 1) \times \dots \times 1$ .

Step 3: Since $r \leq n$ , the product for $^{n} P_{r}$ contains $r$ terms, while $n!$ contains $n$ terms.

Step 4: If $r = n$ , $^{n} P_{r} = n!$ . If $r < n$ , $^{n} P_{r}$ is missing the terms from $(n - r)$ down to 1, which are all $\geq 1$ . Thus, $^{n} P_{r} \leq n!$ .

Answer: $^{n} P_{r} \leq n!$

Question 9 · Quantitative Aptitude MCQ

In how many ways can 3 distinct books be arranged on a shelf from a collection of 5 distinct books?

A.
10
B.
120
C.
60
D.
125

Correct Answer:

Step-by-Step Solution

Key idea: This is a permutation problem because the order of the books on the shelf matters.

Step 1: Identify the total number of objects $n = 5$ and the number of objects to arrange $r = 3$ .

Step 2: Apply the permutation formula $^{n} P_{r} = \frac{n !}{( n - r )!}$ .

Step 3: Substitute the values: $^{5} P_{3} = \frac{5 !}{( 5 - 3 )!} = \frac{5 !}{2 !}$ .

Step 4: Calculate the result: $\frac{120}{2} = 60$ .

Answer: 60

Question 10 · Quantitative Aptitude MCQ

A fair die is rolled twice. What is the minimum number of outcomes that must be removed from the sample space of 36 to ensure that no outcome contains a 6?

A.
10
B.
12
C.
25
D.
11

Correct Answer:

Step-by-Step Solution

Key idea: Use the complement. Find the number of outcomes that do not contain a 6, and subtract from the total.

Step 1: The total number of outcomes is 36.

Step 2: An outcome contains no 6 if both rolls are from the set ${1, 2, 3, 4, 5}$ .

Step 3: The number of such outcomes is $5 \times 5 = 25$ .

Step 4: The number of outcomes to remove is the total minus the outcomes with no 6: $36 - 25 = 11$ .

Answer: 11

counting sets and elementary probability short notes

Quick Reference: Sets and Inclusion-Exclusion

Core Formulas

Key Relationships

Problem-Solving Method

Common Traps to Avoid

Memory Hooks

Quick Revision: Permutations

Essential Formulas

Decision Checklist

Avoid These Mistakes

Dice Probability Checklist

Dice Probability Checklist

Try a question

Login to view the complete short 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

Counting, Sets and Elementary Probability Short Notes for GATE CS

Quick Reference: Sets and Inclusion-Exclusion

Core Formulas

Key Relationships

Problem-Solving Method

Common Traps to Avoid

Memory Hooks

Quick Revision: Permutations

Essential Formulas

Decision Checklist

Avoid These Mistakes

Dice Probability Checklist

Dice Probability Checklist

Counting, Sets and Elementary Probability: 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 short notes in this unit