Inclusion-exclusion and double counting

This chapter rigorously introduces advanced combinatorial techniques, including the Inclusion-Exclusion Principle and Double Counting. Mastery of these methods is crucial for effectively addressing complex enumeration problems, a common requirement in CMI examinations.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Counting through cases | | 2 | Complement counting | | 3 | Inclusion-exclusion principle | | 4 | Double counting |

---

We begin with Counting through cases.

Part 1: Counting through cases

Counting through Cases

Overview

Counting through cases is one of the most reliable combinatorial methods. The idea is simple: split a complicated counting problem into simpler, non-overlapping cases, count each case separately, and then add the answers. In harder problems, the challenge is not arithmetic but choosing a case split that is both complete and disjoint. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Partition a counting problem into valid cases.

Ensure the cases are exhaustive and non-overlapping.

Use addition and multiplication principles inside each case.

Detect bad case splits that overcount or miss possibilities.

Solve medium-level combinatorics questions by structured classification.

---

Core Idea

📖 Counting by Cases

Suppose a set of objects can be divided into cases

$\qquad C_1,\ C_2,\ \dots,\ C_k$

such that:

every desired object belongs to at least one case

no object belongs to more than one case

Then the total number of objects is

\qquad |C_1|+|C_2|+\cdots+|C_k|

This is just the addition principle applied carefully. ---

What Makes a Good Case Split?

❗ Two Conditions

A case split is useful only if it is:

Exhaustive

Every valid object must fall into some case.

Disjoint

No valid object should be counted in two different cases.

⚠️ Most Common Error

A case split that is not disjoint leads to overcounting.

A case split that is not exhaustive misses valid objects.

Both errors are common in exam problems.

---

Standard Reasons to Split into Cases

📐 Common Ways to Classify

You often split according to:

whether a specific element is chosen or not chosen

the first position or last position

parity: even / odd

number of repeated objects

largest or smallest element

whether a restriction is active or inactive

how many times a special symbol appears

A good split reduces the structure, not increases it. ---

Addition and Multiplication Principles Together

📐 Inside a Case

After splitting into cases, each case is usually counted using:

the multiplication principle

permutations

combinations

simple arrangement logic

Then all case-counts are added.

So the typical workflow is:

\qquad \text{split} \to \text{count each case} \to \text{add}

---

Minimal Worked Examples

Example 1 How many 3-digit numbers have distinct digits? Split into two cases according to whether the first digit is

0

or not. But since a 3-digit number cannot begin with

0

, the better approach is direct counting. First digit:

9

choices

(1

9)

Second digit:

9

choices Third digit:

8

choices So total:

\qquad 9\cdot 9\cdot 8=648

This example shows that not every problem needs a case split. --- Example 2 How many 4-letter strings over

\{A,B\}

contain at least one

A

and at least one

B

? Split into cases by number of

A

's:

exactly one $A$ : $\binom{4}{1}=4$

exactly two $A$ 's: $\binom{4}{2}=6$

exactly three $A$ 's: $\binom{4}{3}=4$

Total:

\qquad 4+6+4=14

This is a clean, disjoint, exhaustive case split. ---

When Cases Are Better Than Formulas

💡 Use Cases When

Use counting through cases when:

there is a visible special element

different configurations behave differently

a direct formula is messy

the condition says “at least one”, “exactly one”, “either-or”, or “depending on”

restrictions change according to the arrangement

---

Complement vs Cases

❗ A Useful Comparison

Sometimes a problem can be solved either:

by splitting into cases, or

by complement counting

For example, “at least one” often suggests complement.

But when the complement is not simpler, casework is usually better.

---

Common Patterns

📐 Typical Question Types

Count objects with exactly $k$ special features.

Count objects with at least one special feature by splitting into exact-count cases.

Count arrangements depending on where a distinguished object sits.

Count integers or strings according to parity or repeated symbols.

Count selections by whether a special group contributes $0,1,2,\dots$ elements.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Cases overlap

✅ Make the cases disjoint

❌ Cases do not cover everything

✅ Check exhaustiveness at the end

❌ Counting the same structure in two different languages

✅ Fix one classification principle and stay with it

❌ Using casework when one direct count is easier

✅ First look for the shortest correct method

---

CMI Strategy

💡 How to Build Good Casework

Identify the feature that causes different behaviour.

Split according to that feature.

Check the cases are disjoint.

Check the cases cover all possibilities.

Count each case independently and add.

At the end, do a quick sanity check on size.

---

Practice Questions

:::question type="MCQ" question="A counting-by-cases solution is valid only when the cases are" options=["equal in size","disjoint and exhaustive","all symmetric","all nonempty"] answer="B" hint="Think about when addition of case-counts works." solution="Counting by cases works when every valid object lies in exactly one case. So the cases must be disjoint and exhaustive. Therefore the correct option is

\boxed{B}

." ::: :::question type="NAT" question="How many binary strings of length

4

contain exactly two

1

's?" answer="6" hint="Choose the positions of the

1

's." solution="A binary string of length

4

with exactly two

1

's is determined by choosing which

2

of the

4

positions contain

1

. Hence the count is

\qquad \binom{4}{2}=6

Therefore the answer is

\boxed{6}

." ::: :::question type="MSQ" question="Which of the following are good ways to split a counting problem into cases?" options=["according to the number of selected special elements","according to whether a distinguished object is chosen or not","using overlapping cases and subtracting later without checking","according to parity when parity changes the structure"] answer="A,B,D" hint="A good split should simplify the problem and avoid uncontrolled overlap." solution="1. True. This is a very standard case split.

True. Presence/absence of a distinguished object is a natural split.

False. Overlapping cases are dangerous unless handled with precise correction.

True. Parity is often a useful structural classifier.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="How many 5-letter strings over

\{A,B\}

contain at least one

A

and at least one

B

? Solve by counting through cases." answer="

30

" hint="Split by the number of

A

's." solution="We count by the number of

A

's.

exactly one $A$ : $\binom{5}{1}=5$

exactly two $A$ 's: $\binom{5}{2}=10$

exactly three $A$ 's: $\binom{5}{3}=10$

exactly four $A$ 's: $\binom{5}{4}=5$

So the total number of valid strings is

\qquad 5+10+10+5=30

Hence the answer is

\boxed{30}

." ::: ---

Summary

❗ Key Takeaways for CMI

Counting through cases is addition after a correct partition.

The cases must be exhaustive and disjoint.

Good casework is about choosing the right classification.

Each case is usually counted using simpler principles.

In many combinatorics problems, the hard part is choosing the cases, not counting them.

---

💡 Next Up

Proceeding to Complement counting.

---

Part 2: Complement counting

Complement Counting

Overview

Complement counting is a counting strategy where we count the total number of objects first and then subtract the number of unwanted objects. It is especially useful when the direct count of the desired set is messy but the opposite set is easy to count. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Recognise when complement counting is more efficient than direct counting.

Use the formula

\qquad \text{wanted} = \text{total} - \text{unwanted}

correctly.

Solve “at least one”, “not all”, and “repetition” type counting problems.

Combine complement counting with basic inclusion-exclusion ideas when needed.

Avoid counting the complement incorrectly.

---

Core Idea

📖 Complement Counting Principle

If $U$ is the universal set and $A$ is the set we want to count, then

$\qquad |A| = |U| - |A^c|$

where $A^c$ is the complement of $A$ inside $U$ .

This is useful when:

$|U|$ is easy to count

$|A^c|$ is simpler than $|A|$

---

Standard Patterns

📐 Most Common Complement Forms

At least one

\qquad \text{count} = \text{total} - \text{none}

Contains repetition

\qquad \text{count} = \text{total} - \text{all distinct}

Not all satisfy a condition

\qquad \text{count} = \text{total} - \text{all satisfy it}

At least one forbidden digit / object / property

\qquad \text{count} = \text{total} - \text{no forbidden object appears}

---

Why It Works Well

❗ Why Complement Is Powerful

Many problems ask for a condition like:

at least one zero

at least one repeated digit

at least one success

not all chosen from one category

Such conditions are difficult to count directly because there may be many overlapping cases.

The opposite event is often cleaner:

no zero

no repeated digit

no success

all chosen from one category

---

Standard Examples of Complement Choice

💡 Good Situations for Complement Counting

Use complement counting when the desired condition involves:

“at least one”

“not all”

“at least one repeated”

“not equal to a special case”

many overlapping bad cases that collapse into one clean opposite case

---

Minimal Worked Examples

Example 1 How many binary strings of length

5

contain at least one

1

? Total number of binary strings:

\qquad 2^5=32

Complement: strings with no

1

, that is, all zeros:

\qquad 1

So the answer is

\qquad 32-1=31

--- Example 2 How many

4

-digit numbers have at least one repeated digit? Total

4

-digit numbers:

\qquad 9000

Complement: all digits distinct.

First digit: $9$ choices

Second digit: $9$ choices

Third digit: $8$ choices

Fourth digit: $7$ choices

So complement count:

\qquad 9\cdot 9\cdot 8\cdot 7 = 4536

Hence required count:

\qquad 9000-4536=4464

---

Relation with Inclusion-Exclusion

❗ Connection with Inclusion-Exclusion

Sometimes the complement itself is a union of several bad cases. Then:

$\qquad |A| = |U| - |A^c|$

but to compute $|A^c|$ , you may need inclusion-exclusion.

So complement counting and inclusion-exclusion are not rivals; they often work together.

---

Common Traps

⚠️ Avoid These Errors

❌ Forgetting to define the universe first

✅ Always decide what the total set is

❌ Counting the complement in a different universe

✅ Complement must be inside the same total set

❌ Missing restrictions such as first digit nonzero

✅ In number problems, leading digit rules matter

❌ Directly counting “at least one” by adding cases

✅ Cases may overlap; complement is often safer

❌ Using complement when the complement is actually harder

✅ Choose the simpler side to count

---

CMI Strategy

💡 How to Attack Complement Counting Questions

Define the total set clearly.

Translate the wanted condition into its exact opposite.

Check whether the opposite condition is easier to count.

Count total and complement in the same sample space.

Subtract only at the very end.

---

Practice Questions

:::question type="MCQ" question="How many binary strings of length

4

contain at least one

1

?" options=["

15

","

16

","

8

","

14

"] answer="A" hint="Count total strings and subtract the all-zero string." solution="Total binary strings of length

4

\qquad 2^4=16

Complement: the string with no

1

, namely

0000

\qquad 1

So required number:

\qquad 16-1=15

Hence the correct option is

\boxed{A}

." ::: :::question type="NAT" question="How many

3

-digit numbers contain no digit

7

?" answer="648" hint="Count directly in the complement-friendly form." solution="For a

3

-digit number with no digit

7

Hundreds place: $8$ choices, namely $1,2,3,4,5,6,8,9$

Tens place: $9$ choices, namely all digits except $7$

Units place: $9$ choices, namely all digits except $7$

So the count is

\qquad 8\cdot 9\cdot 9 = 648

Hence the answer is

\boxed{648}

." ::: :::question type="MSQ" question="Which of the following are suitable situations for complement counting?" options=["Counting objects with at least one repeated element","Counting objects with at least one success","Counting objects where every case is already disjoint and easy to count directly","Counting objects with no easy direct description but an easy opposite description"] answer="A,B,D" hint="Complement counting is best when the opposite set is simpler." solution="1. True.

True.

False. If direct counting is already simple and disjoint, complement may be unnecessary.

True.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Find the number of

4

-digit numbers with at least one digit equal to

0

." answer="

171

" hint="Count all

4

-digit numbers and subtract those with no zero." solution="Total number of

4

-digit numbers:

\qquad 9000

Complement:

4

-digit numbers with no zero.

First digit: $9$ choices

Second digit: $9$ choices

Third digit: $9$ choices

Fourth digit: $9$ choices

So complement count:

\qquad 9^4 = 6561

Hence required count:

\qquad 9000-6561 = 2439

Therefore the answer is

\boxed{2439}

." ::: ---

Summary

❗ Key Takeaways for CMI

Complement counting uses

\qquad \text{wanted}=\text{total}-\text{unwanted}

It is especially useful for “at least one” and repetition-type conditions.

The universe must be fixed before taking complements.

Leading-digit and restriction issues must be handled carefully.

In many problems, complement counting is the cleanest way to avoid overlapping cases.

---

💡 Next Up

Proceeding to Inclusion-exclusion principle.

---

Part 3: Inclusion-exclusion principle

Inclusion-Exclusion Principle

Overview

The inclusion-exclusion principle is the standard tool for counting objects that satisfy at least one of several conditions, especially when direct counting causes overcounting because some objects belong to multiple categories. In CMI-style problems, it appears in:

union of sets,

passwords with multiple required character types,

onto functions,

club membership problems,

arrangements with forbidden patterns,

exact-count conditions after subtracting overlaps.

The core skill is to count correctly without missing overlaps or counting the same object too many times. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Use inclusion-exclusion for two sets and three sets.

Count objects with at least one of several properties.

Count onto functions by excluding functions that miss one or more values.

Handle counting questions with letters, digits, vowels, consonants, and similar classes.

Decide when inclusion-exclusion is the right tool and when a gap method or direct counting is cleaner.

---

Core Formulas

📐 Two-Set Inclusion-Exclusion

For finite sets $A$ and $B$ ,

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

📐 Three-Set Inclusion-Exclusion

For finite sets $A,B,C$ ,

$\qquad |A\cup B\cup C| = |A|+|B|+|C| <ul><li>|A\cap B|-|B\cap C|-|C\cap A|</li></ul> + |A\cap B\cap C|$

❗ Why the Triple Term is Added Back

When you add $|A|+|B|+|C|$ , an element in all three sets is counted three times.

Then subtracting pairwise intersections removes it three times.

So it disappears completely, and must be added back once.

---

General Pattern

📐 General Idea

To count objects having at least one of several properties:

Count everything.

Subtract objects missing one property.

Add back objects missing two properties.

Subtract objects missing three properties.

Continue with alternating signs.

This is the main source of most exam formulas in this topic. ---

Counting With Complements

💡 Complement Method + Inclusion-Exclusion

Very often, the fastest route is:

$\qquad \text{wanted count} = \text{total count} - \text{bad count}$

But if the bad objects themselves break into overlapping classes, then inclusion-exclusion is used inside the bad count.

Example pattern:

total passwords

subtract passwords with no digit

subtract passwords with no letter

add back passwords with neither digit nor letter

---

Onto Functions

📐 Onto Functions to a 3-Element Set

Let $N=\{1,2,\dots,n\}$ and $L=\{a,b,c\}$ .

Total functions from $N$ to $L$ :

$\qquad 3^n$

To count onto functions, subtract those that miss at least one image:

miss $a$ : $\qquad 2^n$

miss $b$ : $\qquad 2^n$

miss $c$ : $\qquad 2^n$

This subtracts too much, since functions using only one symbol were subtracted twice too many times. Add them back:

only $a$ : $\qquad 1$

only $b$ : $\qquad 1$

only $c$ : $\qquad 1$

Hence

\qquad \text{onto functions } N\to L = 3^n - 3\cdot 2^n + 3

More generally, inclusion-exclusion is the standard method for counting onto functions. ---

Password and String Problems

📐 At Least One From Each Class

Suppose length- $m$ strings are formed from:

vowels: $5$

consonants: $21$

digits: $10$

Total alphabet size:

\qquad 5+21+10 = 36

Number of length-

m

strings with at least one vowel, at least one consonant, and at least one digit:

\qquad 36^m - 31^m - 15^m - 26^m + 21^m + 10^m + 5^m

because:

no vowel $\Rightarrow 31^m$

no consonant $\Rightarrow 15^m$

no digit $\Rightarrow 26^m$

no vowel and no consonant $\Rightarrow 10^m$

no vowel and no digit $\Rightarrow 21^m$

no consonant and no digit $\Rightarrow 5^m$

This pattern comes up very often. ---

Exact Distribution Questions

📐 Exactly

r_1,r_2,\dots,r_k

mapped to given images

If a function from an $n$ -element set to $\{a,b,c\}$ has:

exactly $r_1$ elements mapped to $a$

exactly $r_2$ mapped to $b$

exactly $r_3$ mapped to $c$

with

r_1+r_2+r_3=n

, then the count is

\qquad \dfrac{n!}{r_1!\,r_2!\,r_3!}

This is not inclusion-exclusion itself, but it often appears next to onto counting in the same problems.

---

Club Membership Problems

💡 Union Size With Overlaps

If three clubs $A,B,C$ each have known size, then the total number of students in at least one club is

$\qquad |A\cup B\cup C| = |A|+|B|+|C| <ul><li>|A\cap B|-|B\cap C|-|C\cap A|</li></ul> + |A\cap B\cap C|$

This can be used to get:

exact totals when intersections are known,

largest possible total by minimizing overlaps,

smallest possible total by maximizing overlaps.

These “largest possible” and “smallest possible” questions are common in olympiad-style counting. ---

When Inclusion-Exclusion Is Not the Best Tool

⚠️ Use the Right Method

Some restriction problems are better solved by a gap method rather than inclusion-exclusion.

Example:

arranging letters so that no two are consecutive

For such problems, first place the unrestricted objects, then choose allowed gaps for the restricted objects.

So inclusion-exclusion is powerful, but not every restriction problem should be forced into it.

---

Minimal Worked Examples

Example 1: Union of three sets If

\qquad |A|=20,\ |B|=18,\ |C|=16

and

\qquad |A\cap B|=7,\ |B\cap C|=6,\ |C\cap A|=5,\ |A\cap B\cap C|=2

then

\qquad |A\cup B\cup C| = 20+18+16-7-6-5+2 = 38

So the union has size

\boxed{38}

. --- Example 2: Onto functions to $\{a,b,c\}$ from a 5-element set

\qquad 3^5 - 3\cdot 2^5 + 3 = 243 - 96 + 3 = 150

So the answer is

\boxed{150}

. --- Example 3: Passwords with at least one letter and one digit Using

26

letters and

10

digits for length

7

passwords: Total passwords:

\qquad 36^7

Subtract:

all-letter passwords: $\qquad 26^7$

all-digit passwords: $\qquad 10^7$

Hence the count is

\qquad 36^7 - 26^7 - 10^7

::: ---

Common Mistakes

⚠️ Avoid These Errors

❌ Forgetting to add back the triple intersection in the three-set formula.

❌ Subtracting “bad cases” that overlap, but never correcting the overlap.

❌ Using inclusion-exclusion when a gap method is simpler.

❌ Counting onto functions by subtracting only one missing image class.

❌ Forgetting that “at least one from each class” usually needs alternating subtraction and addition.

---

CMI Strategy

💡 How to Attack Inclusion-Exclusion Problems

Decide what the “bad” conditions are.

Count total objects first.

Count objects violating one condition.

Count overlaps of bad conditions.

Use alternating signs carefully.

Simplify only after the structure is correct.

If the problem is about adjacency, first ask whether the gap method is better.

---

Practice Questions

:::question type="MCQ" question="If

|A|=12

|B|=15

, and

|A\cap B|=4

, then

|A\cup B|

equals" options=["

23

","

27

","

31

","

19

"] answer="A" hint="Use the two-set formula." solution="We use

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

\qquad |A\cup B|=12+15-4=23

Hence the correct option is

\boxed{A}

." ::: :::question type="NAT" question="How many onto functions are there from a

4

-element set to a

2

-element set?" answer="14" hint="Subtract the two constant functions from all functions." solution="Total functions:

\qquad 2^4=16

Non-onto functions are the two constant functions, one using only the first value and one using only the second. Hence the number of onto functions is

\qquad 16-2=14

So the answer is

\boxed{14}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["

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

","

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

for all sets","The number of onto functions from an

n

-element set to a

3

-element set is

3^n-3\cdot 2^n+3

","Inclusion-exclusion is often used with complement counting"] answer="A,C,D" hint="One option is missing the triple-intersection term." solution="1. True.

False. The correct formula also has

+|A\cap B\cap C|

True.

Hence the correct answer is

\boxed{A,C,D}

." ::: :::question type="SUB" question="Prove that the number of onto functions from an

n

-element set to

\{a,b,c\}

3^n-3\cdot 2^n+3

." answer="

3^n-3\cdot 2^n+3

" hint="Use inclusion-exclusion on the missing images." solution="Total functions from an

n

-element set to

\{a,b,c\}

are

\qquad 3^n

. Now subtract functions that miss at least one value:

miss $a$ : $\qquad 2^n$

miss $b$ : $\qquad 2^n$

miss $c$ : $\qquad 2^n$

So subtract

\qquad 3\cdot 2^n

. But functions using only one symbol were subtracted too many times. There are exactly

3

such functions:

all values are $a$

all values are $b$

all values are $c$

So we add back

3

. Hence the number of onto functions is

\qquad 3^n-3\cdot 2^n+3

." ::: ---

Summary

❗ Key Takeaways for CMI

Inclusion-exclusion corrects overcounting by alternating subtraction and addition.

For two sets, subtract the overlap once.

For three sets, subtract pairwise overlaps and add back the triple overlap.

Onto functions are counted naturally by excluding functions that miss one or more images.

Password and string problems with “at least one from each class” are classic inclusion-exclusion applications.

The hardest part is usually identifying the bad conditions correctly.

---

💡 Next Up

Proceeding to Double counting.

---

Part 4: Double counting

Double Counting

Overview

Double counting is one of the most elegant methods in combinatorics. The principle is to count the same set or quantity in two different ways and then equate the results. This often converts a difficult counting problem into a simple identity. In CMI-style problems, double counting is used not only for formulas, but also for proving relations and extracting hidden structure. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Recognise when a set or quantity can be counted in two ways.

Build a valid double-counting argument.

Use double counting to prove identities.

Count incidences between two kinds of objects.

Avoid invalid arguments where the two counts are not counting the same thing.

---

Core Idea

📖 Double Counting

Suppose a quantity $Q$ can be counted in two different correct ways. Then the two answers must be equal.

Symbolically,

$\qquad Q = Q$

but with two different expressions on the two sides.

This gives a useful identity or formula.

The challenge is to identify the correct quantity to count. ---

Most Common Model: Counting Incidences

📐 Incidence Counting

Suppose we have two types of objects:

objects of type $A$

objects of type $B$

and we count the number of incidences between them.

Then we may count:

first by fixing an object of type $A$

then by fixing an object of type $B$

Both counts must agree.

Examples:

student–club memberships

edge–endpoint incidences in a graph

committee–member incidences

subset–element incidences

---

Classic Combinatorial Identity

📐 A Standard Double Counting Identity

Count the number of pairs $(S,x)$ such that:

$S$ is a $k$ -element subset of an $n$ -element set

$x\in S$

Count in two ways:

Way 1: choose the set first, then the element inside it

\qquad \binom{n}{k}\cdot k

Way 2: choose the element first, then complete the set

\qquad n\binom{n-1}{k-1}

Hence,

\qquad k\binom{n}{k}=n\binom{n-1}{k-1}

---

Why Double Counting Works

❗ The Same Quantity Must Be Counted

A double-counting proof is valid only if both sides count exactly the same collection of objects.

Not similar objects. Not related objects. The same objects.

⚠️ Most Common Error

A wrong double-counting argument often happens when:

the left side counts one structure

the right side counts a slightly different structure

So always state clearly: what exactly is being counted?

---

Standard Situations for Double Counting

📐 Where It Appears Often

Counting pairs $(x,S)$ where $x$ belongs to $S$

Counting edge-endpoint incidences in a graph

Counting committee-member or object-container incidences

Proving algebraic identities involving binomial coefficients

Summing row counts and column counts of a matrix of $0$ 's and $1$ 's

---

Minimal Worked Examples

Example 1 Prove

\qquad \sum_{k=0}^{n}\binom{n}{k}=2^n

Count subsets of an

n

-element set in two ways.

Directly: each element is either included or not included, so there are $\qquad 2^n$ subsets.

By size: the number of subsets with exactly $k$ elements is $\qquad \binom{n}{k}$ .

So,

\qquad \sum_{k=0}^{n}\binom{n}{k}=2^n

--- Example 2 In any graph, the sum of all vertex degrees equals twice the number of edges. Count edge-endpoint incidences.

Each edge contributes $2$ incidences.

A vertex of degree $d$ contributes $d$ incidences.

Hence,

\qquad \sum \deg(v)=2|E|

---

Incidence Table View

💡 A Useful Way to Think

Imagine a table whose rows are objects of type $A$ and columns are objects of type $B$ .

Write $1$ when there is an incidence, and $0$ otherwise.

Then:

summing rows gives one count

summing columns gives another count

Both must give the same total number of

1

's.

This is a very clean mental model for double counting. ---

How to Build a Double Count

💡 Step-by-Step

Decide what set of objects, pairs, or incidences to count.

Count it one way using one feature.

Count it another way using a different feature.

Equate the two expressions.

Simplify the result.

---

Common Patterns

📐 Patterns to Recognise

Count pairs $(i,S)$ with $i\in S$

Count selections with a distinguished chosen element

Count total appearances of elements across subsets

Count graph incidences

Count a set by grouping in two different ways

---

Common Mistakes

⚠️ Avoid These Errors

❌ Counting different objects on the two sides

✅ State exactly what is being counted

❌ Forgetting multiplicity

✅ One object may contribute several incidences

❌ Proving a formula without explaining the combinatorial meaning

✅ Name the counted structure first

❌ Mixing ordered and unordered choices

✅ Be consistent about whether order matters

---

CMI Strategy

💡 How to Spot a Double Count

Ask:

Is there a natural set of pairs $(A,B)$ here?

Can the quantity be grouped by one variable or the other?

Is there an identity with binomial coefficients hiding in the background?

Is there a graph or incidence interpretation available?

If yes, try double counting before doing algebra.

---

Practice Questions

:::question type="MCQ" question="In a valid double-counting proof, the two expressions must count" options=["equal numbers by luck","the same set of objects in two ways","different objects of equal size","approximate values"] answer="B" hint="This is the central principle of the method." solution="A double-counting argument works only when both expressions count exactly the same set or quantity, but in two different ways. Therefore the correct option is

\boxed{B}

." ::: :::question type="NAT" question="How many incidences are contributed by a graph with

7

edges when counted edge-wise?" answer="14" hint="Each edge has two endpoints." solution="Each edge contributes exactly

2

edge-endpoint incidences. So a graph with

7

edges contributes

\qquad 2\cdot 7=14

incidences. Therefore the answer is

\boxed{14}

." ::: :::question type="MSQ" question="Which of the following are standard settings for double counting?" options=["counting pairs

(x,S)

with

x\in S

","counting graph edge-endpoint incidences","counting the same family by size and also directly","blindly splitting into overlapping cases"] answer="A,B,C" hint="Double counting requires two valid counts of the same quantity." solution="1. True. This is a standard subset-incidence setup.

True. This gives the handshaking identity.

True. Many binomial identities arise this way.

False. Overlapping casework is not double counting by itself.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Prove using double counting that

k\binom{n}{k}=n\binom{n-1}{k-1}

." answer="Both sides count pairs

(S,x)

where

S

is a

k

-subset of an

n

-set and

x\in S

." hint="Count the same pair-set in two different orders." solution="Consider all pairs

(S,x)

such that:

$S$ is a $k$ -element subset of an $n$ -element set

$x\in S$

Count these pairs in two ways. First way: choose the set

S

first, then choose

x

inside it. This gives

\qquad \binom{n}{k}\cdot k

Second way: choose the element

x

first. There are

n

choices for

x

. Then choose the remaining

k-1

elements of

S

from the remaining

n-1

elements. This gives

\qquad n\binom{n-1}{k-1}

Since both expressions count the same set of pairs, they are equal. Hence

\qquad k\binom{n}{k}=n\binom{n-1}{k-1}

" ::: ---

Summary

❗ Key Takeaways for CMI

Double counting means counting the same quantity in two valid ways.

The most useful setup is incidence counting.

Many binomial identities are easiest through double counting.

Always define clearly what is being counted.

The method is powerful because it converts structure into an identity.

---

Chapter Summary

❗ Inclusion-exclusion and double counting — Key Points

Complement Counting: Effectively determine the size of a set by subtracting the size of its complement from the total universe, particularly useful for "at least one" scenarios or when direct counting is complex.

Inclusion-Exclusion Principle (IEP): Precisely count the union of sets by summing individual set sizes, then subtracting the sizes of all pairwise intersections, adding the sizes of all triple intersections, and so on, to correct for initial over- or under-counting.

General IEP Formula: For $N$ sets $A_1, \dots, A_N$ , the size of their union is given by

\left| \bigcup_{i=1}^N A_i \right| = \sum_{i} |A_i| - \sum_{i<j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \dots + (-1)^{N-1} |A_1 \cap \dots \cap A_N|

Double Counting (Combinatorial Proof): A powerful technique to prove combinatorial identities by counting the same set of objects or the same property of a configuration in two distinct ways, leading to an equality.

Careful Set Definition: Success in applying these principles hinges on precisely defining the sets involved, their properties, and their intersections, to ensure accurate counting.

Applications: These principles are fundamental for solving a wide range of problems in combinatorics, including those involving divisibility, derangements, permutations with restrictions, and various arrangements of objects.

---

Chapter Review Questions

:::question type="MCQ" question="How many integers between 1 and 100 (inclusive) are divisible by 2 or 3 or 5?" options=["70","72","74","76"] answer="74" hint="Use the Inclusion-Exclusion Principle for three sets. Let $A_2$ be the set of integers divisible by 2, $A_3$ by 3, and $A_5$ by 5." solution="Let $S = \{1, 2, \dots, 100\}$ .
Let $A_2$ be the set of numbers in $S$ divisible by 2. $|A_2| = \lfloor 100/2 \rfloor = 50$ .
Let $A_3$ be the set of numbers in $S$ divisible by 3. $|A_3| = \lfloor 100/3 \rfloor = 33$ .
Let $A_5$ be the set of numbers in $S$ divisible by 5. $|A_5| = \lfloor 100/5 \rfloor = 20$ .

$A_2 \cap A_3 \cap A_5$ (divisible by 30): $|A_2 \cap A_3 \cap A_5| = \lfloor 100/30 \rfloor = 3$ .

By the Inclusion-Exclusion Principle:
$|A_2 \cup A_3 \cup A_5| = |A_2| + |A_3| + |A_5| - (|A_2 \cap A_3| + |A_2 \cap A_5| + |A_3 \cap A_5|) + |A_2 \cap A_3 \cap A_5|$
$= 50 + 33 + 20 - (16 + 10 + 6) + 3$
$= 103 - 32 + 3 = 74$ .
The number of integers is 74."
:::

:::question type="NAT" question="A group of 7 friends is to be seated in a row. In how many ways can they be seated if two specific friends, Alice and Bob, must NOT sit next to each other?" answer="3600" hint="Use complement counting. First, find the total number of arrangements without any restrictions. Then, find the number of arrangements where Alice and Bob do sit together." solution="Total number of ways to seat 7 friends in a row is $7! = 5040$ .

Now, consider the case where Alice and Bob do sit next to each other. Treat Alice and Bob as a single block (AB).
There are now effectively 6 items to arrange: (AB), C, D, E, F, G. This can be done in $6!$ ways.
Within the (AB) block, Alice and Bob can swap positions (AB or BA), so there are $2!$ ways for them to sit together.
So, the number of ways Alice and Bob sit together is $6! \times 2! = 720 \times 2 = 1440$ .

The number of ways Alice and Bob must NOT sit next to each other is the total arrangements minus the arrangements where they do sit together:
$5040 - 1440 = 3600$ ."
:::

:::question type="MCQ" question="Consider the identity $k \binom{n}{k} = n \binom{n-1}{k-1}$ for $n \ge k \ge 1$ . Which of the following scenarios best illustrates a combinatorial proof of this identity using double counting?" options=["Counting committees of $k$ members from $n$ people and a president from the remaining $n-k$ people.","Counting ways to select a captain and $k-1$ team members from $n$ players.","Counting permutations of $n$ objects taken $k$ at a time.","Counting subsets of size $k$ from a set of $n$ elements."] answer="Counting ways to select a captain and $k-1$ team members from $n$ players." hint="Think about how to form a group of $k$ people with one designated leader. Count this in two different ways." solution="The identity $k \binom{n}{k} = n \binom{n-1}{k-1}$ counts the number of ways to choose a committee of $k$ members from $n$ people and then select a president from that committee.

Method 1 (LHS):
First, choose a committee of $k$ members from $n$ people. There are $\binom{n}{k}$ ways to do this.
Then, from these $k$ chosen members, select one to be the president. There are $k$ ways to do this.
Total ways = $k \binom{n}{k}$ .

Method 2 (RHS):
First, choose one person from the $n$ people to be the president. There are $n$ ways to do this.
Then, choose the remaining $k-1$ members for the committee from the remaining $n-1$ people. There are $\binom{n-1}{k-1}$ ways to do this.
Total ways = $n \binom{n-1}{k-1}$ .

Since both methods count the same set of configurations (a committee of $k$ with a designated president), the expressions must be equal. The option 'Counting ways to select a captain and $k-1$ team members from $n$ players' perfectly describes this scenario, where the captain is the president and the $k-1$ team members complete the committee."
:::

---

What's Next?

💡 Continue Your CMI Journey

Having mastered the fundamental techniques of counting through cases, complement counting, inclusion-exclusion, and double counting, you are well-equipped to tackle more advanced combinatorial challenges. These principles form the bedrock for understanding topics such as the Pigeonhole Principle, which often complements inclusion-exclusion in existence proofs, and Generating Functions, which provide an algebraic framework for solving complex counting problems, especially those involving partitions and compositions. Furthermore, a solid grasp of these concepts is crucial for approaching various problems in Graph Theory, where counting paths, cycles, and specific substructures is a common task, and in Discrete Probability, where precise enumeration of outcomes is essential.

Inclusion-exclusion and double counting

Inclusion-exclusion and double counting

Chapter Contents

| Topic |

Part 1: Counting through cases

Counting through Cases

Overview

Learning Objectives

Core Idea

What Makes a Good Case Split?

Standard Reasons to Split into Cases

Addition and Multiplication Principles Together

Minimal Worked Examples

When Cases Are Better Than Formulas

Complement vs Cases

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 2: Complement counting

Complement Counting

Overview

Learning Objectives

Core Idea

Standard Patterns

Why It Works Well

Standard Examples of Complement Choice

Minimal Worked Examples

Relation with Inclusion-Exclusion

Common Traps

CMI Strategy

Practice Questions

Summary

Part 3: Inclusion-exclusion principle

Inclusion-Exclusion Principle

Overview

Learning Objectives

Core Formulas

General Pattern

Counting With Complements

Onto Functions

Password and String Problems

Exact Distribution Questions

Club Membership Problems

When Inclusion-Exclusion Is Not the Best Tool

Minimal Worked Examples

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 4: Double counting

Double Counting

Overview

Learning Objectives

Core Idea

Most Common Model: Counting Incidences

Classic Combinatorial Identity

Why Double Counting Works

Standard Situations for Double Counting

Minimal Worked Examples

Incidence Table View

How to Build a Double Count

Common Patterns

Common Mistakes

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Combinatorics and Discrete Mathematics

Binomial methods

Recurrence relations

Counting principles

Pigeonhole principle

More Resources

Study Notes

Short Notes