Proof BlocksEnumerative Combinatorics
All proofsProof Blocks
The steps of a proof are mixed up, with a few extra steps that don't belong. Put the right steps in order.
A college study tested this kind of practice. After reading the same notes, students learned about as much as those who wrote proofs from scratch, in about a quarter of the time. Read the study
How Proof Blocks works
- Read the claim at the top. That's what the proof has to show.
- Pick the steps you need. Leave out the ones that don't belong.
- Put your steps in order, top to bottom. Each step should follow from the ones above it.
- Press Check proof. It tells you how many steps from the top are right.
- Stuck? Hint explains where to look next.
This is practice. Finishing an activity doesn't count as mastering the proof. Writing it on your own does.
Write for an integer , and let . Let be the number of even-cardinality subsets of , including the empty subset.
For , construct an explicit bijection from the subsets of to the even-cardinality subsets of . Give its inverse, use it to find , and handle separately. For , show what your map does to and state .
Choose an activity
Join to unlock the full course and save your place.
- Path position 019
Build a parity-fixing bijection from the subsets of to the even-size subsets of , prove its inverse works, use it to count even subsets, treat on its own, and run the map on a small example.
- Path position 015
Build the stars-and-bars bijection between weak compositions and strings of stars and bars, explain how zero parts appear, count distributions of identical counters into labeled trays, and check the cases and .
- Path position 017
Prove the hockey-stick identity by sorting subsets by their largest element and again by telescoping Pascal's identity, then use it on a numerical sum and explain the case .
- Path position 012
Derive the recurrence for by looking at the block that contains , state the boundary values including the empty set, build row from them, and explain the factor .
- Path position 001
Derive the generating function for sequences of positive-size objects, explain why positive size matters, and use it to find the generating function, recurrence and closed formula for tilings with two colors of length-two tile.
5 sample Enumerative Combinatorics Proof Blocks activities are ready.