Day 58 — Gate V

Updated

July 30, 2026

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

Timebox ~90–120 minutes for exam simulation.
No looking at Days 47–57 until you finish a first pass.
Write object + method + answer for every counting problem.
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:

Product rule; sum rule; when IE is needed.
\(P(n,k)=n!/(n-k)!\); \(n^k\); circular \((n-1)!\).
\(\binom{n}{k}\); \(P(n,k)=\binom{n}{k}k!\); multiset \(\binom{n+k-1}{k}\).
Stars-and-bars nonnegative \(\binom{n+k-1}{k-1}\); positive \(\binom{n-1}{k-1}\).
IE 2-set and 3-set; surjection formula.
\(!n=n!\sum(-1)^k/k!\approx n!/e\).
Binomial theorem; Pascal; \(\sum\binom{n}{k}=2^n\); \(\sum k\binom{n}{k}=n2^{n-1}\).
\(C_n=\frac{1}{n+1}\binom{2n}{n}\) (one interpretation).
Characteristic equation for \(a_n=pa_{n-1}+qa_{n-2}\).
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):

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

Section B — Core counting (25)

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

Section C — Stars, IE, functions (25)

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

Section D — Identities, Catalan, derangement (15)

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

Section E — Recurrences (10)

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

Section F — Mixed CS scenarios (10)

Password length 8 from 62-char alphabet; write size and \(\log_2\) expression for entropy bits.
6 feature flags with flags 1 and 2 mutually exclusive (not both true)—count valid configs.
5 distinct jobs to 3 distinct workers, each worker ≥1 job—set up (number OK as expression).
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:

Strongest method?
Weakest method?
One overcount you almost made.
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:

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

Extended practice battery (if time remains or for rematch)

Battery 1 — Speed arithmetic

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

Battery 2 — Method choice only (no full arithmetic)

For each, name the method in ≤5 words:

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

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

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

Battery 4 — CS

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

Partial solutions for batteries

\(5040\), \(210\), \(10000\).
\(\binom{10}{2}=45\).
\(\binom{7}{2}=21\).
\(9\), \(5\).
IE surjections.
Recurrence Fib-like.
\(10\log_2 52\).
\(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.