Skip to main content

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

Your work here isn't saved. Refreshing the page starts over.

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.