The Central Idea
Two finite sets have the same cardinality when their elements can be paired so that every element of each set appears exactly once.
A function
\[ f:A\to B \]is a bijection when it is both injective and surjective.
For finite sets,
\[ \boxed{A\leftrightarrow B\text{ by a bijection} \Longrightarrow |A|=|B|}. \]Counting by Pairing
Suppose set \(A\) is difficult to count directly, but every element of \(A\) can be paired uniquely with an element of an easier set \(B\).
If the pairing is one-to-one and onto, then
\[ |A|=|B|. \]We may therefore count \(B\) instead of \(A\).
A Simple Bijection
Consider the sets
\[ A=\{1,2,3,4\} \]and
\[ B=\{a,b,c,d\}. \]Define
\[ 1\leftrightarrow a,\qquad 2\leftrightarrow b,\qquad 3\leftrightarrow c,\qquad 4\leftrightarrow d. \]Every element of each set appears in exactly one pair.
Therefore,
\[ \boxed{|A|=|B|=4}. \]Why Bijections Are More Than Matching Labels
In useful applications, the objects in the two sets may look completely different.
The power of a bijection is that it translates one type of object into another while preserving uniqueness.
A difficult family of configurations may correspond exactly to a familiar family of subsets, strings, paths, or functions.
Example: Subsets and Binary Strings
Let
\[ S=\{1,2,\ldots,n\}. \]Every subset \(A\subseteq S\) can be encoded by a binary string of length \(n\).
In position \(i\), write
\[ 1 \]if \(i\in A\), and
\[ 0 \]if \(i\notin A\).
This correspondence is bijective.
Why the Subset Encoding Is a Bijection
Every subset produces exactly one binary string.
Every binary string produces exactly one subset.
Therefore, the power set of an \(n\)-element set and the set of binary strings of length \(n\) have the same size.
Since there are
\[ 2^n \]binary strings of length \(n\),
\[ \boxed{|\mathcal P(S)|=2^n}. \]Example: Even and Odd Subsets
Let \(S\) be a nonempty finite set.
Fix one element
\[ x\in S. \]Pair each subset \(A\subseteq S\) with the subset obtained by toggling whether \(x\) belongs to it.
If \(x\in A\), remove it. If \(x\notin A\), add it.
This changes the parity of the subset size.
A Parity Bijection
The toggling map pairs every even-sized subset with exactly one odd-sized subset and vice versa.
Therefore, a nonempty \(n\)-element set has equally many even-sized and odd-sized subsets.
Since the total number of subsets is \(2^n\),
\[ \boxed{\#(\text{even subsets}) = \#(\text{odd subsets}) = 2^{n-1}}. \]Constructing a Useful Bijection
A good bijection should satisfy three practical requirements:
- every source object has an image;
- different source objects produce different images;
- every target object is produced.
In many problems, the easiest way to verify these conditions is to describe a reversible transformation.
Reversibility Is a Strong Signal
If a transformation can be undone uniquely, it is often a bijection.
Suppose
\[ T:A\to B \]has a well-defined inverse transformation
\[ T^{-1}:B\to A. \]Then \(T\) is bijective.
Example: Complementing Subsets
Let \(S\) have \(n\) elements.
Map each \(k\)-element subset \(A\) to its complement
\[ S\setminus A. \]The complement has
\[ n-k \]elements.
Complementing twice returns the original subset, so the map is bijective.
Therefore,
\[ \boxed{\binom{n}{k}=\binom{n}{n-k}}. \]Bijections Can Prove Identities
An algebraic identity involving counting expressions can often be proved by showing that both sides count two bijectively equivalent collections.
Such a proof explains why the quantities are equal, not merely that an algebraic manipulation transforms one expression into the other.
What Is Double Counting?
Double counting means counting the same finite set in two different ways.
If one method gives
\[ X \]and another method gives
\[ Y, \]then both count the same set, so
\[ \boxed{X=Y}. \]The Main Double-Counting Pattern
A typical double-counting argument has three steps:
- define one collection of objects;
- count that collection in one way;
- count the same collection in a different way.
Equating the two counts produces an identity or structural relationship.
Example: Handshakes
Suppose \(n\) people each shake hands with every other person exactly once.
One way to count handshakes is to choose the pair of people involved:
\[ \boxed{\binom{n}{2}}. \]Another approach counts the number of handshakes from individual people.
Why Dividing by Two Appears
Each person shakes hands with
\[ n-1 \]others.
Summing over all \(n\) people gives
\[ n(n-1). \]But every handshake was counted once from each participant, so every handshake appears twice.
Therefore,
\[ \boxed{\binom{n}{2}=\frac{n(n-1)}{2}}. \]Incidence Counting
Double counting often uses incidences.
An incidence is a relationship between two kinds of objects.
Examples include:
- a student belonging to a club;
- a vertex touching an edge;
- a point lying on a line;
- a person participating in an event;
- a subset containing a particular element.
Count Incidences from Either Side
Suppose a relation connects objects in sets \(A\) and \(B\).
Count all related pairs
\[ (a,b) \]by summing over the elements of \(A\), then count them again by summing over the elements of \(B\).
The two totals must agree.
Example: Students and Clubs
Suppose a school has several clubs.
Let
\[ I=\{(\text{student},\text{club}): \text{the student belongs to the club}\}. \]We can count \(|I|\) by summing the number of clubs joined by each student.
We can also count \(|I|\) by summing the membership sizes of all clubs.
Therefore,
\[ \boxed{ \sum_{\text{students}}(\text{clubs joined}) = \sum_{\text{clubs}}(\text{members}) }. \]The Handshaking Lemma
In a finite undirected graph, count vertex-edge incidences.
Each vertex contributes its degree, so the total number of incidences is
\[ \sum_{v\in V}\deg(v). \]Each edge has exactly two endpoints, so the same incidence set has size
\[ 2|E|. \]Therefore,
\[ \boxed{\sum_{v\in V}\deg(v)=2|E|}. \]A Consequence: Even Degree Sum
Since
\[ 2|E| \]is even, the sum of the vertex degrees of any finite undirected graph is even.
This is an immediate consequence of double counting edge endpoints.
Counting Subset-Element Incidences
Let \(S\) be an \(n\)-element set.
Consider pairs
\[ (A,x) \]where \(A\subseteq S\) and \(x\in A\).
We can count these incidences in two different ways.
First Count: By Subset Size
There are
\[ \binom{n}{k} \]subsets of size \(k\), and each contributes \(k\) incidences.
Therefore,
\[ |I| = \sum_{k=0}^{n}k\binom{n}{k}. \]Second Count: By Distinguished Element
Choose the distinguished element \(x\) first.
There are
\[ n \]choices for \(x\).
Once \(x\) is included, each of the remaining \(n-1\) elements may be either included or excluded.
Therefore,
\[ |I|=n2^{n-1}. \]A Double-Counting Identity
Equating the two counts gives
\[ \boxed{ \sum_{k=0}^{n}k\binom{n}{k} = n2^{n-1} }. \]The identity follows because both sides count the same subset-element incidences.
Pascal's Identity by Double Counting
Let \(S\) be an \(n\)-element set, and fix one distinguished element \(x\).
Count the \(k\)-element subsets of \(S\).
There are
\[ \binom{n}{k} \]in total.
Now split them into two disjoint cases.
Subsets That Contain or Avoid \(x\)
A \(k\)-element subset either contains \(x\) or does not contain \(x\).
If it contains \(x\), choose the remaining \(k-1\) elements from the other \(n-1\):
\[ \binom{n-1}{k-1}. \]If it does not contain \(x\), choose all \(k\) elements from the other \(n-1\):
\[ \binom{n-1}{k}. \]Therefore,
\[ \boxed{ \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k} }. \]Counting Ordered Pairs of Distinct Elements
Let \(S\) have \(n\) elements.
Count ordered pairs
\[ (a,b) \]with \(a\neq b\).
Sequentially, there are
\[ n(n-1) \]such pairs.
From Ordered Pairs to Unordered Pairs
Every unordered two-element subset
\[ \{a,b\} \]corresponds to exactly two ordered pairs:
\[ (a,b) \]and
\[ (b,a). \]Therefore,
\[ n(n-1)=2\binom{n}{2}, \]so
\[ \boxed{\binom{n}{2}=\frac{n(n-1)}{2}}. \]Bijection versus Double Counting
The two methods are related but distinct.
A bijection directly pairs two sets of objects.
Double counting defines one set and computes its size in two ways.
Some arguments can be expressed naturally in either language.
Example: Choosing a Committee with a Chair
From \(n\) people, count committees of size \(k\) with one committee member designated as chair.
First method: choose the committee, then choose its chair.
\[ \binom{n}{k}k. \]Second Count: Choose the Chair First
Choose the chair from all \(n\) people:
\[ n. \]Then choose the remaining \(k-1\) committee members from the other \(n-1\):
\[ \binom{n-1}{k-1}. \]Therefore,
\[ \boxed{ k\binom{n}{k} = n\binom{n-1}{k-1} }. \]Why the Committee Identity Works
Both sides count exactly the same objects:
\[ (\text{\(k\)-person committee},\text{designated chair}). \]The difference is only the order in which the choices are organized.
Double Counting by Rows and Columns
Suppose a finite table contains marked cells.
Count the marked cells by summing the number of marks in each row.
Then count them again by summing the number of marks in each column.
Therefore,
\[ \boxed{ \sum(\text{row counts}) = \sum(\text{column counts}) }. \]Matrix Interpretation
If a \(0\)-\(1\) matrix records a relation, then each \(1\) represents an incidence.
The total number of \(1\)s can be found by summing row totals or by summing column totals.
This is double counting in matrix form.
Double Counting in Networks
In a network, one side of a count may sum local information while the other counts global structures.
The handshaking lemma is the standard example:
\[ \text{sum of local degrees} = 2(\text{number of edges}). \]This local-global relationship is a recurring pattern in discrete mathematics.
Counting Memberships in a Family of Sets
Suppose
\[ A_1,A_2,\ldots,A_m \]are subsets of a finite universe \(U\).
Count incidences
\[ (x,A_i) \]where \(x\in A_i\).
Summing over the sets gives
\[ \sum_{i=1}^{m}|A_i|. \]Summing over the elements gives the total number of memberships each element has across the family.
A Weighted View
Double counting often turns a sum of local multiplicities into a structural total.
An object that participates in several incidences contributes once for each incidence.
Careful control of these multiplicities is essential.
Many-to-One Correspondences Need Adjustment
Not every useful correspondence is bijective.
If every target object corresponds to exactly \(r\) source objects, then
\[ |A|=r|B|. \]Therefore,
\[ \boxed{|B|=\frac{|A|}{r}}. \]This is the logic behind dividing ordered pairs by \(2\) to count unordered pairs.
Example: Cyclic Arrangements
Suppose a collection of linear representations describes the same cyclic arrangement in exactly \(n\) different rotations.
If there are \(L\) linear representations and every cyclic arrangement has exactly \(n\) such representations, then
\[ \boxed{\text{cyclic arrangements}=\frac{L}{n}}. \]Later counting lessons will develop this type of symmetry correction in more detail.
Common Error: Pairing Without Proving Uniqueness
A proposed correspondence is not a bijection merely because every source object is assigned somewhere.
Different source objects must not collapse to the same target object unless the counting argument explicitly accounts for that multiplicity.
Common Error: Missing Target Objects
A one-to-one map need not be onto.
To use a bijection to prove equal cardinalities, every target object must be reached.
Common Error: Counting Different Sets
In double counting, both calculations must count exactly the same collection of objects.
If one method includes objects that the other excludes, the resulting equation is invalid.
Common Error: Ignoring Multiplicity
In the handshake problem, summing individual handshakes counts each handshake twice.
Forgetting this multiplicity would produce
\[ n(n-1) \]instead of
\[ \frac{n(n-1)}{2}. \]Double counting requires knowing how many times each object appears in each count.
Common Error: Assuming a Correspondence Is Reversible
A transformation that loses information may fail to be injective.
A strong verification question is:
Given the target object, can I reconstruct the original source object uniquely?
If not, the map may not be a bijection.
A Reliable Procedure for Bijections
- Define the source set \(A\).
- Define the target set \(B\).
- Describe the transformation \(A\to B\).
- Show that every source object has exactly one image.
- Show that distinct source objects have distinct images.
- Show that every target object has a preimage.
- Conclude that \(|A|=|B|\).
A Reliable Procedure for Double Counting
- Define one finite set of objects or incidences.
- Count it using one organizational viewpoint.
- Count the same set using a different viewpoint.
- Track any multiplicities carefully.
- Equate the two expressions.
- Interpret or simplify the resulting identity.
Example: Full Bijection Workflow
Show that the number of \(k\)-element subsets of an \(n\)-element set equals the number of \((n-k)\)-element subsets.
Source set:
\[ A=\{\text{\(k\)-element subsets of }S\}. \]Target set:
\[ B=\{\text{\((n-k)\)-element subsets of }S\}. \]Map each subset \(X\) to its complement
\[ S\setminus X. \]Complementing twice returns \(X\), so the transformation is reversible.
Therefore,
\[ \boxed{\binom{n}{k}=\binom{n}{n-k}}. \]Example: Full Double-Counting Workflow
Count pairs
\[ (A,x) \]where \(A\subseteq S\), \(|S|=n\), and \(x\in A\).
By subset size:
\[ \sum_{k=0}^{n}k\binom{n}{k}. \]By choosing \(x\) first:
\[ n2^{n-1}. \]Therefore,
\[ \boxed{ \sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1} }. \]Practice 1: Complement Bijection
Explain why the number of \(3\)-element subsets of a \(10\)-element set equals the number of \(7\)-element subsets.
Practice 2: Binary Encoding
How many subsets does a \(6\)-element set have? Use the bijection with binary strings.
Practice 3: Handshakes
If \(12\) people each shake hands with every other person exactly once, how many handshakes occur?
Practice 4: Graph Degrees
A finite undirected graph has \(15\) edges. What is the sum of all vertex degrees?
Practice 5: Committee with a Chair
From \(8\) people, count \(4\)-person committees with one member designated as chair in two ways.
Practice 6: Pascal's Identity
Use a distinguished element to explain why
\[ \binom{9}{4} = \binom{8}{3} + \binom{8}{4}. \]Practice 7: Student-Club Incidences
Suppose \(20\) students each belong to exactly \(3\) clubs. How many student-club incidences are there?
Practice 8: Club Membership Totals
If the same incidence set from Practice 7 is distributed among \(5\) clubs, what must the sum of the five club membership counts equal?
Practice 9: Ordered and Unordered Pairs
How many unordered pairs can be formed from \(14\) distinct objects?
Practice 10: Identify the Error
A student proposes a bijection from all binary strings of length \(4\) to all binary strings of length \(3\) by deleting the last bit. Why is this not a bijection?
Practice Answers
Practice 1
Map each \(3\)-element subset to its complement. The complement contains \(10-3=7\) elements, and complementing again recovers the original set.
\[ \boxed{\binom{10}{3}=\binom{10}{7}}. \]Practice 2
Every subset corresponds to one binary string of length \(6\), and each position has \(2\) choices:
\[ \boxed{2^6=64}. \]Practice 3
\[ \boxed{\binom{12}{2}=\frac{12\cdot11}{2}=66}. \]Practice 4
By the handshaking lemma,
\[ \sum_{v\in V}\deg(v)=2|E|. \]Therefore,
\[ \boxed{2(15)=30}. \]Practice 5
Choose the committee, then the chair:
\[ \binom{8}{4}\cdot4. \]Or choose the chair first, then the other three members:
\[ 8\binom{7}{3}. \]Both equal
\[ \boxed{280}. \]Practice 6
Count \(4\)-element subsets of a \(9\)-element set by whether they contain one distinguished element.
Containing it:
\[ \binom{8}{3}. \]Avoiding it:
\[ \binom{8}{4}. \]Therefore,
\[ \boxed{\binom{9}{4}=\binom{8}{3}+\binom{8}{4}}. \]Practice 7
\[ \boxed{20\cdot3=60}. \]Practice 8
The same incidence set is being counted from the club side, so the sum of the five club membership counts must also equal
\[ \boxed{60}. \]Practice 9
There are
\[ 14\cdot13 \]ordered pairs of distinct objects, and each unordered pair corresponds to two orders.
\[ \boxed{\frac{14\cdot13}{2}=91}. \]Practice 10
Different length-\(4\) strings can produce the same length-\(3\) string. For example,
\[ 1010 \]and
\[ 1011 \]both map to
\[ 101. \]The map is not injective, so it is not a bijection.
What to Remember
A bijection proves equal finite cardinalities:
\[ \boxed{A\leftrightarrow B\Longrightarrow |A|=|B|}. \]Double counting proves identities by counting the same finite set twice:
\[ \boxed{\text{first count}=\text{second count}}. \]- Look for reversible transformations when building bijections.
- Verify both uniqueness and completeness of the pairing.
- Define one exact collection before double counting.
- Track multiplicity carefully.
- Use incidences to connect local and global counts.
- Recognize that many combinatorial identities express two views of the same objects.
Where We Go Next
Bijections and double counting exploit structural equivalence. Another foundational strategy divides a problem into mutually exclusive situations and counts each situation separately.
The next lesson, Counting by Cases, develops systematic case decomposition and shows how to ensure that cases are complete and nonoverlapping.