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}$ .

Counting subsets

|P(A)| = 2^n \qquad \text{proper subsets} = 2^n - 1 \qquad \text{subsets containing a fixed element} = 2^{n-1}

Worked example

A set S has

2n+1

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

Practice this conceptself-check · 4 quick reps

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|)$ .

Inclusion–exclusion (two sets)

|A \cup B| = |A| + |B| - |A \cap B| \qquad |A \cap B| \ge |A| + |B| - |U|

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?

Practice this conceptself-check · 3 quick reps

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.

Inclusion–exclusion (three sets)

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

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|

Practice this conceptself-check · 3 quick reps

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})$ .

Survey accounting identities

\text{exactly two} = \textstyle\sum\text{pairwise} - 3\,(\text{all three}) \qquad \text{at least two} = \text{exactly two} + (\text{all three})

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.

Practice this conceptself-check · 4 quick reps

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.

Formulas (4)

Power set and counting subsets
Counting subsets
$|P(A)| = 2^n \qquad \text{proper subsets} = 2^n - 1 \qquad \text{subsets containing a fixed element} = 2^{n-1}$
Inclusion-exclusion for two sets
Inclusion–exclusion (two sets)
$|A \cup B| = |A| + |B| - |A \cap B| \qquad |A \cap B| \ge |A| + |B| - |U|$
Inclusion-exclusion for three sets
Inclusion–exclusion (three sets)
$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |B \cap C| - |A \cap C| + |A \cap B \cap C|$
Survey problems — exactly one, exactly two, all three
Survey accounting identities
$\text{exactly two} = \textstyle\sum\text{pairwise} - 3\,(\text{all three}) \qquad \text{at least two} = \text{exactly two} + (\text{all three})$

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

Drill every past-year question on this subtopic

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

Drill the 27 questions