Combinatorics · step 8 of 13

Double counting & bijective proofs

A double counting proof counts the same collection in two different ways and equates the answers — no algebra required. A bijective proof instead constructs an explicit one-to-one correspondence between two sets, proving they are equal in size. Both give real insight where an algebraic manipulation only gives verification.

Practise double counting & bijective proofs free → All Combinatorics subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Choose the set to countThe identity tells you what: for ΣC(n,k) = 2ⁿ, count all subsets of an n-set.
Count it one wayDirectly — every element is in or out, so 2ⁿ.
Count it another wayBy classifying — group subsets by size, giving ΣC(n,k).
For a bijection, describe the map and its inverseState the map, show it is well defined, and give the inverse explicitly. Both directions are needed.

Worked example

Prove C(n,k) = C(n, n−k) bijectively.

Left side counts the k-element subsets of an n-set S.
Right side counts the (n−k)-element subsets.
Define a map sending each k-subset A to its complement S \ A, which has n − k elements.
The map is its own inverse: complementing twice returns A. So it is a bijection.

Answer. Complementation is a bijection between the two families, so C(n,k) = C(n,n−k) — no algebra needed.

Where marks get dropped

These are the specific errors that cost credit on double counting & bijective proofs questions — QED's rubric penalises each of them separately.

Presenting only one direction of a claimed bijection. You must show the correspondence is one-to-one AND onto, usually by exhibiting the inverse.
Double counting two different sets. Both counts must be of the SAME collection, or the equation is meaningless.
Verifying an identity numerically and calling it a proof. Checking n = 4 is evidence, not a bijection.

Practise this until it is automatic

Unlimited fresh questions

QED generates new double counting & bijective proofs problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Combinatorics mastery is tracked so you know when this is exam-ready.

Double counting & bijective proofs — frequently asked questions

What is the handshake lemma as double counting?

Count edge-endpoints two ways: once per edge (2 each) and once per vertex (its degree). Equating gives Σdeg = 2|E|.

Why prefer a bijective proof?

Because it explains WHY the identity holds. An algebraic verification confirms it; a bijection shows the two sides are literally the same objects relabelled.

How do I prove Pascal’s identity this way?

Count k-subsets of {1,…,n} by whether they contain n. Those that do correspond to (k−1)-subsets of the rest; those that do not are k-subsets of the rest.

The rest of Combinatorics

Counting principles, permutations, combinations. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make double counting & bijective proofs exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →