NDA Maths · Sets & Relations

Counting, Subsets and Inclusion-Exclusion

An n-element set has 2ⁿ subsets; the inclusion-exclusion principle counts a union by adding the parts and subtracting the overlaps — the engine behind every Venn 'survey' word problem.

All Sets & Relations notes NDA Maths strategy

Why this matters

27 PYQs — the largest subtopic, and the home of the chapter's highest-yield HARD genre: the survey word problem (so many like cricket, so many like both, how many like exactly two). Master two things — counting subsets with 2ⁿ, and the exactly-one / exactly-two / all-three accounting — and you cover most of these marks.

Concept 1 of 4

Power set and counting subsets

Intuition

Each element of a set is either in or out of a subset, so an n-element set has

2^n

subsets — the power set. From that one fact flow proper-subset counts, superset counts, and a slick symmetry trick for 'at most half' the elements.

Definition

The counting rules:

A set with $n$ elements has $2^n$ subsets (the power set $P(A)$ ), of which $2^n - 1$ are proper subsets (all except the set itself).
Supersets of a fixed set $\{x\}$ : fix x as 'in', let the other $n-1$ elements vary $\Rightarrow 2^{n-1}$ subsets contain x.
Count carefully when elements are themselves sets: $A=\{\{1,2,3\}\}$ has ONE element, so $|P(A)|=2$ .
Symmetry trick: in a $(2n+1)$ -element set, the subsets of size $\le n$ are exactly half of all subsets $= \tfrac{1}{2}\cdot 2^{2n+1} = 2^{2n}$ .

Worked example

A set S has

2n+1

elements. The number of subsets of S with at most n elements is 256. Find n.

Subsets of size $0,1,\dots,n$ pair up with subsets of size $2n+1,\dots,n+1$ by complementation — exactly half of all subsets.
So that count is $\tfrac{1}{2}\cdot 2^{2n+1} = 2^{2n}$ .
Set $2^{2n} = 256 = 2^8 \Rightarrow 2n = 8 \Rightarrow n = 4$ .

Answer:

n = 4

Practice this conceptself-check · 4 quick reps

Try it yourself

How many subsets of

\{1,2,3,4\}

are supersets of

\{3\}

but are not the whole set?

Practice — Level 1 (4 reps)

Quick reps to lock in the method. Try each, then check.

1.
How many subsets does a 10-element set have?
2.
How many proper subsets does a 6-element set have?
3.
If $A = \{\{1,2\}\}$ , how many elements has $P(A)$ ?
4.
How many subsets of an 8-set contain a fixed element x?

From the bank · past-year question

Example 1Sets & RelationsMODERATE

A set S contains

(2n+1)

elements. If the number of subsets of S which contain at most

n

elements is 1024, then what is the value of

n

[Q7 · Apr · 2026]

Count the elements before raising 2 to a power

A=\{\lambda, \{\lambda,\mu\}\}

has TWO elements (an element

\lambda

and a SET

\{\lambda,\mu\}

), so

|P(A)|=4

. The brace-inside-brace is one element, not two — miscounting elements is the usual error.

Drill 10 more on power set and counting subsets

Concept 2 of 4

Inclusion-exclusion for two sets

Intuition

If you add the sizes of two overlapping sets you count the overlap twice, so subtract it once:

|A\cup B| = |A|+|B|-|A\cap B|

. The same idea bounds how small or large an overlap can be in 'at least / at most' survey questions.

Definition

The two-set rule and its uses:

$|A\cup B| = |A| + |B| - |A\cap B|$ .
For sets of multiples, $A\cap B$ uses the LCM: multiples of 3 $\cap$ multiples of 2 are multiples of 6.
Least overlap: $|A\cap B| \ge |A|+|B|-|U|$ (when the union can't exceed the universe). Most overlap: $|A\cap B| \le \min(|A|,|B|)$ .

Worked example

In a group of 100 people, 70 like tea and 80 like coffee, and everyone likes at least one. How many like both?

Everyone likes at least one, so $|T\cup C| = 100$ .
Inclusion-exclusion: $100 = 70 + 80 - |T\cap C|$ .
$|T\cap C| = 150 - 100 = 50$ .

Answer:50 like both.

Practice this conceptself-check · 3 quick reps

Try it yourself

How many integers from 1 to 100 are divisible by 2 or by 5?

Practice — Level 1 (3 reps)

Quick reps to lock in the method. Try each, then check.

1.
$|A|=30, |B|=25, |A\cap B|=10$ . Find $|A\cup B|$ .
2.
Multiples of 4 $\cap$ multiples of 6 are multiples of?
3.
$|A|=60, |B|=50$ in a universe of 100. Least $|A\cap B|$ ?

From the bank · past-year question

Example 2Sets & RelationsMODERATE

Suppose set

A

consists of first 250 natural numbers that are multiples of 3 and set

B

consists of first 200 even natural numbers. How many elements does

A\cup B

have?

[Q43 · Sep · 2021]

Overlap of multiples uses LCM, not product

Multiples of 4 and 6 in common are multiples of

\mathrm{lcm}(4,6)=12

, NOT

4\times 6 = 24

. Use the LCM whenever 'divisible by both' appears.

Drill 3 more on inclusion-exclusion for two sets

Concept 3 of 4

Inclusion-exclusion for three sets

Intuition

Three overlapping sets need alternating signs: add the three singles, subtract the three pairwise overlaps, add back the triple overlap. With three sets, max/min questions hinge on how large the triple overlap can be.

Definition

The three-set rule:

$|A\cup B\cup C| = |A|+|B|+|C| - |A\cap B| - |B\cap C| - |A\cap C| + |A\cap B\cap C|$ .
This equals the sum of the seven disjoint Venn regions.
Maximising/minimising the union: the only free quantity is the triple overlap $x = |A\cap B\cap C|$ . The union grows with x; x is bounded by $0 \le x \le \min$ of the pairwise intersections.

Worked example

Three sets satisfy

|A\cup B\cup C| = 90 + x

where

x=|A\cap B\cap C|

, and the pairwise intersections are 20, 15, 12. What is the maximum possible

|A\cup B\cup C|

The triple overlap can be at most the smallest pairwise intersection: $x \le \min(20,15,12) = 12$ .
The union increases with x, so use $x = 12$ .
$|A\cup B\cup C|_{\max} = 90 + 12 = 102$ .

Answer:102 (at

x = 12

Practice this conceptself-check · 3 quick reps

Try it yourself

Expand

n(X)+n(Y)+n(Z)-n(X\cap Y)-n(Y\cap Z)-n(X\cap Z)+n(X\cap Y\cap Z)

— what single quantity is it?

Practice — Level 1 (3 reps)

Quick reps to lock in the method. Try each, then check.

1.
Write the sign of the triple-overlap term in the 3-set formula.
2.
The 3-set formula equals the sum of how many disjoint regions?
3.
Triple overlap $x$ is bounded above by?

From the bank · past-year question

Example 3Sets & RelationsMODERATE

Consider the following for the next 02 (two) items that follow: In a school, all the students play at least one of three indoor games – chess, carrom and table tennis. 60 play chess, 50 play table tennis, 48 play carrom, 12 play chess and carrom, 15 play carrom and table tennis, 20 play table tennis and chess.

What can be the maximum number of students in the school?

[Q17 · Apr · 2019]

Mind the alternating signs

Pairwise intersections are SUBTRACTED, the triple intersection is ADDED. Dropping the

+|A\cap B\cap C|

term is the most common slip — it under-counts the union.

Drill 5 more on inclusion-exclusion for three sets

Concept 4 of 4

Survey problems — exactly one, exactly two, all three

Intuition

The hardest sets questions are surveys: so many play each game, so many play exactly two, how many play all three. The trick is to keep 'exactly k' and 'at least k' strictly separate, and to remember the two bridging identities. Most of these are pure region bookkeeping on a 3-circle Venn diagram.

Definition

The accounting identities (let one/two/three = people in exactly one / exactly two / all three regions):

Total in the union $= (\text{exactly one}) + (\text{exactly two}) + (\text{exactly three})$ . This is the 'exactly' decomposition — NOT the raw inclusion-exclusion sum.
Sum of pairwise intersections $= (\text{exactly two}) + 3\cdot(\text{all three})$ , so exactly two $= \sum\text{pairwise} - 3\cdot(\text{all three})$ .
At least two $= (\text{exactly two}) + (\text{all three})$ .
Exactly one $= \text{total} - (\text{at least two})$ .

Worked example

In a class everyone plays at least one of three sports. 25 play exactly two sports and 5 play all three. The pairwise totals

|A\cap B|+|B\cap C|+|A\cap C|

sum to S. Find S.

Each 'exactly two' person sits in one pairwise-intersection region: contributes 1 to S.
Each 'all three' person sits in all three pairwise intersections: contributes 3 to S.
So $S = (\text{exactly two}) + 3\cdot(\text{all three}) = 25 + 3(5) = 40$ .

Answer:

S = 40

Practice this conceptself-check · 4 quick reps

Try it yourself

In a class of 240, 10 passed none. Of those who passed at least one, 60 passed exactly one and 110 passed exactly two. How many passed all three?

Practice — Level 1 (4 reps)

Quick reps to lock in the method. Try each, then check.

1.
exactly two = (sum of pairwise) − ? × (all three)
2.
at least two = exactly two + ?
3.
Total in union (exactly form) = exactly one + exactly two + ?
4.
exactly one = total − ?

From the bank · past-year question

Example 4Sets & RelationsHARD

In a class of 240 students, 180 passed in English, 130 passed in Hindi and 150 passed in Sanskrit. Further, 60 passed in only one subject, 110 passed in only two subjects and 10 passed in none of the subjects. How many passed in all three subjects?

[Q40 · Sep · 2024]

'Exactly two' is not the sum of pairwise intersections

Each all-three person is counted in all three pairwise intersections, so

\sum\text{pairwise}

over-counts them by a factor of 3. Subtract: exactly two

= \sum\text{pairwise} - 3\cdot(\text{all three})

. Mixing up 'exactly' and 'at least' is the single biggest source of wrong answers here.

Drill 5 more on survey problems — exactly one, exactly two, all three

Summary — formulas & gotchas at a glance

A revision cheat-sheet for the formulas and gotchas above. Click any concept name to jump back to its full explanation.

Watch out for (4)

Count the elements before raising 2 to a power
→ Power set and counting subsets
Overlap of multiples uses LCM, not product
→ Inclusion-exclusion for two sets
Mind the alternating signs
→ Inclusion-exclusion for three sets
'Exactly two' is not the sum of pairwise intersections
→ Survey problems — exactly one, exactly two, all three

Mastery check — 5 interleaved questions

Try each one before clicking. Questions are interleaved across the concepts above, not grouped — interleaving sharpens transfer.

Example 1Sets & RelationsEASY

A=\{\{1,2,3\}\}

, then how many elements are there in the power set of

A

[Q23 · Apr · 2022]

Example 2Sets & RelationsMODERATE

Directions for the following three (03) items: Consider the following Venn diagram, where X, Y and Z are three sets. Let the number of elements in Z be denoted by n(Z) which is equal to 90. From the diagram: region only-in-Z = c, X∩Y only = 16, X∩Y∩Z = 18, Y∩Z only = 17, X∩Z only = 12, region only-in-X = a, region only-in-Y = b.

If the number of elements in Y and Z are in the ratio 4 : 5, then what is the value of b?

[Q16 · Apr · 2020]

Example 3Sets & RelationsEASY

Consider the information given below and answer the two items (02) that follow: In a class, 54 students are good in Hindi only, 63 students are good in Mathematics only and 41 students are good in English only. There are 18 students who are good in both Hindi and Mathematics. 10 students are good in all three subjects.

What is the number of students who are good in Hindi and Mathematics but not in English?

[Q14 · Apr · 2018]

Example 4Sets & RelationsHARD

Consider the following for the items that follow: A university awarded medals in basketball, football and volleyball. Only x students (x < 6) got medal in all the three sports and the medals went to a total of 15x students. It awarded 5x medals in basketball, (4x + 15) medals in football and (x + 25) medals in volleyball.

How many received medals in exactly two of the three sports?

[Q34 · Sep · 2022]

Example 5Sets & RelationsMODERATE

A = \{\lambda, \{\lambda, \mu\}\}

, then the power set of A is

[Q15 · Apr · 2019]

Drill every past-year question on this subtopic

27 questions from the bank — paginated, with cart and Word-export support.

Drill the 27 questions