Skip to main content

Counting and Combinatorial Proof Lab

Retrieval Prompts​

  1. State the product, sum, and division rules from memory.
  2. Explain the difference between a permutation count and a combination count.
  3. Define a combinatorial proof in one precise sentence.

Compare and Distinguish​

Separate these clearly:

  • ordered selection versus unordered selection
  • direct counting versus complement counting
  • algebraic proof of an identity versus combinatorial proof of an identity

Common Mistake Check​

Explain the error in each move:

  1. "At least one forbidden feature" was counted by adding separate cases with no overlap correction.
  2. "n! counts all arrangements, so it works even when letters repeat."
  3. "C(n,k) and P(n,k) are basically interchangeable for large n."

Mini Application​

Complete all three tasks for each problem:

  1. name the first counting move
  2. write the exact counted set
  3. compute only after the setup is justified

Problems:

  1. Count 5-bit strings with exactly three 1s.
  2. Count committees of size 4 chosen from 9 people with one designated chair.
  3. Give a combinatorial proof of sum_(k=0)^n C(n,k) = 2^n.

Evidence Check​

This page is complete only if your written solutions explain why the setup is correct, not just what the final number is.

Integrated Counting Drill​

Solve these without reaching for formulas first. For each problem, name the rule, define the counted objects, and write one sentence explaining why there is no overcount or undercount.

  1. A password has four lowercase letters followed by two digits. How many passwords are possible if repetition is allowed?
  2. How many length-6 bit strings contain at least one 1?
  3. How many integers from 1 to 200 are divisible by 3 or 5?
  4. Ten people sit in a row. How many ways can Alice and Bo sit next to each other?
  5. How many ways can you choose a 5-person review panel from 12 engineers if 2 specific engineers cannot both be selected?
  6. Prove with a story, not algebra alone, why n * C(n - 1, k - 1) = k * C(n, k).

Remediation prompt: if you wrote only P, C, or a final number, redo the problem and identify whether order matters, repetition is allowed, and whether cases overlap.