Day 57 — Counting workshop

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.