Day 17 — Counting Rules, Permutations & Combinations

Day 17 — Counting Rules, Permutations & Combinations

Day 47 — Product & sum rules

Stage V · concept day
Goal: Count systematically with the product rule, sum rule, complementary counting, decision trees, and justified mixed arguments; diagnose overcounts before they become habits.

Why this matters

Every password policy, test-suite size estimate, state-machine enumeration, and “how many configurations?” question is a counting problem. The product and sum rules are the two primitive operations: a sequence of independent choices multiplies; mutually exclusive cases add. Later tools (permutations, combinations, inclusion–exclusion) are special cases or corrections of these two ideas. If your product/sum story is wrong, no amount of binomial algebra saves the answer.

Theory

What “counting” means

We count finite sets of outcomes. An outcome is a complete description of a configuration (a password string, a seating, a bit-string satisfying a constraint). Two descriptions that look different but represent the same object must not both be counted (overcount); two that represent different objects must not be collapsed (undercount).

Principle of bijection. If you build a 1–1 correspondence between the set you care about and a set you already know how to count, the sizes match. Writing a clear “story” of how each outcome is built is how you prove the correspondence.

Product rule (multiplication principle)

Statement. Suppose a process of constructing an outcome has \(k\) stages, and:

• stage \(1\) can be completed in \(n_1\) ways,
• after stage \(1\) is fixed, stage \(2\) can be completed in \(n_2\) ways,
• …
• after stages \(1,\ldots,k-1\) are fixed, stage \(k\) can be completed in \(n_k\) ways,

and every outcome arises from exactly one sequence of stage choices. Then the number of outcomes is

\[ n_1 n_2 \cdots n_k. \]

Why it is true (decision tree). Draw a rooted tree: the root has \(n_1\) children; every node at depth \(i-1\) has \(n_i\) children. A full \(k\)-level tree of this shape has exactly \(n_1\cdots n_k\) leaves, and each leaf is one outcome.

Why it is true (induction on stages). For \(k=1\) the claim is trivial. If the first \(k-1\) stages can be completed in \(N=n_1\cdots n_{k-1}\) ways and each such history leaves \(n_k\) options, total \(= \sum_{\text{histories}} n_k = N\cdot n_k\).

Independence note. The \(n_i\) need not be “independent of everything”—they may depend on which previous choices were made, as long as every history still leaves the same number \(n_i\) of options. If the count of options depends on the history, you must case-split (sum rule) or use a more careful product with different branches.

Sum rule (addition principle)

Statement. If a set of outcomes can be partitioned into \(m\) pairwise disjoint classes \(C_1,\ldots,C_m\), and \(|C_i|=n_i\), then

\[ |C_1\cup\cdots\cup C_m| = n_1+\cdots+n_m. \]

Why it is true. Partition means every outcome is in exactly one class: no overlap, no omission. Cardinality of a disjoint union is the sum of cardinalities.

Warning. If classes overlap, plain addition overcounts. That is why inclusion–exclusion (Day 52) exists. If classes miss some outcomes, you undercount.

Complementary counting

Often the easiest count of \(A\) is

\[ |A| = |U| - |U\setminus A| \]

for a simple universe \(U\) that contains \(A\). Complementary counting is product/sum applied to the complement. Classic pattern: “at least one \(X\)” $= $ total \(-\) “no \(X\).”

Decision tree discipline

Before writing a formula:

1. Name what an outcome is (exact type of object).
2. Stages or cases: sequential structure → product; mutually exclusive types → sum.
3. Check once: every legal outcome counted once; no illegal outcome counted.
4. Sanity: small \(n\) enumeration matches the formula.
5. Order matters? If the final object is a set/multiset vs a sequence, the story differs.

Overcount diagnosis

When two methods disagree:

Symptom	Likely cause	Fix
Answer too large vs listing	Double-counted overlapping cases, or counted ordered when object is unordered	Partition more carefully; divide by symmetry if justified
Answer too small	Missed a case; illegal constraint too strong	Re-check partition covers \(U\)
Product used on OR of properties	Sum-rule violation	Cases or IE
Sum used on sequential stages	Product-rule violation	Stages in order

Functions as product

If \(|A|=n\) and \(|B|=m\), the set of all functions \(f:A\to B\) has size \(m^n\): for each of \(n\) domain elements independently choose one of \(m\) images. Specializations:

• injections (no collisions): \(P(m,n)\) if \(n\le m\) (Day 48);
• all binary strings of length \(n\): \(2^n\) (functions \([n]\to\{0,1\}\));
• power set of an \(n\)-set: \(2^n\) (characteristic functions).

Inclusion–exclusion preview

For two properties \(A,B\) that may overlap:

\[ |A\cup B| = |A|+|B|-|A\cap B|. \]

Today: recognize when you need the third term. Full IE on Day 52.

Linking to earlier days

Cartesian products (Day 37) are pure product: \(|A\times B|=|A|\,|B|\). Power sets give \(|\mathcal{P}(S)|=2^{|S|}\). Pigeonhole (Day 45) says when collisions must exist; counting says how many configurations avoid them.

Worked examples

Example 1 — Pure product: license plates

A plate is three letters (A–Z) followed by three digits (0–9), repetition allowed.

• Stages 1–3: letter, 26 choices each → \(26^3\).
• Stages 4–6: digit, 10 choices each → \(10^3\).
• Product: \(26^3\cdot 10^3 = 17{,}576{,}000\).

If letters must be distinct but digits free: \(26\cdot 25\cdot 24\cdot 10^3\).

Example 2 — Pure sum: bit-strings by length

Count bit-strings of length exactly \(1\) or exactly \(2\).

• Length 1: \(2^1=2\); length 2: \(2^2=4\).
• Disjoint by length: \(2+4=6\).

Wrongly multiplying \(2\cdot 4=8\) counts ordered pairs of (len-1 string, len-2 string)—a different set.

Example 3 — Mix: passwords with structure

Length-4 passwords over letter/digit classes (26 letters, 10 digits). Pattern LLDD: \(26\cdot 26\cdot 10\cdot 10=67{,}600\).

Exactly two letters and two digits in some order:

• Choose 2 positions for letters: \(\binom{4}{2}=6\) patterns (or list LLDD, LDLD, LDDL, DLLD, DLDL, DDLL).
• Each pattern: \(26^2\cdot 10^2\).
• Sum: \(6\cdot 26^2\cdot 10^2=405{,}600\).

Example 4 — Dependent counts that still multiply

Seat 5 people in a row of 5: first seat 5 choices, then 4, then 3, then 2, then 1: \(5!=120\). Counts depend on prior choices, but the number remaining is fixed at each stage.

Example 5 — Complementary count

Bit-strings of length \(n\) that are not all zeros: \(2^n-1\).
Length-5 strings over \(\{0,1\}\) with at least one \(1\): \(32-1=31\).

Example 6 — When product fails without cases

Length-3 strings over \(\{A,B,C\}\) with no two consecutive equal:

• Pos 1: 3; pos 2: 2 (\(\neq\) first); pos 3: 2 (\(\neq\) second) → \(3\cdot 2\cdot 2=12\).

Constraint “not all three equal”: complement \(3^3-3=24\). Different constraint → different method.

Example 7 — CS-shaped state space

Feature flags \((f_1,f_2,f_3)\) each boolean, but \((0,0,0)\) disabled: \(2^3-1=7\).

Example 8 — Nested cases

IDs: either (a) 2 letters + 2 digits, or (b) 4 digits.

• (a): \(26^2\cdot 10^2\); (b): \(10^4\); disjoint formats → \(67{,}600+10{,}000=77{,}600\).

Example 9 — Functions

Maps \(\{1,2,3\}\to\{a,b,c,d\}\): \(4^3=64\). With \(f(1)=a\) forced: \(4^2=16\). Constant maps: 4.

Example 10 — Complement with larger alphabet

Length-4 strings over \(\{0,1,2\}\) with ≥ one \(2\): \(3^4-2^4=81-16=65\).

Example 11 — Optional fields

Main dish 5 ways; starter optional among 3 (or absent = 4 choices); dessert optional among 2 (or absent = 3): \(5\cdot 4\cdot 3=60\).

Example 12 — Dependent digits, no leading zero

3-digit strings, distinct digits, no leading zero: hundreds \(9\) choices (\(1\)–\(9\)); tens \(9\) (remaining including \(0\)); units \(8\): \(9\cdot 9\cdot 8=648\).

Example 13 — Case on pattern

Length-3 over letter/digit with exactly one digit: choose digit position (3); that pos \(10\) ways; others \(26\) each: \(3\cdot 10\cdot 26^2\).

Example 14 — Grid enumeration (product/sum story)

From \((0,0)\) to \((2,1)\) with unit Right/Up only: need 2 R and 1 U in some order. Sequences: RRU, RUR, URR — 3 ways. (Tomorrow’s combinations will say \(\binom{3}{1}\).)

Example 15 — Overcount diagnosis

Count length-3 bit-strings that start with 1 or end with 1.

• Start with 1: \(2^2=4\); end with 1: \(4\); sum \(8\).
• But 1x1 counted twice; listing: total \(8\), start-or-end: all except 000,010 wait—length 3: universe \(8\); neither property: start \(0\) and end \(0\) → \(0x0\) with middle free: \(2\) strings 000,010. So \(|A\cup B|=8-2=6\).
• Correct: \(4+4-2=6\) (IE preview). Naive sum overcounted by \(2\).

Exercises

Solve by hand. Write a short justification (stages or partition) for each answer.

1. How many length-\(4\) bit-strings start with \(1\)? With \(01\)?
   
2. A 4-digit PIN (digits \(0\)–\(9\)). Count with repetition allowed; with all digits distinct; with digits strictly increasing (think: choose 4 digits then only one order works).
   
3. Menu: 3 starters, 5 mains, 2 desserts. Full meals (one of each)? Meals that skip dessert? Total with dessert optional?
   
4. Passwords length 5 from 26 letters + 10 digits (each char either). How many? How many if first char must be a letter?
   
5. License plates: 2 letters then 3 digits, letters distinct, digits free.
   
6. Bit-strings length \(n\) with first bit \(0\) or last bit \(1\)—for \(n=3\) list and compute; explain why plain sum fails.
   
7. Functions \(f:\{1,2,3\}\to\{a,b\}\): count all by product. How many are constant? How many are surjective?
   
8. A byte is 8 bits. How many have MSB \(=1\)? How many have even parity (even number of \(1\)s)?
   
9. Paths on a grid from \((0,0)\) to \((2,1)\) moving only right or up—enumerate.
   
10. Explain two mistakes: adding when stages are sequential; multiplying when cases overlap. One numeric micro-example of each.
    
11. Count strings of length 3 over \(\{1,2,3,4\}\) with all characters different.
    
12. Outcomes of rolling a fair 6-sided die then flipping a coin (ordered pair).
    
13. Protocol version \((major,minor,patch)\) with \(major\in\{0,1,2\}\), \(minor,patch\in\{0,\ldots,9\}\). How many versions? How many with \(major\ge 1\)?
    
14. Shelf A: 4 distinct books left-to-right; shelf B: 3 different books. Arrangements if shelves are distinguishable.
    
15. Length-4 passwords over 62 alphanumeric chars with at least one digit: set up with complement (symbolic OK).
    
16. Count \(n\)-tuples in \(\{1,\ldots,m\}^n\) with first coordinate fixed to \(1\).
    
17. Letter-digit-letter-digit plates, distinct letters and distinct digits.
    
18. Assign 5 distinct bugs to 3 severity levels (all functions).
    
19. Length-6 bit-strings starting with \(1\) or ending with \(00\) (handle overlap carefully).
    
20. Prove the \(k\)-stage product rule by induction on \(k\).
    
21. Invent a problem needing a 2-way sum and a 3-stage product; solve it.
    
22. Password space \(N=36^8\); write \(\log_2 N\) as an expression (entropy bits).
    
23. How many nonempty subsets does an \(n\)-set have? (Product or sum of binomials.)
    
24. Two distinguishable dice: total outcomes; outcomes with sum \(\ge 10\).
    
25. CS: pairs \((a,b)\) with \(a\in\{0,\ldots,255\}\), \(b\in\{0,\ldots,15\}\), \(a\neq 0\).

CS connection

• Test matrices: each factor with \(n_i\) levels → \(\prod n_i\) full factorial designs; incomplete designs are deliberate undercounts.
  
• API keys / tokens: alphabet size \(\times\) length → product; entropy \(\approx k\log_2 |\Sigma|\).
  
• Feature flags & enums: configuration space is a product of option sets; illegal combos force complement or IE.
  
• FSM / protocol states: reachable configurations ⊆ product of local variables; exhaustive testing needs the product size first.
  
• Type systems: product types (struct) multiply; sum types (enum/Result) add.

Common pitfalls

Pitfall	What to do instead
Multiplying overlapping cases	Partition first; or use inclusion–exclusion later
Forgetting order of stages changes the story not always the count	Name the object; check with small \(n\)
“Independent” misread as “unrelated quantities”	Product needs fixed option counts along a construction
Losing the empty/all-zero case	Explicitly include or complement
Double-counting symmetry (arrangements vs sets)	Ask: does order matter in the final object?
Using sum for sequential stages	Stages → product
Ignoring leading-zero constraints	Case the first digit separately

Checkpoint

• State product and sum rules without notes
  
• Give one pure-product and one pure-sum example with numbers
  
• Explain complementary counting in one sentence
  
• Diagnose the overcount in Example 15 cold
  
• Rework Examples 3, 6, and 12 cold
  
• Exercises 1–15 done with justifications
  
• One sentence: where product/sum appears in a system you use

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

1. Start 1: \(2^3=8\); start 01: \(2^2=4\).
   
2. PINs: \(10^4\); distinct \(P(10,4)=5040\); strictly increasing \(\binom{10}{4}=210\).
   
3. Functions \(2^3=8\); constants \(2\); surjections \(8-2=6\).
   
4. MSB \(1\): \(2^7=128\); even parity: \(2^7=128\).
   
5. \(P(4,3)=24\).
   
6. \(6\cdot 2=12\).
   
7. \(62^4-52^4\).
   
8. \(2^n-1\).

Deepening notes

Product rule as iterated sum (formal)

If stage 1 has \(n_1\) options and every history leaves \(n_2\) options at stage 2, total \(=\sum_{i=1}^{n_1} n_2 = n_1 n_2\). Induct on stages for the \(k\)-fold product. The constant-branch-count hypothesis is what factors the sum.

When option counts depend on history

Suppose after choosing the first letter, the number of legal second letters depends on which letter you chose (not just “how many left”). Then you cannot write a single product \(n_1 n_2\). Case-split on first letter (sum rule), or group histories that share the same remaining count.

Bijection discipline example

To count length-\(n\) bit-strings with even parity: map strings ending in 0 with even weight on the prefix ↔︎ fix last bit to force parity. Standard bijection shows exactly half are even: \(2^{n-1}\).

IE preview fully written

\(|A\cup B\cup C|\) expands to seven Venn regions counted once each after the alternating sum. Draw the Venn diagram once and mark the coefficient each region gets at each stage of IE—muscle memory for Day 52.

Exam micro-drills (extra)

D1. Count length-4 strings over \(\{0,1,2\}\) with no two consecutive equal.
D2. Feature flags 5 booleans with not-all-true and not-all-false.
D3. Two distinguishable dice showing different faces.
D4. Functions \([n]\to[2]\) that are surjective.
D5. IDs of form letter+digit or digit+letter (disjoint formats).
D6. Prove by induction: number of subsets of an \(n\)-set is \(2^n\) via product of in/out choices.
D7. Where does the product rule hide in \(|A\times B\times C|\)?
D8. Deliberately overcount length-2 bit-strings starting with 1 or ending with 0; fix with IE.

Flash formulas

Situation	First try
Sequence of free choices	\(\prod n_i\)
Partition into types	\(\sum n_i\)
At least one \(X\)	total − none
All maps \(A\to B\)	\(\|B\|^{\|A\|}\)
Overlapping properties	IE

Reflection prompts

• Rewrite Example 15 without looking.
  
• Invent a password policy and count it two ways (should match).
  
• Explain to a peer why “or” is not multiply.

Tomorrow

Day 48 — Permutations: ordered selections, \(P(n,k)=n!/(n-k)!\), with repetition \(n^k\), circular \((n-1)!\), and derangements.

---

Day 48 — Permutations

Stage V · concept day
Goal: Count ordered arrangements: \(n!\), \(P(n,k)\), with/without repetition, circular permutations, multiset permutations, and derangements with full formulas.

Why this matters

Whenever order matters—password characters in sequence, ranking candidates, scheduling jobs in a queue, assigning distinct keys to slots—you are counting permutations (or words over an alphabet). Combinations (Day 49) drop order; today you keep it. Derangements answer “hat check” and “nobody gets their own ID” problems that reappear in hashing and matching.

Theory

Factorial

For integer \(n\ge 0\),

\[ n! = n\cdot(n-1)\cdots 1,\qquad 0! := 1. \]

Why \(0!=1\): one empty arrangement of zero objects (empty product). Needed so \(\binom{n}{0}=1\) and \(P(n,0)=1\).

Recurrence: \(n! = n\cdot(n-1)!\) for \(n\ge 1\).

Permutations of \(n\) distinct objects

Number of ways to order \(n\) distinct objects in a line:

\[ n!. \]

Story: \(n\) choices for position 1, \(n-1\) for position 2, …, \(1\) for the last (product rule).

\(k\)-permutations

The number of injective sequences of length \(k\) from an \(n\)-set (\(0\le k\le n\)), order matters, no repetition:

\[ P(n,k) = n^{\underline{k}} = n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!}. \]

Story: fill \(k\) ordered slots without reuse. Equivalent: number of injections from a labeled \(k\)-set into an \(n\)-set.

Edge cases: \(P(n,0)=1\); \(P(n,n)=n!\); \(P(n,k)=0\) if \(k>n\) (no-repetition model).

Bridge to combinations (preview):

\[ P(n,k) = \binom{n}{k}\, k!, \]

because choose the \(k\) elements unordered, then order them in \(k!\) ways.

With repetition allowed

Sequences of length \(k\) from \(n\) types, repetition allowed (words of length \(k\) over alphabet size \(n\)):

\[ n^k. \]

Product rule: \(n\) choices each of \(k\) positions. This is not \(P(n,k)\).
Interpretation: all functions from a \(k\)-set to an \(n\)-set.

Multiset permutations

If objects are not all distinct—multiset with counts \(n_1,\ldots,n_m\) totaling \(n\)—the number of distinct linear arrangements is

\[ \frac{n!}{n_1!\,n_2!\cdots n_m!}. \]

Story: if all were distinct you would have \(n!\); for each type \(i\), the \(n_i!\) internal swaps of identical copies look the same, so divide.

Circular permutations

Arrangements of \(n\) distinct people around a round table, where rotations of the same relative order are identical:

\[ (n-1)!. \]

Story: fix one person’s position (break rotational symmetry), arrange the other \(n-1\) people in the remaining seats: \((n-1)!\).

Equivalently: \(n!\) linear arrangements, identify those that differ by rotation ( \(n\) per class) → \(n!/n=(n-1)!\).

Reflections: if the table has no distinguished direction (necklace that can flip), further identify reflections → \(\frac{(n-1)!}{2}\) for \(n\ge 3\) (only when the problem says flips count as the same).

Numbered seats (chairs labeled): use \(n!\), not \((n-1)!\)—labels break rotational symmetry.

Derangements

A derangement of \(n\) objects is a permutation \(\pi\) with no fixed points: \(\pi(i)\neq i\) for all \(i\).

Notation: \(!n\) or \(d(n)\) or \(D_n\).

Exact formula (inclusion–exclusion)

Let \(A_i\) be the set of permutations that fix \(i\). Then permutations with at least one fixed point are \(\bigcup A_i\), and derangements are the complement:

\[ !n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}. \]

Derivation sketch. By IE,

\[ \Bigl|\bigcap_i \overline{A_i}\Bigr| = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n\binom{n}{n}0! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}, \]

since \(\binom{n}{k}(n-k)! = n!/k!\).

Approximation

\[ !n = \frac{n!}{e} \text{ rounded to nearest integer for } n\ge 1 \]

(more precisely \(!n = \bigl\lfloor n!/e + 1/2\bigr\rfloor\) for \(n\neq 0\)). As \(n\to\infty\), \(!n / n! \to 1/e \approx 0.3679\)—about \(37\%\) of permutations are derangements.

Recurrences (optional awareness)

\[ !n = (n-1)\bigl[!(n-1)+!(n-2)\bigr],\qquad !0=1,\; !1=0. \]

Also \(!n = n\cdot!(n-1)+(-1)^n\).

Relation to functions

Object	Count
All functions \([k]\to[n]\)	\(n^k\)
Injections \([k]\to[n]\)	\(P(n,k)\)
Bijections \([n]\to[n]\)	\(n!\)
Derangements of \([n]\)	\(!n\)

Worked examples

Example 1 — Full permutations

Line up 5 distinct books: \(5!=120\).

Example 2 — \(P(n,k)\)

From 10 people, choose president, VP, treasurer (roles different): \(P(10,3)=10\cdot 9\cdot 8=720\).
Unordered committee of 3: \(\binom{10}{3}=120\) (Day 49).

Example 3 — Passwords without repeated characters

Length-4 from 26 lowercase, no repeat: \(P(26,4)=26\cdot 25\cdot 24\cdot 23\).
With repetition: \(26^4\).

Example 4 — Multiset

Rearrangements of SUCCESS: S×3, C×2, E, U:

\[ \frac{7!}{3!\,2!} = \frac{5040}{12} = 420. \]

Example 5 — Partial with restriction

3-digit numbers, distinct digits, no leading zero: \(9\cdot 9\cdot 8=648\).

Example 6 — Circular

6 people around a table, rotations same: \((6-1)! = 120\).
If chairs are numbered: \(6!=720\).

Example 7 — Sequential assignment

4 distinct tasks to 4 workers, one each: \(4!\).
4 distinct tasks to 10 workers, at most one each: \(P(10,4)\).

Example 8 — Comparing models

From \(\{1,2,3,4\}\):

Object	Count	Formula
Length-2 sequences, rep OK	16	\(4^2\)
Length-2 sequences, no rep	12	\(P(4,2)\)
Unordered 2-subsets	6	\(\binom{4}{2}\)

Example 9 — Complement + permutations

Anagrams of MATH with A not at the end: total \(4!=24\); end with A: \(3!=6\); so \(24-6=18\).

Example 10 — Derangement of 3

Permutations of \(\{1,2,3\}\): \(6\) total. Fixed-point-free: \((123)\mapsto(2,3,1)\) and \((3,1,2)\) only. So \(!3=2\).
Formula: \(3!(1-1+1/2-1/6)=6\cdot(1/3)=2\).

Example 11 — Derangement of 4

\(!4 = 24(1-1+1/2-1/6+1/24)=24\cdot(9/24)=9\).
List types: 2-cycles double (9 of form \((ab)(cd)\) and 4-cycles with no fixed points: actually \(!4=9\)).

Example 12 — Circular with adjacency

\(n=5\) people, A and B must sit together (rotations identical): glue AB as a block (2 internal orders), arrange block + 3 others circularly: \(2\cdot 4! / 5\)? Better: fix one other person C, or: treat block as one, circular of 4 entities: \(2\cdot(4-1)! = 2\cdot 6=12\). Wait carefully: circular of 4 units = \(3!\), times \(2\) for AB/BA: \(2\cdot 3!=12\).
Alternative: linear glue then divide by rotation carefully—stick to fix-one method when unsure.

Example 13 — Seating row with adjacency

5 people in a row, A and B adjacent: glue → \(2\cdot 4!=48\). Not adjacent: \(5!-48=72\).

Example 14 — \(P\) recurrence

Prove \(P(n,k)=n\,P(n-1,k-1)\) for \(k\ge 1\): choose image of first slot (\(n\) ways), inject the rest into remaining \(n-1\) elements: \(P(n-1,k-1)\).

Example 15 — Words with/without order

How many ways to award gold and silver (distinct) from 20 athletes? \(P(20,2)=20\cdot 19\).
How many ways to pick 2 athletes for a two-person team with no roles? \(\binom{20}{2}\).

Exercises

Solve by hand. Name the model (\(n!\), \(P(n,k)\), \(n^k\), multiset, circular, derangement).

1. Compute \(P(7,3)\), \(P(7,7)\), \(P(7,0)\), and \(7!\).
   
2. Award gold/silver/bronze to 12 runners (no ties).
   
3. Length-5 passwords from 10 digits, no digit repeated; with repetition.
   
4. Distinct rearrangements of MISSISSIPPI.
   
5. Distinct rearrangements of LEVEL.
   
6. Circular arrangements of 8 distinct beads (rotations same; flips different).
   
7. Same beads if flips (necklace) count as identical.
   
8. 4-digit numbers with distinct digits (leading zero allowed as digit string vs as number—state both).
   
9. Injections from \(\{1,2,3\}\) into \(\{1,\ldots,10\}\).
   
10. Is \(P(n,k)=P(n,n-k)\)? Prove or counterexample.
    
11. Prove \(P(n,k)=n!/(n-k)!\) from the falling factorial definition.
    
12. \(!5\) by the sum formula; compare to \(\mathrm{round}(120/e)\).
    
13. \(!6\) by formula.
    
14. Probability a random permutation of \(n\) is a derangement (limit as \(n\to\infty\)).
    
15. Seating 6 in a row: A,B adjacent; A,B not adjacent.
    
16. Circular 7 with two particular people together.
    
17. Prove \(P(n,k)=n\,P(n-1,k-1)\) combinatorially.
    
18. How many ways to choose president and distinct VP from 20?
    
19. Words of length 4 from 10 symbols, no repetition.
    
20. Multiset rearrangements of BOOKKEEPER.
    
21. Compare \(5^3\) vs \(P(5,3)\) with interpretations.
    
22. Order \(n\) distinct deploy steps on one pipeline.
    
23. Derangements of 4 by classifying cycle types (optional).
    
24. Functions \([3]\to[5]\) vs injections \([3]\to[5]\).
    
25. Challenge: number of permutations of \([n]\) with exactly \(k\) fixed points: \(\binom{n}{k}\cdot !(n-k)\).

CS connection

• Unique IDs / nonces: ordered selections without replacement from a keyspace.
  
• Scheduling / priority queues: permutations of tasks.
  
• Password entropy with no-repeat policies: \(P(|\Sigma|,k)\) vs \(|\Sigma|^k\).
  
• Shuffles & randomness tests: \(n!\) of a deck; derangement probability \(\to 1/e\) in “secret santa” algorithms.
  
• Compiler / register assignment lite: injectives map temps to registers (\(P\)).

Common pitfalls

Pitfall	What to do instead
Using \(n!\) when only \(k\) positions filled	Use \(P(n,k)\)
Using \(P(n,k)\) when repetition allowed	Use \(n^k\)
Circular vs linear confusion	Ask: do rotations look the same?
Forgetting to divide for identical letters	Multiset formula
\(0!\) treated as \(0\)	\(0!=1\)
Derangement \(\approx n!/e\) without rounding note	Exact sum exists
Treating roles as unordered	\(P(n,k)\) vs \(\binom{n}{k}\)

Checkpoint

• Write \(P(n,k)\) two ways (product and factorial ratio)
  
• Circular: \((n-1)!\) with a one-line story
  
• Multiset permutation formula
  
• \(!n\) exact formula and \(\approx n!/e\)
  
• Compute \(!3,!4\) cold
  
• Exercises 1–15 with model names
  
• Explain \(P(n,k)=\binom{n}{k}k!\) in words

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

1. \(P(7,3)=210\), \(P(7,7)=5040\), \(P(7,0)=1\), \(7!=5040\).
   
2. \(P(12,3)=1320\).
   
3. MISSISSIPPI: \(11!/(4!4!2!)=34650\).
   
4. LEVEL: \(5!/(2!2!)=30\).
   
5. False: \(P(5,2)=20\neq 60=P(5,3)\).
   
6. \(!5=44\); \(120/e\approx 44.145\).
   
7. Exactly \(k\) fixed: choose them \(\binom{n}{k}\), derange the rest.

Deepening notes

Derangement inclusion–exclusion expanded

\(U=\) all \(n!\) permutations. \(A_i=\) fix \(i\). For a set \(I\) of \(r\) indices, \(|\cap_{i\in I}A_i|=(n-r)!\). There are \(\binom{n}{r}\) such \(I\). IE for none of the \(A_i\):

\[ !n=\sum_{r=0}^{n}(-1)^r\binom{n}{r}(n-r)! = n!\sum_{r=0}^{n}\frac{(-1)^r}{r!}. \]

Circular with reflections

If the problem is a necklace that can flip, Burnside or divide by \(2\) for \(n\ge 3\) when no symmetry issues—only when stated. Default banquet problem: rotations only ⇒ \((n-1)!\).

Extra drills

D1. \(P(15,2)\).
D2. Words length 3 no rep from 8 letters.
D3. PEPPER rearrangements.
D4. Circular 10.
D5. \(!6\) and \(!7\).
D6. Seating 8 row, 3 particular together as a block.
D7. Injections \([4]\to[9]\).
D8. Exactly 2 fixed points among \(S_5\): \(\binom{5}{2}!3\).

Flash

\(P(n,k)=n!/(n-k)!\);\(n^k\) with rep;\((n-1)!\) circular;\(!n\approx n!/e\).

Tomorrow

Day 49 — Combinations: unordered selections \(\binom{n}{k}\), symmetry, grid paths, committees, and combinations with repetition (stars-and-bars preview).

---

Day 49 — Combinations

Stage V · concept day
Goal: Count unordered selections \(\binom{n}{k}\); use symmetry and the bridge \(P(n,k)=\binom{n}{k}k!\); solve committee and grid-path problems; preview combinations with repetition.

Why this matters

Most “choose a subset,” “pick a team,” “select bits that are 1,” and “which edges exist” problems are combinations—order does not matter in the final object. Confusing \(P(n,k)\) with \(\binom{n}{k}\) is the single most common combinatorics error in interviews and exams. Grid paths and committee problems are the training ground for binomial identities (Day 50).

Theory

Definition

The number of ways to choose \(k\) elements from an \(n\)-element set without regard to order (i.e. \(k\)-subsets) is the binomial coefficient

\[ \binom{n}{k} = C(n,k) = \frac{n!}{k!\,(n-k)!} = \frac{P(n,k)}{k!}, \]

for integers \(n\ge 0\) and \(0\le k\le n\). For \(k<0\) or \(k>n\), \(\binom{n}{k}=0\) by convention (useful in sums).

Story for the formula. \(P(n,k)\) counts ordered \(k\)-tuples of distinct elements. Each unordered \(k\)-set corresponds to exactly \(k!\) ordered tuples, so divide by \(k!\).

Symmetry

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

Story: choosing \(k\) to include is the same as choosing \(n-k\) to exclude.
Algebra: \(\frac{n!}{k!(n-k)!}=\frac{n!}{(n-k)!k!}\).

Edge cases

\[ \binom{n}{0}=\binom{n}{n}=1,\qquad \binom{n}{1}=\binom{n}{n-1}=n,\qquad \binom{n}{2}=\frac{n(n-1)}{2}. \]

Pascal’s identity (statement; proof Day 50)

\[ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\qquad (n\ge k\ge 1). \]

Story preview: fix a distinguished element \(x\). A \(k\)-subset either contains \(x\) (choose \(k-1\) from the other \(n-1\)) or not (choose \(k\) from \(n-1\)).

Bridge identity

\[ P(n,k) = \binom{n}{k}\, k!. \]

Always ask: does order matter in the final object?

Final object	Tool
Ordered sequence / ranking / word	\(P\) or \(n^k\)
Unordered set / committee / subset	\(\binom{n}{k}\)
Multiset of size \(k\) from \(n\) types	\(\binom{n+k-1}{k}\) (preview)

Grid paths

Number of shortest paths from \((0,0)\) to \((a,b)\) using only unit East and North steps: you need exactly \(a\) East and \(b\) North in some order—total \(a+b\) steps, choose positions for the East steps (or for North):

\[ \binom{a+b}{a} = \binom{a+b}{b}. \]

Committee problems

From \(n\) people:

• committee of \(k\): \(\binom{n}{k}\);
• committee of \(k\) with a chair (chair in committee): \(\binom{n}{k}\cdot k = n\binom{n-1}{k-1}\) (absorption; Day 50);
• committee with \(r\) from group A (\(|A|=m\)) and \(k-r\) from group B: \(\binom{m}{r}\binom{n-m}{k-r}\).

Combinations with repetition (stars-and-bars preview)

Number of ways to choose \(k\) elements from \(n\) types with repetition allowed, order irrelevant (multisets of size \(k\) from \(n\) types):

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

Intuition (stars and bars, Day 51): place \(k\) identical stars (items) and \(n-1\) bars (dividers between types). Full theory tomorrow; today use the formula and small listings to build trust.

Equivalent: nonnegative integer solutions to \(x_1+\cdots+x_n=k\).

Bit-strings and subsets

Number of length-\(n\) bit-strings with exactly \(k\) ones: \(\binom{n}{k}\).
Number of subsets of an \(n\)-set: \(\sum_k\binom{n}{k}=2^n\) (Day 50).

Worked examples

Example 1 — Basic

\(\binom{10}{3}=\frac{10\cdot 9\cdot 8}{6}=120\).
\(\binom{10}{7}=\binom{10}{3}=120\) by symmetry.

Example 2 — Bridge

\(P(10,3)=720=\binom{10}{3}\cdot 3!=120\cdot 6\).

Example 3 — Committee

From 12 people, choose 4 for a project team: \(\binom{12}{4}=495\).
If the team has a leader chosen from the 4: \(495\cdot 4=1980=P(12,1)\cdot\binom{11}{3}\).

Example 4 — Grid paths

\((0,0)\to(5,3)\): \(\binom{8}{5}=\binom{8}{3}=56\).
\((0,0)\to(2,2)\): \(\binom{4}{2}=6\).

Example 5 — Grid with a barrier (complement idea)

Paths \((0,0)\to(3,3)\) that pass through \((1,1)\): paths to \((1,1)\) times paths from \((1,1)\) to \((3,3)\): \(\binom{2}{1}\cdot\binom{4}{2}=2\cdot 6=12\).
Total unrestricted: \(\binom{6}{3}=20\).

Example 6 — Bit-strings

Length 8 with exactly 3 ones: \(\binom{8}{3}=56\).
At least 7 ones: \(\binom{8}{7}+\binom{8}{8}=8+1=9\).

Example 7 — Mixed groups

8 men, 5 women; committee of 3 with at least one woman:

• Total \(\binom{13}{3}=286\); all-men \(\binom{8}{3}=56\); so \(286-56=230\).
  
• Or sum: \(\binom{5}{1}\binom{8}{2}+\binom{5}{2}\binom{8}{1}+\binom{5}{3}\binom{8}{0}=140+80+10=230\).

Example 8 — Poker lite

5-card hands from 52: \(\binom{52}{5}=2{,}598{,}960\).
4-of-a-kind: choose rank \(\binom{13}{1}\), choose 4 suits for that rank \(\binom{4}{4}\), choose fifth card rank \(\binom{12}{1}\) and suit \(\binom{4}{1}\): \(13\cdot 1\cdot 12\cdot 4=624\).

Example 9 — Combinations with repetition

Multiset of size 3 from types \(\{A,B,C\}\): \(\binom{3+3-1}{3}=\binom{5}{3}=10\).
List: AAA,AAB,AAC,ABB,ABC,ACC,BBB,BBC,BCC,CCC.

Example 10 — Ice cream

3 scoops from 5 flavors, repetition OK, order irrelevant: \(\binom{5+3-1}{3}=\binom{7}{3}=35\).
If order matters (stacked scoops): \(5^3=125\).

Example 11 — Choosing positions

Place 3 non-attacking rooks on first three rows of a chessboard so each of 3 columns used: like choosing 3 columns then permuting—or \(P(8,3)\) for 8 columns. If only “which 3 squares on distinct rows/cols” unordered set of positions with constraints—be careful to name the object.

Example 12 — Pascal check

\(\binom{6}{2}=15\), \(\binom{5}{2}+\binom{5}{1}=10+5=15\).

Example 13 — Division by symmetry

Number of ways to split \(2n\) distinct people into two unlabeled teams of \(n\): \(\binom{2n}{n}/2\) for \(n\ge 1\) (dividing by 2 because team labels don’t matter). For \(n=2\): \(\binom{4}{2}/2=3\).

Example 14 — Paths with only right/up/down? (stick to lattice)

Restrict to monotoic paths only—non-monotonic counts need more tools.

Example 15 — Product of combinations

Deal 5 cards to each of 2 players from 52 (order of dealing hands matters between players if players are distinct): \(\binom{52}{5}\binom{47}{5}\). If only the pair of hands as an unordered partition, divide by \(2!\).

Exercises

1. Compute \(\binom{9}{2}\), \(\binom{9}{7}\), \(\binom{9}{0}\), \(\binom{9}{9}\).
   
2. From 15 books, choose 4 to take on a trip.
   
3. From 15 books, choose 4 and arrange them on a shelf.
   
4. Prove \(\binom{n}{k}=\binom{n}{n-k}\) two ways (algebra + story).
   
5. Paths \((0,0)\to(6,2)\); \((0,0)\to(4,4)\).
   
6. Paths \((0,0)\to(4,3)\) through \((2,1)\).
   
7. Length-10 bit-strings with exactly 4 ones; with at least 9 ones.
   
8. 7 men, 6 women; committee of 5 with 3 men and 2 women.
   
9. Same groups; committee of 5 with at least 3 women.
   
10. Show \(\binom{n}{2}+\binom{n}{1}=\binom{n+1}{2}\) algebraically (hockey-stick lite).
    
11. Multisets of size 4 from 3 flavors: compute and list for \(n=3,k=2\).
    
12. Nonnegative solutions preview: \(x+y+z=4\) count via \(\binom{4+3-1}{4}\).
    
13. Poker: number of full houses (3 of one rank, 2 of another).
    
14. Explain why \(\binom{n}{k}\) is integer even though the formula has division.
    
15. How many 5-subsets of \(\{1,\ldots,20\}\) contain \(1\)? Contain neither \(1\) nor \(2\)?
    
16. Split 10 people into two unlabeled teams of 5.
    
17. \(\binom{2n}{n}\) for \(n=5\); compare growth to \(4^n/\sqrt{\pi n}\) (Stirling awareness—optional).
    
18. Committee of \(k\) from \(n\) including at least one of two particular people—set up cases.
    
19. CS: number of ways to choose 3 servers out of 10 to place replicas.
    
20. CS: number of \(n\)-bit masks with Hamming weight \(k\).
    
21. Verify Pascal for \(n=8,k=3\).
    
22. If order of selection mattered in Ex. 2, what would you compute?
    
23. Combinations with rep: doughnuts, 12 types, buy 6: formula.
    
24. Challenge: number of lattice paths \((0,0)\to(n,n)\) not going above the diagonal—Catalan (Day 50).
    
25. Prove \(\sum_{k=0}^{n}\binom{n}{k}=2^n\) by subset story (product of in/out).

CS connection

• Choosing a subset of features / flags of size \(k\).
  
• Error-correcting codes: weight-\(k\) vectors.
  
• Database: choose \(k\) columns for an index.
  
• Sampling without order: combinations; reservoir sampling implements random \(k\)-subsets.
  
• Binomial coefficients in complexity: number of inputs with \(k\) ones; \(\binom{n}{\le k}\) in learning theory.

Common pitfalls

Pitfall	What to do instead
Using \(P\) when order doesn’t matter	Divide by \(k!\) or use \(\binom{n}{k}\)
Using \(\binom{n}{k}\) when order matters	Use \(P\) or \(n^k\)
Forgetting symmetry to simplify arithmetic	Prefer \(\binom{n}{k}\) with \(k\le n/2\)
“At least” without complement or sum	Cases or total − none
Double-dividing when teams are labeled	Labeled vs unlabeled partitions
Combinations with rep vs without	Repetition? → stars/bars formula

Checkpoint

• Formula for \(\binom{n}{k}\) and \(P(n,k)=\binom{n}{k}k!\)
  
• Symmetry story
  
• Grid path formula
  
• One committee problem with mixed groups
  
• Combinations with repetition formula (preview)
  
• Exercises 1–15
  
• Cold: \(\binom{10}{3}\), paths to \((5,3)\), multiset size 3 from 4 types

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

1. \(\binom{9}{2}=36=\binom{9}{7}\); \(\binom{9}{0}=1\).
   
2. \(\binom{15}{4}=1365\).
   
3. \(P(15,4)=32760\).
   
4. \(\binom{8}{6}=28\); \(\binom{8}{4}=70\).
   
5. \(\binom{3+2-1}{2}=6\).
   
6. \(\binom{6}{4}=15\).
   
7. Full house: \(13\cdot\binom{4}{3}\cdot 12\cdot\binom{4}{2}=3744\).
   
8. \(\binom{10}{5}/2=126\).

Deepening notes

Why divide by \(k!\)?

\(P(n,k)\) treats the ordered \(k\)-tuple \((a,b,c)\) as different from \((b,a,c)\). If the final object is the set \(\{a,b,c\}\), those \(k!\) orders are the same outcome—hence \(\binom{n}{k}=P(n,k)/k!\).

Committee taxonomy

Object	Count
Unordered team of \(k\)	\(\binom{n}{k}\)
Team + chair in team	\(k\binom{n}{k}\)
President + VP + secretary	\(P(n,3)\)
Team with \(r\) from group A	\(\binom{|A|}{r}\binom{n-|A|}{k-r}\)

Lattice paths as binary sequences

Any path with \(a\) East and \(b\) North is a word with \(a\) E’s and \(b\) N’s: \(\binom{a+b}{a}\) such words. Barriers: multiply path counts through waypoints; complement for “avoid region” needs inclusion or reflection (Catalan).

Combinations with repetition — full preview

Stars and bars (Day 51) prove \(\binom{n+k-1}{k}\). Today: list for \(n=3,k=3\) the 10 multisets; match formula \(\binom{5}{3}=10\).

Poker hand sketch table

Hand	Count idea
Flush	\(\binom{4}{1}\binom{13}{5}\) minus straight flushes if strict
Pair	choose rank, suits, kickers carefully
Full house	ranks for triple and pair, suits

Extra drills

D1. \(\binom{20}{3}\) compute.
D2. Paths \((0,0)\to(7,2)\) through \((3,1)\).
D3. Bit-strings length 9 with 4 ones and first bit 1.
D4. Committees of 4 from 10 with 2 particular people not both included.
D5. Multisets size 5 from 6 flavors.
D6. Prove \(\binom{n}{2}=n(n-1)/2\) by handshakes among \(n\) people.
D7. Split 8 people into two labeled teams of 4 vs unlabeled.
D8. Why \(\binom{n}{k}\) integer—induct via Pascal.

Flash

\(\displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!},\quad P(n,k)=\binom{n}{k}k!,\quad \text{multiset }=\binom{n+k-1}{k}.\)

More committee / path hybrids

H1. From 5 men and 4 women, committee of 4 with not all men.
H2. Paths \((0,0)\to(5,5)\) through \((2,2)\) and then \((4,3)\).
H3. Choose 2 starters and 3 bench from 12 players (roles).
H4. Number of 6-subsets of \([20]\) intersecting \(\{1,2,3\}\).

H1 solution: \(\binom{9}{4}-\binom{5}{4}=126-5=121\).
H2: \(\binom{4}{2}\binom{3}{2}\binom{3}{1}=6\cdot 3\cdot 3=54\).

Ordering decisions flowchart

Does order matter in final object?
  yes → repetition allowed? yes n^k / no P(n,k)
  no  → repetition allowed? yes multiset C(n+k-1,k) / no C(n,k)

Exam drill block

E1. Compute \(\binom{15}{4}\) and \(\binom{15}{11}\); state the symmetry used.
E2. Paths \((0,0)\to(6,4)\) through \((2,2)\); then total unrestricted.
E3. From 9 men and 7 women, committee of 5 with at least 2 women—two methods.
E4. Bridge check: \(P(12,4)\) vs \(\binom{12}{4}\cdot 4!\).
E5. Multisets of size 6 from 4 types; nonnegative solutions \(x_1+\cdots+x_4=6\).
E6. Length-12 bit-strings with exactly 5 ones; with Hamming weight \(\ge 10\).
E7. Split 12 people into two unlabeled teams of 6.
E8. Poker: number of two-pair hands (sketch ranks and suits).
E9. True/false: (i) \(\binom{n}{k}\) always divides \(n!\) (ii) \(\binom{n}{0}=0\) (iii) multiset formula needs \(k\le n\).
E10. CS: choose \(k\) of \(n\) feature flags true; write \(\binom{n}{\le k}\) for “at most \(k\).”

Mini solutions

E1. \(\binom{15}{4}=1365=\binom{15}{11}\).
E2. Through: \(\binom{4}{2}\binom{6}{4}=6\cdot 15=90\); total \(\binom{10}{6}=210\).
E4. Both \(11880\).
E5. \(\binom{6+4-1}{6}=\binom{9}{6}=84\).
E7. \(\binom{12}{6}/2=462\).
E9. T (product of integers); F (\(=1\)); F (no such requirement).

Synthesis

Combinations count unordered \(k\)-subsets. The bridge \(P(n,k)=\binom{n}{k}k!\) is the permanent mental link to Day 48. Grid paths are words with fixed letter counts; committees product-of-binomials when groups are stratified. Multisets preview stars-and-bars: same formula, different story. Always name whether order and repetition are allowed before writing a symbol.

S1. Write a one-paragraph “object naming” solution for a mixed men/women committee.
S2. Invent a lattice path with two waypoints and compute.
S3. Cold: \(\binom{20}{3}\), multiset size 4 from 5 types, paths to \((3,5)\).

Tomorrow

Day 50 — Binomial theorem & identities: \((x+y)^n\), Pascal proof, sum identities, and Catalan numbers lite.