Skip to main content

Proof BlocksEnumerative Combinatorics

All proofs
ProofAnvil Practice · Enumerative Combinatorics

Proof 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

Write [n]={1,…,n}[n]=\{1,\ldots,n\} for an integer n≥1n\ge1, and let [0]=∅[0]=\varnothing. Let EnE_n be the number of even-cardinality subsets of [n][n], including the empty subset.

For n≥1n\ge1, construct an explicit bijection from the subsets of [n−1][n-1] to the even-cardinality subsets of [n][n]. Give its inverse, use it to find EnE_n, and handle n=0n=0 separately. For n=5n=5, show what your map does to T={1,2,4}T=\{1,2,4\} and state E5E_5.

Opening the proof…

Choose an activity

Join to unlock the full course and save your place.

Honors has roughly twice as many lines to arrange.
  1. Path position 019

    Build a parity-fixing bijection from the subsets of [n−1][n-1] to the even-size subsets of [n][n], prove its inverse works, use it to count even subsets, treat n=0n=0 on its own, and run the map on a small example.

  2. 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 n=0n=0 and k=1k=1.

  3. Path position 017

    Prove the hockey-stick identity ∑j=rn(jr)=(n+1r+1)\sum_{j=r}^{n}\binom jr=\binom{n+1}{r+1} 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 r=0r=0.

  4. Path position 012

    Derive the recurrence for S(n,k)S(n,k) by looking at the block that contains nn, state the boundary values including the empty set, build row n=6n=6 from them, and explain the factor kk.

  5. Path position 001

    Derive the generating function 1/(1−B(x))1/(1-B(x)) 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.