Day 20 — Story Proofs, Counting Workshop & Gate V

Updated

July 30, 2025

Day 20 — Story Proofs, Counting Workshop & Gate V

Day 56 — Story proofs

Stage V · concept day
Goal: Prove binomial identities by combinatorial stories (double counting and bijections); contrast with algebraic proofs; master Pascal, absorption, Vandermonde, and hockey-stick.

Why this matters

A story proof explains why an identity is true by counting the same set two ways (or exhibiting a bijection). In CS interviews and paper proofs, a one-paragraph combinatorial argument often beats page-long algebra. Algebra still matters for verification; stories give insight and prevent cargo-cult formula use.

Theory

Combinatorial vs algebraic proofs

Style What you do Strength
Algebraic Manipulate factorials, induct, use generating functions Mechanical, rigorous once steps OK
Combinatorial / story Interpret both sides as counting the same family of objects Explains meaning; often shorter
Bijective Explicit invertible map between two sets Strongest “same size” certificate

Good practice: do both for core identities.

Double counting

To prove \(LHS=RHS\):

  1. Describe a set \(S\) of configurations.
  2. Show \(|S|=LHS\) by one classification.
  3. Show \(|S|=RHS\) by another.
  4. Conclude equality.

Bijective proofs

Exhibit \(f:A\to B\) invertible (or describe inverse). Then \(|A|=|B|\).
Example: \(k\)-subsets ↔︎ complements ↔︎ \((n-k)\)-subsets gives \(\binom{n}{k}=\binom{n}{n-k}\).

Pascal’s identity (both proofs)

\[ \binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. \]

Story: \(k\)-subsets of \([n]\); distinguish whether \(n\in S\) or not.
Algebra: Day 50.

Absorption / committee chair

\[ k\binom{n}{k}=n\binom{n-1}{k-1}. \]

Story: committees of \(k\) with a chair from the committee—two counting orders.

Symmetry

\[ \binom{n}{k}=\binom{n}{n-k}. \]

Bijection: \(S\mapsto [n]\setminus S\).

Sum of binomials

\[ \sum_{k=0}^{n}\binom{n}{k}=2^n. \]

Story: LHS subsets by size; RHS each element in/out.

Alternating sum / parity

\[ \sum_{k}(-1)^k\binom{n}{k}=0\quad(n>0). \]

Story: even-sized and odd-sized subsets equally many via \(S\leftrightarrow S\triangle\{x\}\).

Vandermonde

\[ \binom{m+n}{r}=\sum_{k}\binom{m}{k}\binom{n}{r-k}. \]

Story: \(r\)-subsets from \(m\) men + \(n\) women, classified by number of men.

Hockey-stick identity

\[ \sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}. \]

Story: Count \((r+1)\)-subsets of \([n+1]=\{1,2,\ldots,n+1\}\).
Let \(S\) be such a subset; let \(m=\max S\). Then \(m\) ranges from \(r+1\) to \(n+1\), and the remaining \(r\) elements are chosen from \(\{1,\ldots,m-1\}\): \(\binom{m-1}{r}\) ways.
Sum \(\sum_{m=r+1}^{n+1}\binom{m-1}{r}=\sum_{i=r}^{n}\binom{i}{r}\) with \(i=m-1\).
RHS: \(\binom{n+1}{r+1}\). \(\square\)

Algebraic path: Pascal telescope \(\binom{i+1}{r+1}-\binom{i}{r+1}=\binom{i}{r}\), sum both sides.

Parallel sum identity

\[ \sum_{k}k\binom{n}{k}=n2^{n-1}. \]

Story: pick distinguished element in subset: choose element (\(n\)) then any subset of rest (\(2^{n-1}\)).

Block-walking / lattice path stories

\(\binom{a+b}{a}\) paths; Pascal: last step East or North.
Vandermonde: path through a diagonal cut.

When stories fail (honestly)

Some identities (e.g. sophisticated \(q\)-analogs, highly alternating multi-sums) resist simple stories. Algebra and GF remain essential. Prefer stories when both sides clearly count.

Proof hygiene

  • Name the set of objects in the first sentence.
  • “LHS counts by …” / “RHS counts by …”
  • Avoid double-counting within one side unless intentional and corrected.
  • Check small \(n\) numerically first.

Worked examples

Example 1 — Symmetry bijection

Write \(f(S)=[n]\setminus S\); \(f\circ f=\mathrm{id}\); maps \(k\)-sets to \((n-k)\)-sets.

Example 2 — Pascal numeric

\(n=6,k=2\): \(15=10+5\).

Example 3 — Chair

\(n=10,k=3\): \(3\binom{10}{3}=360=10\binom{9}{2}\).

Example 4 — Vandermonde numeric

\(m=n=3,r=3\): \(\binom{6}{3}=20=\sum_k\binom{3}{k}\binom{3}{3-k}\).

Example 5 — Hockey-stick numeric

\(\binom{3}{3}+\binom{4}{3}+\binom{5}{3}+\binom{6}{3}=1+4+10+20=35=\binom{7}{4}\).

Example 6 — Algebraic hockey-stick telescope

\(\binom{i}{r}=\binom{i+1}{r+1}-\binom{i}{r+1}\); sum \(i=r\) to \(n\) telescopes to \(\binom{n+1}{r+1}-\binom{r}{r+1}=\binom{n+1}{r+1}\).

Example 7 — \(\sum\binom{n}{k}^2=\binom{2n}{n}\)

Choose \(n\) people from \(n\) men + \(n\) women: Vandermonde with \(k\) men gives \(\sum\binom{n}{k}\binom{n}{n-k}=\sum\binom{n}{k}^2\).

Example 8 — Bit-string story

Number of length-\(n\) strings with odd parity equals even: \(2^{n-1}\) each—pair flip first bit.

Example 9 — Paths Pascal

Paths to \((n-k,k)\): last step from \((n-k-1,k)\) or \((n-k,k-1)\).

Example 10 — Committee with roles

Number of ways to choose president and \(k-1\) other members: \(n\binom{n-1}{k-1}=\binom{n}{k}k\).

Example 11 — Non-story failure mode

“Both sides equal 6” for specific \(n\) is not a proof of identity for all \(n\).

Example 12 — Injection story for inequality

\(\binom{n}{k}\le 2^n\) because \(k\)-sets inject into all subsets.

Example 13 — Double count edges of \(K_n\)

\(\binom{n}{2}\) vs \(\frac{1}{2}\sum_v\deg(v)\) handshaking—graph Day 59, same method.

Example 14 — Choose then order

\(P(n,k)=\binom{n}{k}k!\): LHS ordered tuples; RHS choose set then permute.

Example 15 — Write a full formal story proof

Theorem. \(\sum_{k=0}^{n}k\binom{n}{k}=n2^{n-1}\).
Proof. Let \(S\) be the set of pairs \((A,x)\) with \(A\subseteq[n]\), \(x\in A\).
Count \(|S|\): for each \(k\), \(\binom{n}{k}\) choices of \(A\) with \(|A|=k\) and \(k\) choices of \(x\): \(\sum k\binom{n}{k}\).
Alternatively: choose \(x\in[n]\) first (\(n\) ways), then \(A\setminus\{x\}\) any subset of \([n]\setminus\{x\}\) (\(2^{n-1}\) ways).
Thus equality. \(\square\)

Exercises

  1. Prove \(\binom{n}{k}=\binom{n}{n-k}\) bijectively.
  2. Prove Pascal combinatorially.
  3. Prove absorption combinatorially.
  4. Prove \(\sum\binom{n}{k}=2^n\) two ways (story + induction).
  5. Prove alternating sum by pairing for \(n>0\).
  6. Prove Vandermonde by story.
  7. Prove hockey-stick by max-element story.
  8. Prove hockey-stick by Pascal telescope.
  9. Prove \(\sum k\binom{n}{k}=n2^{n-1}\) formally as in Ex. 15.
  10. Prove \(\sum\binom{n}{k}^2=\binom{2n}{n}\).
  11. Give a lattice-path proof of Pascal.
  12. Prove \(P(n,k)=\binom{n}{k}k!\) by story.
  13. Combinatorial proof: \(\binom{n}{0}+\binom{n}{1}+\binom{n}{2}+\cdots=\sum_{k\text{ even?}}\) wait—prove even = odd = \(2^{n-1}\).
  14. Story for \(\binom{n+1}{k}=\binom{n}{k}+\binom{n}{k-1}\) (reindex Pascal).
  15. Why is “count the same thing two ways” valid logic? (One paragraph on equinumerosity.)
  16. Algebraic proof of absorption from factorials.
  17. Challenge: combinatorial proof of \(\sum_{k}k(k-1)\binom{n}{k}=n(n-1)2^{n-2}\).
  18. Find a story for \(\binom{2n}{n}/(n+1)\) being integer (Catalan)—interpretations Day 50.
  19. Double-count: number of functions \([k]\to[n]\) vs something? (\(n^k\))—optional.
  20. Write the worst fake story proof for Pascal and mark the flaw.
  21. Hockey-stick application: simplify \(\binom{5}{2}+\binom{6}{2}+\cdots+\binom{20}{2}\).
  22. Prove \(\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}\) by committee story.
  23. CS: story for number of \(n\)-bit strings = number of subsets of flags.
  24. Compare length of algebraic vs story proof for Ex. 22.
  25. Portfolio: pick 3 identities and write exam-quality story proofs.

CS connection

  • Algorithm correctness: counting arguments (amortized, potential) often double-count operations.
  • Hashing analysis: balls-and-bins stories.
  • Coding theory: weight enumerators and identities.
  • Interview signal: story proofs show conceptual mastery beyond memorization.
  • Compiler / SSA / graph: handshaking-style double counts reappear in Stage VI.

Common pitfalls

Pitfall What to do instead
Story that only works for special \(n\) Keep \(n\) general
Hidden overcount on one side Check with small numbers
“Clearly the same” without map Define the bijection
Algebra errors after story Still verify small \(n\)
Confusing \(\sum_i\binom{i}{r}\) limits Hockey-stick bounds careful

Checkpoint

  • Double counting template cold
  • Pascal + absorption + Vandermonde stories
  • Hockey-stick full proof
  • \(\sum k\binom{n}{k}\) formal writeup
  • One bijective proof
  • Exercises 1–15
  • Three identities in personal portfolio

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. Pairing with fixed \(x\).
  2. Choose 2 distinguished ordered members in subset: \(n(n-1)2^{n-2}\).
  3. \(\sum_{i=5}^{20}\binom{i}{2}=\binom{21}{3}-\binom{5}{3}=1330-10=1320\).
  4. Choose \(k\) leaders then \(m-k\) ordinary from rest; or choose \(m\) then \(k\) leaders among them.

Deepening notes

Story proof rubric (self-grade)

Criterion Pass?
Object set \(S\) named in sentence 1
LHS interpretation clear
RHS interpretation clear
No hidden overcount
Checked small \(n\)

Bijection checklist

Define \(f:A\to B\), define \(g:B\to A\), check \(g\circ f=\mathrm{id}_A\) and \(f\circ g=\mathrm{id}_B\)—or argue obvious invertibility carefully.

Hockey-stick memory hook

“Sum a diagonal of Pascal’s triangle to get the next entry off the diagonal.”
\(\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}\).

Extra formal writeups to practice

  1. Symmetry bijection (full).
  2. Pascal distinguished element (full).
  3. Absorption chair (full).
  4. \(\sum k\binom{n}{k}\) pairs (full).
  5. Vandermonde men/women (full).
  6. Hockey-stick max element (full).
  7. \(\sum\binom{n}{k}^2=\binom{2n}{n}\) (full).
  8. \(P(n,k)=\binom{n}{k}k!\) (full).

Anti-patterns

  • “Both sides count ways to choose, QED” without specifying from what.
  • Using a story that assumes \(k\) fixed incorrectly.
  • Algebraic cancellation disguised as a story.

Exam drill block

E1. Story-prove \(\binom{n}{k}=\binom{n}{n-k}\).
E2. Story-prove Pascal.
E3. Story-prove absorption \(k\binom{n}{k}=n\binom{n-1}{k-1}\).
E4. Double-count \(\sum k\binom{n}{k}=n2^{n-1}\).
E5. Vandermonde men/women story for \(\binom{m+n}{r}\).
E6. Hockey-stick: full max-element writeup \(\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}\).
E7. Bijective: even vs odd sized subsets for \(n\ge 1\).
E8. Story for \(P(n,k)=\binom{n}{k}k!\).
E9. True/false: (i) story proofs need \(n\) specific (ii) both sides must count the same set \(S\) (iii) small-\(n\) check is optional fluff.
E10. Write \(\sum\binom{n}{k}^2=\binom{2n}{n}\) as choosing \(n\) from \(n\) red + \(n\) blue.

Mini solutions

E1. Complement map \(A\mapsto S\setminus A\) is a bijection \(k\)-sets ↔︎ \((n-k)\)-sets.
E4. Pick distinguished member first (\(n\)), free subset of rest (\(2^{n-1}\)).
E7. Fix \(x\); toggle membership of \(x\) pairs even/odd.
E9. F; T; F (mandatory sanity).
E10. Vandermonde with \(m=n\), choose \(k\) red and \(n-k\) blue, sum on \(k\).

Portfolio identities (write full proofs offline)

  1. Symmetry
  2. Pascal
  3. Absorption
  4. \(\sum\binom{n}{k}=2^n\)
  5. \(\sum k\binom{n}{k}=n2^{n-1}\)
  6. Vandermonde
  7. Hockey-stick
  8. \(\sum\binom{n}{k}^2=\binom{2n}{n}\)

Synthesis

Story proofs double-count or biject. Name the set \(S\) of objects first; interpret LHS and RHS as two counting procedures on \(S\). Check a small \(n\). Algebra still matters for confidence, but the story is what transfers to new identities.

S1. Full formal hockey-stick from memory.
S2. One original identity with a story (even a simple product).
S3. Cold: absorption + Pascal stories in under two minutes each.

Tomorrow

Day 57 — Counting workshop: mixed hard set spanning product through IE and recurrences; method selection guide.

Day 57 — Counting workshop

Stage V · workshop day
Goal: Solve a mixed hard counting set (product through IE and recurrences); practice method selection; write exam-quality justifications.

Why this matters

Isolated technique drills fail under mixture. Real problems (and Gate V) hide the method. Today is deliberate transfer practice: read the object, pick a tool, justify, sanity-check.

Method selection guide

Clue in the problem Try first
Sequential stages, fixed option counts Product rule
Mutually exclusive types/formats Sum rule / cases
“At least one” / “not all” Complement
Order matters, no rep \(P(n,k)\)
Order irrelevant subset \(\binom{n}{k}\)
Identical items → distinct bins Stars and bars
Overlapping properties Inclusion–exclusion
“Onto” / every bin used Surjections IE
No fixed points Derangements
Last step / recursive structure Recurrence
Both sides of identity Story / double count
Huge answer \(\log_2\) + asymptotic compare

Decision tree (short):

  1. Name the object precisely.
  2. Does order matter in the final object?
  3. Are pieces identical or distinct?
  4. Constraints: none / forbidden / at-least / upper bounds?
  5. Small-\(n\) enumerate if stuck under 2 minutes.
  6. If two methods disagree, diagnose over/under-count.

Warm-up block (timed ~15 min)

W1. Length-5 bit-strings with more ones than zeros.
W2. Anagrams of STATISTICS.
W3. Paths \((0,0)\to(4,3)\) not through \((2,2)\) (complement).
W4. \(x_1+x_2+x_3=10\), \(x_i\ge 0\), \(x_1\le 4\).
W5. \(a_n=2a_{n-1}+3\), \(a_0=1\) closed form.

Workshop problems (mixed hard)

Write object + method + answer for each. Aim for 10–15 complete solutions; rest as stretch.

Block A — Product / sum / complement

A1. License plates: 3 letters + 3 digits; letters not all equal; digits free.
A2. Passwords length 6 from 62 chars with ≥1 letter and ≥1 digit.
A3. Functions \([5]\to[3]\); count non-surjective; count surjective.
A4. IDs: either 2 letters + 4 digits OR 6 digits; letters A–Z, no leading letter restriction.

Block B — Permutations / combinations

B1. From 12 people: president, VP, secretary (distinct).
B2. From 12: unordered committee of 3; committee of 3 with a chair.
B3. Seating 7 at a round table (rotations same); two particular people adjacent.
B4. Grid paths \((0,0)\to(6,4)\); through \((3,2)\).
B5. 5-card hands with all distinct ranks (from 52).

Block C — Stars-bars / IE

C1. Nonnegative solutions \(w+x+y+z=15\).
C2. Positive solutions \(x+y+z=12\).
C3. \(x+y+z=12\), each \(\le 6\).
C4. Integers \(1..300\) divisible by 4, 5, or 6.
C5. Multisets of size 8 from 5 types.

Block D — Binomial / Catalan / story

D1. Coefficient of \(x^4y^6\) in \((x+y)^{10}\).
D2. \(\sum_{k=0}^{n}k\binom{n}{k}\) closed form; story one sentence.
D3. \(C_5\) Catalan; list interpretations (names only).
D4. Prove Pascal by story (rewrite clean).
D5. Hockey-stick: \(\sum_{i=4}^{10}\binom{i}{4}\).

Block E — Recurrences

E1. Tilings of \(n\)-board with 1s and 2s: \(T_6\).
E2. Bit-strings length \(n\) no consecutive 1s: recurrence + \(a_6\).
E3. Solve \(a_n=4a_{n-1}-4a_{n-2}\), \(a_0=1,a_1=4\).
E4. Hanoi \(H_n\) closed form proof by induction.
E5. Merge-sort \(T(n)=2T(n/2)+n\): \(T(16)\) with \(T(1)=0\).

Block F — CS scenarios

F1. Entropy bits of 10-char base32 secrets (\(32^{10}\)).
F2. 8 feature flags, at most 2 enabled.
F3. Hash 7 distinct keys to 5 buckets, no empty bucket.
F4. Protocol: 3-bit type; if type \(<4\), 5-bit payload; else 0 payload—message count.
F5. Secret Santa among 6: derangements.

Block G — Mixed “which method?” rapid fire

For each, write one sentence naming the method before computing.

G1. Number of injective functions \([k]\to[n]\).
G2. Ways to put \(n\) identical balls into \(k\) distinct bins nonempty.
G3. Integers \(1..n\) not divisible by \(2\) or \(3\).
G4. Binary strings length \(n\) with no two consecutive \(1\)s (recurrence name).
G5. Committees of \(k\) from \(n\) with one chair from the committee.
G6. Anagrams of a word with repeated letters.
G7. Onto functions \([n]\to[k]\).
G8. Lattice paths with a barrier (Catalan trigger).

Stretch challenges

S1. Number of surjections \([n]\to[n-1]\).
S2. Lattice paths \((0,0)\to(n,n)\) not above diagonal—\(C_n\) formula application for \(n=4\).
S3. \(x_1+\cdots+x_5=20\), \(0\le x_i\le 7\) full IE.
S4. Exactly 2 fixed points in random sense—count \(\binom{n}{2}!(n-2)\) for \(n=6\).
S5. Story: \(\binom{n}{k}\binom{k}{m}=\binom{n}{m}\binom{n-m}{k-m}\).

Worked solutions (selected)

W1. Length 5: more 1s than 0s means 3,4, or 5 ones: \(\binom{5}{3}+\binom{5}{4}+\binom{5}{5}=10+5+1=16\).

W2. STATISTICS: S3,T3,I2,A1,C1 → \(10!/(3!3!2!)=50400\).

W3. Total \(\binom{7}{3}=35\); through \((2,2)\): \(\binom{4}{2}\binom{3}{1}=6\cdot 3=18\); avoid: \(35-18=17\).

W4. Total \(\binom{12}{2}=66\); \(x_1\ge 5\): \(\binom{7}{2}=21\); answer \(45\).

W5. \(a_n=K\cdot 2^n-3\); \(a_0=1\Rightarrow K=4\); \(a_n=4\cdot 2^n-3=2^{n+2}-3\).

A1. \(26^3 10^3-26\cdot 10^3\) (subtract all letters equal).

A3. Total \(3^5=243\); surj \(\sum(-1)^i\binom{3}{i}(3-i)^5=243-3\cdot 32+3\cdot 1=150\); non-surj \(243-150=93\).

C3. Total \(\binom{14}{2}=91\); one var \(\ge 7\): \(\binom{7}{2}=21\), \(\times 3=63\); two vars \(\ge 7\): \(12-14<0\) wait \(12-14=-2\) empty for sum 12? \(12-7-7=-2\) yes 0. Answer \(91-63=28\).

E3. \((r-2)^2\); \(a_n=(1+n)2^n\).

F5. \(!6=265\).

Self-score rubric

Block Problems Points each Score
A 4 5 /20
B 5 4 /20
C 5 4 /20
D 5 4 /20
E 5 4 /20
F 5 4 /20
Total /120

Convert: \(\ge 90\) strong; \(70\)–\(89\) pass with remediation; \(<70\) rework weak days before Gate V.

For each miss: note which method clue you missed, not only the arithmetic.

Exercises (meta + remaining practice)

  1. Complete all of Block A with full writeups.
  2. Complete Block B.
  3. Complete Block C.
  4. Complete Block D including one formal story proof.
  5. Complete Block E.
  6. Complete Block F.
  7. Attempt S1–S3.
  8. Time yourself: 45 minutes on A+B+C only.
  9. Rewrite your worst solution at exam quality.
  10. Create 3 original problems (one product, one IE, one recurrence) with answer key.
  11. Method guide: add one personal “tells” note.
  12. Compute \(!7\) and \(C_6\).
  13. Password \(62^8-52^8-10^8\) — what policy? (Is it correct?)
  14. Fix: if any, the error in “at least one letter and digit” using only two subtractions for length ≥1.
  15. Paths \((0,0)\to(5,5)\) through \((2,2)\) and \((4,3)\).
  16. \(S(6,3)\) via surjection formula.
  17. Closed form \(a_n=5a_{n-1}-6a_{n-2}\), \(a_0=2,a_1=5\).
  18. Multiset permutations of BOOKKEEPER.
  19. CS: count valid states of a 4-bit register with even parity and not all zero.
  20. Summarize Stage V tools on one handwritten page.
  21. Peer-teach Pascal story in 90 seconds.
  22. Find an online-style “trick” problem and solve without looking.
  23. Challenge: number of integer solutions \(x+y+z=20\), \(x,y,z\ge 0\), \(x\le y\le z\) (stars-bars + symmetry—harder).
  24. Derivation: why \(P(n,k)/k!=\binom{n}{k}\).
  25. Gate prep: list 10 formulas to memorize tonight.

CS connection

Workshop problems F1–F5 are the job. Also: design reviews that ask “how many configs?” deserve the same writeup discipline—object, method, number, \(\log_2\).

Common pitfalls (workshop edition)

Pitfall What to do instead
Jumping to a formula without object Sentence 1: “We count …”
Mixing labeled/unlabeled Teams, tables, partitions
IE sign errors under time pressure Write sign pattern first
Skipping sanity check \(n=2\) listing
Spending 20 min on one hard item Park it; return

Checkpoint

  • Method selection guide usable without notes
  • ≥ 12 workshop problems fully written
  • Self-score ≥ 70/120 or remediation plan
  • One story proof polished
  • One recurrence solved closed form
  • Stage V formula sheet drafted
  • Ready for Gate V conditions

Two personal takeaways:

  1. …
  2. …

Deepening notes

60-minute exam simulation plan

Minutes Task
0–5 Scan all; mark easy
5–35 Blocks A–C
35–50 D–E
50–55 F CS
55–60 Sanity check 3 answers

Method tells (personalize)

Write three “tells” you missed today:

  1. …
  2. …
  3. …

Extra mixed set

X1. \(!5\) and \(C_5\).
X2. Surjections \([5]\to[3]\).
X3. Paths \((0,0)\to(6,6)\) not above diagonal \(=C_6\).
X4. \(a_n=6a_{n-1}-9a_{n-2}\), \(a_0=1,a_1=3\).
X5. \(\{1..100\}\) div by 2,3, or 5.
X6. Multiset rearrangements of COMBINATORICS.
X7. Stars-bars \(x_1+\cdots+x_5=10\), each ≤4.
X8. Bit-strings length 7 no consecutive 1s.

Error log template

# My answer Correct Clue I missed

Fill after scoring.

Full worked stretch S3 sketch

\(x_1+\cdots+x_5=20\), \(0\le x_i\le 7\).
Unrestricted: \(\binom{20+4}{4}=\binom{24}{4}=10626\).
One var ≥8: \(x'=x-8\), sum 12: \(\binom{12+4}{4}=\binom{16}{4}=1820\); ×5 = 9100.
Two vars ≥8: sum 4: \(\binom{4+4}{4}=\binom{8}{4}=70\); \(\binom{5}{2}=10\) pairs → 700.
Three vars ≥8: sum \(-4\) impossible.
Answer: \(10626-9100+700=2226\).

Full worked A2

Length 6 over 62 with ≥1 letter and ≥1 digit: \(62^6-52^6-10^6\) (intersection empty).

Full worked E3

\(a_n=4a_{n-1}-4a_{n-2}=(A+Bn)2^n\); \(a_0=1\Rightarrow A=1\); \(a_1=4\Rightarrow 2(A+B)=4\Rightarrow B=1\); \(a_n=(1+n)2^n\).

Workshop debrief questions

  1. Which block was slowest?
  2. Did you name the object every time?
  3. One overcount you caught mid-solution?
  4. Ready for timed Gate V?

Formula sheet draft (complete before Gate)

Leave space and fill from memory—compare to Days 47–56 theory boxes.

Fully worked extra solutions

B3. Round table 7 people: \((7-1)! = 720\) if rotations same. Two particular adjacent: glue as unit → \(6!\cdot 2/7\)? Standard: fix one person’s position to kill rotation, or \((n-1)!\) total; adjacent: treat pair as block: \(2\cdot(n-2)!\) with one seat fixed, equivalently \(2\cdot 5!=240\) with rotations quotiented as \((7-1)!\) style—write: fix person A; arrange other 6 in \(6!\) then… Clean: rotations of \(n\): \((n-1)!\). Adjacent pair: \(2(n-2)!\) if we fix rotation by \((n-1)!\) vs \(2(n-1)!/n\) wait. Standard answer: \(2\cdot(7-1)!/7 \cdot 7\)? Preferred: fix one unrelated person’s position; seat the pair as \(2\cdot 5!\) for remaining seats in circle… Use: linear arrange pair as block \(2\cdot 6!\), divide by \(7\) for rotations: \(\frac{2\cdot 720}{7}\) not integer—so fix one person: \(2\cdot 5!=240\).

G1. \(P(n,k)=n!/(n-k)!\).
G2. Stars-bars positive: \(\binom{n-1}{k-1}\).
G5. \(\binom{n}{k}\cdot k=n\binom{n-1}{k-1}\).
G7. \(k!\,S(n,k)=\sum_{i=0}^{k}(-1)^{k-i}\binom{k}{i}i^{n}\).

X8 worked. Bit-strings length 7 no consecutive 1s: Fibonacci-type \(a_n=a_{n-1}+a_{n-2}\), \(a_1=2,a_2=3\) → \(a_7=34\) (or \(F_9\) depending on indexing—list recurrence carefully).

Synthesis — exam transfer skills

  1. Name the object in one noun phrase before formulas.
  2. Order / identical / constraints triad.
  3. Complement when “at least one” or “not all.”
  4. IE when several overlapping properties.
  5. Recurrence when last step decomposes.
  6. Sanity: \(n=0,1,2\) enumerate; compare two methods.

S6. Write full exam solution for A2 (password ≥1 letter and digit).
S7. Story-prove \(\sum k\binom{n}{k}=n2^{n-1}\).
S8. Full IE for \(|\{1..210\}|\) divisible by \(2,3,\) or \(5\).
S9. Closed form \(a_n=3a_{n-1}-2a_{n-2}\), \(a_0=1,a_1=3\).
S10. Create and solve one original “surjection + IE” problem with \(n\le 6\).

Method selection guide (final)

Clue in the problem First tool
Sequence / slots free Product \(n_1 n_2\cdots\)
Partition into types Sum
Ordered distinct \(P(n,k)\)
Unordered distinct \(\binom{n}{k}\)
Identical into distinct bins Stars-bars
Overlapping bad properties IE
“No fixed points” Derangement IE
Onto functions Surjection IE
Last step decomposes Recurrence
Balanced parentheses / BST shapes Catalan
At least one / not all Complement

Timed micro-set (15 minutes)

  1. \(P(9,3)\) and \(\binom{9}{3}\).
  2. Nonneg \(x+y+z+w=7\).
  3. \(!5\).
  4. \(C_4\).
  5. Surjections \([4]\to[2]\).
  6. Paths \((0,0)\to(4,3)\).
  7. \(\sum k\binom{6}{k}\).
  8. Bit-strings length 6 no consecutive 1s.

Answers sketch: \(504\), \(84\); \(\binom{10}{3}=120\); \(44\); \(14\); \(14\); \(\binom{7}{4}=35\); \(6\cdot 32=192\); \(a_6=21\) (Fib-type).

Synthesis

Workshop skill is method selection under mixed prompts. Name the object, classify order/repetition/constraints, pick the tool, sanity-check small \(n\). Gate V rewards clean justification over clever arithmetic tricks.

Tomorrow

Day 58 — Gate V: counting portfolio under exam conditions—full justification; include derangement or Catalan; include a recurrence.

Day 58 — Gate V

Stage V · gate day
Goal: Demonstrate combinatorics fluency: justified counts, identities, light recurrences—closed notes if possible; full written work. Include derangement or Catalan; include a recurrence item.

Why this matters

A gate is a retestable portfolio: if you clear it, Stage V skills are available under pressure for graphs (Stage VI) and later probability. If not, remediate weak days before moving on. Counting without justification is not counting.

How to take this gate

  1. Timebox ~90–120 minutes for exam simulation.
  2. No looking at Days 47–57 until you finish a first pass.
  3. Write object + method + answer for every counting problem.
  4. Afterward, score with the rubric; redo any section below threshold within 48h.
Important

No coding labs. Proofs short and complete. Calculators OK for arithmetic; formulas from memory.

Rubric (self-score)

Section Points Pass bar
A Definitions & formulas 15 ≥ 11
B Product/sum/\(P\)/\(\binom{n}{k}\) 25 ≥ 18
C Stars-bars / IE / functions 25 ≥ 18
D Identities, Catalan/derangement 15 ≥ 10
E Recurrences 10 ≥ 7
F Mixed CS scenarios 10 ≥ 7
Total 100 ≥ 75 and no section < 50%

Theory — rapid self-check sheet

Reproduce from memory before starting:

  1. Product rule; sum rule; when IE is needed.
  2. \(P(n,k)=n!/(n-k)!\); \(n^k\); circular \((n-1)!\).
  3. \(\binom{n}{k}\); \(P(n,k)=\binom{n}{k}k!\); multiset \(\binom{n+k-1}{k}\).
  4. Stars-and-bars nonnegative \(\binom{n+k-1}{k-1}\); positive \(\binom{n-1}{k-1}\).
  5. IE 2-set and 3-set; surjection formula.
  6. \(!n=n!\sum(-1)^k/k!\approx n!/e\).
  7. Binomial theorem; Pascal; \(\sum\binom{n}{k}=2^n\); \(\sum k\binom{n}{k}=n2^{n-1}\).
  8. \(C_n=\frac{1}{n+1}\binom{2n}{n}\) (one interpretation).
  9. Characteristic equation for \(a_n=pa_{n-1}+qa_{n-2}\).
  10. Fib / Hanoi / tiling setups.

Worked warm-ups (optional, 10 min)

A. \(P(6,2)\) vs \(\binom{6}{2}\) vs \(6^2\).
B. \(x+y+z=5\) nonnegative.
C. \(!3\) by list.
D. \(a_n=2a_{n-1}\), \(a_0=3\).
E. Paths to \((3,2)\).

Gate exam (closed book)

Section A — Definitions & formulas (15)

Write from memory (≈2–3 pts each):

  1. Product rule and sum rule (one sentence each + tiny example).
  2. \(P(n,k)\) formula and combinatorial meaning.
  3. \(\binom{n}{k}\) formula and meaning.
  4. Nonnegative stars-and-bars count for \(x_1+\cdots+x_k=n\).
  5. Two-set inclusion–exclusion.
  6. Binomial theorem statement.
  7. (Bonus +2, still in A budget as optional) Surjection formula or derangement formula.

Section B — Core counting (25)

  1. Length-6 bit-strings starting with 10 or ending with 11 — careful with overlap (IE or cases).
  2. From 9 distinct books, arrange 4 on a shelf (order matters).
  3. From 9 books, choose 4 for a reading list (order irrelevant).
  4. Anagrams of LEVEL.
  5. 3-digit numbers with distinct digits, no leading zero.
  6. Paths from \((0,0)\) to \((5,3)\) with unit \(R,U\) steps.
  7. Coefficient of \(x^3y^4\) in \((x+y)^7\).
  8. Evaluate \(\sum_{k=0}^{n}\binom{n}{k}\) and \(\sum_{k}k\binom{n}{k}\) in closed form.

Section C — Stars, IE, functions (25)

  1. Nonnegative integer solutions to \(a+b+c+d=12\).
  2. Positive integer solutions to \(a+b+c=10\).
  3. Nonnegative solutions to \(x+y+z=7\) with each variable \(\le 4\).
  4. How many integers in \(\{1,\ldots,120\}\) divisible by 3 or 4?
  5. Count all functions \([4]\to[3]\); injections \([3]\to[5]\); bijections \([4]\to[4]\).
  6. Surjections \([4]\to[2]\).
  7. Multisets of size 6 from 4 colors.
  8. \(!4\) by formula (show the sum).

Section D — Identities, Catalan, derangement (15)

  1. Prove \(\binom{n}{k}=\binom{n}{n-k}\) by bijection.
  2. Prove Pascal’s identity by a distinguished-element story.
  3. Prove \(k\binom{n}{k}=n\binom{n-1}{k-1}\) by double counting.
  4. Compute \(C_4=\frac{1}{5}\binom{8}{4}\); name two Catalan interpretations.
  5. (Choose one) Probability limit of derangements \(!n/n!\to ?\) or Vandermonde story statement.

Section E — Recurrences (10)

  1. Write a recurrence + bases for tilings of \(n\)-board with tiles of size 1 and 2; compute \(T_5\).
  2. Solve \(a_n=3a_{n-1}\), \(a_0=7\).
  3. Solve \(a_n=5a_{n-1}-6a_{n-2}\), \(a_0=0\), \(a_1=1\) (closed form).
  4. Bit-strings length \(n\) no consecutive \(1\)s: recurrence + \(a_4\).

Section F — Mixed CS scenarios (10)

  1. Password length 8 from 62-char alphabet; write size and \(\log_2\) expression for entropy bits.
  2. 6 feature flags with flags 1 and 2 mutually exclusive (not both true)—count valid configs.
  3. 5 distinct jobs to 3 distinct workers, each worker ≥1 job—set up (number OK as expression).
  4. Protocol versions \((M,m,p)\) with \(M\in\{0,1,2\}\), \(m,p\in\{0,\ldots,9\}\)—count.

Answer key (self-mark after first pass)

A. Grade for correctness of formulas/statements.
8. Start 10: \(2^4=16\); end 11: \(2^4=16\); both: start 10 and end 11: \(2^2=4\); union \(16+16-4=28\).
9. \(P(9,4)=9\cdot8\cdot7\cdot6=3024\).
10. \(\binom{9}{4}=126\).
11. \(5!/(2!2!)=30\).
12. \(9\cdot9\cdot8=648\).
13. \(\binom{8}{5}=\binom{8}{3}=56\).
14. \(\binom{7}{4}=35\) (for \(y^4\)) or \(\binom{7}{3}=35\).
15. \(2^n\); \(n2^{n-1}\).
16. \(\binom{12+3}{3}=\binom{15}{3}=455\).
17. \(\binom{9}{2}=36\).
18. Total \(\binom{9}{2}=36\); one var ≥5: \(\binom{4}{2}=6\) each, ×3=18; two ≥5: \(7-10<0\)? \(7-5-5=-3\) →0; answer \(18\). Wait \(36-18=18\).
19. \(\lfloor120/3\rfloor+\lfloor120/4\rfloor-\lfloor120/12\rfloor=40+30-10=60\).
20. \(3^4=81\); \(P(5,3)=60\); \(4!=24\).
21. \(2^4-2=14\).
22. \(\binom{4+6-1}{6}=\binom{9}{6}=84\).
23. \(24(1-1+1/2-1/6+1/24)=9\).
24–26. Standard stories (Days 49–50, 56).
27. \(C_4=14\); Dyck/parens/BST/paths.
28. \(1/e\) or men/women story.
29. \(T_n=T_{n-1}+T_{n-2}\), \(T_0=1,T_1=1\); \(T_5=8\).
30. \(a_n=7\cdot 3^n\).
31. \(a_n=3^n-2^n\).
32. \(a_n=a_{n-1}+a_{n-2}\), \(a_1=2,a_2=3\); \(a_4=8\).
33. \(62^8\); \(8\log_2 62\).
34. \(2^6-2^4=64-16=48\).
35. Surjections \(3!S(5,3)\) or IE \(\sum(-1)^i\binom{3}{i}(3-i)^5=150\).
36. \(3\cdot10\cdot10=300\).

Remediation map

Weak section Rework days
A formulas 47–52 skim theory boxes
B core 47–50 + workshop A/B
C stars/IE 51–52
D identities 50, 56
E recurrences 54–55
F CS 53

Portfolio reflection (required after scoring)

Write 5–10 lines:

  1. Strongest method?
  2. Weakest method?
  3. One overcount you almost made.
  4. Ready for graphs? If no, what one skill blocks you?

Checkpoint

  • Full exam attempted closed book
  • Score ≥ 75/100 with no section < 50%
  • Missed items redone cold within 48h
  • Formula sheet reduced to one page from memory
  • Reflection written
  • Derangement or Catalan item correct
  • At least one recurrence item correct

Two personal takeaways:

  1. …
  2. …

Deepening notes

Closed-book formula sheet (reproduce blank)

Write on scrap before the exam:

  • \(P(n,k)\), \(\binom{n}{k}\), multiset, stars-bars ±
  • IE 2-set / 3-set / surjection / \(!n\)
  • Binomial theorem; Pascal; \(\sum_k\binom{n}{k}=2^n\); \(\sum_k k\binom{n}{k}=n2^{n-1}\)
  • \(C_n=\frac1{n+1}\binom{2n}{n}\)
  • Char eq \(r^2-pr-q=0\); Fib bases

Full justification template

Object: …
Method: product | sum | complement | P | C | SB | IE | rec | story
Setup: …
Arithmetic: …
Sanity: small n or bound check

Extra gate-style items

G1. Circular arrangements of 9 with two together.
G2. \(x+y+z+w=20\) each ≤8.
G3. Catalan \(C_3\) list parentheses.
G4. Solve \(a_n=2a_{n-1}+2^n\), \(a_0=0\) (particular form).
G5. Functions \([6]\to[4]\) surjective count.

Post-gate 48h plan

Day Action
+0 Score + error log
+1 Rework failed section cold
+2 Mini retest 5 items

Stage V exit criteria

  • Gate ≥75
  • Derangement or Catalan correct
  • Recurrence closed form correct
  • Story proof of Pascal correct
  • One CS entropy calculation correct

Extended practice battery (if time remains or for rematch)

Battery 1 — Speed arithmetic

  1. \(P(10,4)\), \(\binom{10}{4}\), \(10^4\).
  2. \(\binom{12}{3}\), \(\binom{12}{9}\).
  3. Nonnegative \(x+y+z=8\).
  4. Positive \(x+y+z=8\).
  5. \(!4\), \(C_3\).

Battery 2 — Method choice only (no full arithmetic)

For each, name the method in ≤5 words:

  1. Anagrams of PROBABILITY.
  2. Onto maps \([7]\to[4]\).
  3. Bit-strings with no two consecutive 1s.
  4. Coefficient of \(x^5\) in \((1+x)^{12}\).
  5. Integers ≤1000 divisible by 7 or 11.

Battery 3 — Proof sketches (5–8 lines each)

  1. Pascal combinatorial.
  2. Absorption.
  3. Hockey-stick max-element.
  4. Surjection IE setup (formula only).
  5. Characteristic equation for Fib.

Battery 4 — CS

  1. Entropy bits \(52^{10}\).
  2. Feature flags 8 with at most 2 true.
  3. Secret Santa \(!9\) formula.
  4. Hash all buckets nonempty: 6 keys, 3 buckets.
  5. Protocol product: 4-bit type × payload \(2^{8}\) if type even else \(2^{4}\).

Partial solutions for batteries

  1. \(5040\), \(210\), \(10000\).
  2. \(\binom{10}{2}=45\).
  3. \(\binom{7}{2}=21\).
  4. \(9\), \(5\).
  5. IE surjections.
  6. Recurrence Fib-like.
  7. \(10\log_2 52\).
  8. \(3!S(6,3)=540\).

Confidence map

After the gate, shade each topic green/yellow/red:

Topic Color
Product/sum
\(P\)/circular/derange
\(\binom{n}{k}\) / paths
Binomial/Catalan
Stars-bars
IE/surjections
Story proofs
Recurrences solve
CS counting

Yellow and red → Day numbers from remediation map.

Remediation map (Day → topic)

Weak area Return to
Product / sum / complement Day 47
Permutations / circular / derange Day 48
Combinations / paths Day 49
Binomial / Catalan Day 50
Stars and bars Day 51
IE / surjections Day 52
CS counting / entropy Day 53
Recurrence setup Day 54
Closed forms / char eq Day 55
Story proofs Day 56
Mixed drill Day 57

Gate self-score rubric

Criterion Points idea
Correct method named High
Correct formula setup High
Arithmetic Medium
Justification sentences High
Sanity small-\(n\) Bonus

Partial credit: right model, wrong arithmetic > wrong model, lucky number.

Post-gate checklist

  • Scored each problem
  • Confidence map filled
  • At least two yellow/red topics reworked (3 problems each)
  • Portfolio: 1 story proof + 1 IE + 1 recurrence closed form + 1 Catalan or derangement
  • Formula sheet rewritten from memory once

Synthesis

Gate V closes Stage V counting. You should select among product, \(P(n,k)\), \(\binom{n}{k}\), stars-bars, IE, Catalan, and recurrences with a one-line object name. Stage VI shifts to graphs—structure, connectivity, and algorithms—while still using counting for degrees, trees, and colorings.

Tomorrow

Day 59 — Graphs & handshaking: simple/multi/directed graphs; handshaking lemma; graphic sequences; special graphs.