Day 18 — Binomial Theorem, Stars-and-Bars & Inclusion-Exclusion

Day 18 — Binomial Theorem, Stars-and-Bars & Inclusion-Exclusion

Day 50 — Binomial theorem & identities

Stage V · concept day
Goal: Prove and apply the binomial theorem; master Pascal’s identity and core binomial coefficient identities; meet Catalan numbers with 2–3 combinatorial interpretations (lite).

Why this matters

The binomial theorem is the algebraic twin of subset counting. Identities like \(\sum_k\binom{n}{k}=2^n\) and \(\sum_k k\binom{n}{k}=n2^{n-1}\) appear in algorithm analysis, expected values (Stage VIII), and closed forms for combinatorial sums. Catalan numbers count Dyck words, balanced parentheses, and binary trees—structures you will meet in parsing and data structures. Story proofs + algebraic proofs reinforce each other (Day 56 deepens story proofs).

Theory

Binomial theorem

For nonnegative integer \(n\) and indeterminates (or numbers) \(x,y\):

\[ (x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^{k} \]

(equivalently \(\sum_{k}\binom{n}{k}x^{k}y^{n-k}\)).

Combinatorial proof. Expanding \((x+y)(x+y)\cdots(x+y)\) (\(n\) factors), each term picks \(x\) or \(y\) from each factor. A term \(x^{n-k}y^{k}\) arises by choosing \(y\) from exactly \(k\) factors: \(\binom{n}{k}\) ways; the product is \(x^{n-k}y^{k}\).

Algebraic proof (induction on \(n\)). Base \(n=0\): \(1=\binom{0}{0}\). Assume for \(n-1\). Then

\[ (x+y)^n = (x+y)(x+y)^{n-1} = (x+y)\sum_{k=0}^{n-1}\binom{n-1}{k}x^{n-1-k}y^{k}. \]

Collect coefficient of \(x^{n-k}y^{k}\): \(\binom{n-1}{k}+\binom{n-1}{k-1}=\binom{n}{k}\) by Pascal. \(\square\)

Pascal’s identity

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

Combinatorial proof. Fix \(x\in S\), \(|S|=n\). Partition \(k\)-subsets of \(S\) into those containing \(x\) and those not:

• not containing \(x\): \(\binom{n-1}{k}\);
• containing \(x\): choose \(k-1\) more from remaining: \(\binom{n-1}{k-1}\).

Algebraic proof.

\[ \binom{n-1}{k}+\binom{n-1}{k-1} = \frac{(n-1)!}{k!(n-1-k)!}+\frac{(n-1)!}{(k-1)!(n-k)!} = \frac{(n-1)!}{(k-1)!(n-1-k)!}\left(\frac{1}{k}+\frac{1}{n-k}\right) = \frac{(n-1)!}{(k-1)!(n-1-k)!}\cdot\frac{n}{k(n-k)} = \frac{n!}{k!(n-k)!}=\binom{n}{k}. \]

Specializations of the binomial theorem

Substitution	Identity
\(x=y=1\)	\(\sum_{k=0}^{n}\binom{n}{k}=2^n\)
\(x=1,y=-1\)	\(\sum_{k=0}^{n}\binom{n}{k}(-1)^k=0\) for \(n>0\)
\(y=1\)	\((x+1)^n=\sum\binom{n}{k}x^{n-k}\)
\(x=y=1\) story	total subsets by size

Story for \(2^n\): each of \(n\) elements in or out of a subset → product \(2^n\); also \(\sum_k\binom{n}{k}\).

Story for alternating sum (\(n>0\)): number of even-sized subsets equals number of odd-sized subsets (\(=2^{n-1}\)). Pairing: fix \(x\); map \(A\mapsto A\triangle\{x\}\) swaps parity. Hence difference is \(0\).

Absorption / committee-chair identity

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

Story: choose a committee of \(k\) and a chair in the committee.

• Left: committee then chair: \(\binom{n}{k}\cdot k\).
  
• Right: chair first (\(n\)), then \(k-1\) members from remaining: \(n\binom{n-1}{k-1}\).

Sum of \(k\binom{n}{k}\)

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

Story: from \(n\) people, choose a nonempty? Actually: number of ways to choose a subset and a distinguished element in the subset: pick the element first (\(n\)), then any subset of the rest (\(2^{n-1}\)).

Vandermonde’s identity

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

Story: choose \(r\) people from \(m\) men and \(n\) women; if \(k\) men, then \(r-k\) women.

Hockey-stick identity (statement)

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

Story sketch: number of \((r+1)\)-subsets of \(\{1,\ldots,n+1\}\) by maximum element \(i+1\): if max is \(i+1\), choose \(r\) from \(\{1,\ldots,i\}\). Full story proof Day 56.

Pascal’s triangle

Row \(n\): coefficients of \((x+y)^n\). Each interior entry is sum of two above—Pascal identity. Useful for hand expansions and pattern spotting (powers of 2 on row sums).

Multinomial awareness

\((x+y+z)^n\) expands with multinomial coefficients \(\frac{n!}{i!j!k!}\) for \(i+j+k=n\).

Catalan numbers (lite)

The Catalan numbers are

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

with \(C_0=1\), \(C_1=1\), \(C_2=2\), \(C_3=5\), \(C_4=14\), \(C_5=42\).

Recurrence: \(C_0=1\) and \(C_{n+1}=\sum_{i=0}^{n} C_i C_{n-i}\) (or \(C_n=\sum_{i=0}^{n-1}C_i C_{n-1-i}\)).

Combinatorial interpretations (3)

1. Dyck words / balanced parentheses. Number of correctly matched parenthesis strings with \(n\) pairs; equivalently lattice paths from \((0,0)\) to \((n,n)\) with steps \(E,N\) that never rise above the diagonal (or never have more \(N\) than \(E\) in any prefix—Ballot theorem special case).

2. Binary trees. Number of full binary trees with \(n+1\) leaves (or plane binary trees with \(n\) internal nodes)—recursive structure: left subtree \(C_i\), right \(C_{n-1-i}\).

3. Noncrossing handshakes / triangulations. Ways to connect \(2n\) people around a table with \(n\) non-intersecting handshakes; or triangulations of a convex \((n+2)\)-gon: \(C_n\).

Why divide by \(n+1\)? Total paths \((0,0)\to(n,n)\): \(\binom{2n}{n}\). The reflection principle subtracts the bad paths (those that touch \(y=x+1\)), leaving \(\frac{1}{n+1}\binom{2n}{n}\). Full reflection proof is optional; remember the formula and interpretations.

Worked examples

Example 1 — Expand

\((x+y)^4 = x^4+4x^3y+6x^2y^2+4xy^3+y^4\).

Example 2 — Coefficient

Coefficient of \(x^3y^4\) in \((x+y)^7\): \(\binom{7}{4}=35\) (or \(\binom{7}{3}\)).

Example 3 — Evaluate sums

\(\sum_{k=0}^{5}\binom{5}{k}=32\).
\(\sum_{k=0}^{5}(-1)^k\binom{5}{k}=0\).
\(\sum_{k}k\binom{5}{k}=5\cdot 16=80\).

Example 4 — Pascal

\(\binom{10}{4}=\binom{9}{4}+\binom{9}{3}=126+84=210\).

Example 5 — Absorption

\(4\binom{10}{4}=10\binom{9}{3}\): left \(4\cdot 210=840\); right \(10\cdot 84=840\).

Example 6 — Vandermonde

\(\binom{5+3}{4}=\binom{8}{4}=70\);
\(\sum_k\binom{5}{k}\binom{3}{4-k}=\binom{5}{1}\binom{3}{3}+\binom{5}{2}\binom{3}{2}+\binom{5}{3}\binom{3}{1}+\binom{5}{4}\binom{3}{0}=5+30+30+5=70\).

Example 7 — Even/odd subsets

\(n=6\): even-sized subsets \(2^5=32\); odd \(32\); difference \(0\).

Example 8 — Extract from \((1+x)^n\)

Coefficient of \(x^k\) in \((1+x)^n\) is \(\binom{n}{k}\).
Coefficient of \(x^3\) in \((1+x)^{10}\): \(\binom{10}{3}=120\).

Example 9 — \((1-x)^n\)

\((1-x)^n=\sum\binom{n}{k}(-1)^k x^k\).
Sum of coefficients: \((1-1)^n=0\) for \(n>0\).

Example 10 — Catalan compute

\(C_4=\frac{1}{5}\binom{8}{4}=\frac{70}{5}=14\).
\(C_3=\frac{1}{4}\binom{6}{3}=\frac{20}{4}=5\).

Example 11 — Parentheses

\(n=3\) balanced strings: ((())), (()()), (())(), ()(()), ()()(). Five \(=C_3\).

Example 12 — Binary trees

Plane binary trees with 3 internal nodes: \(C_3=5\) shapes.

Example 13 — Hockey-stick small

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

Example 14 — Identity challenge

Prove \(\sum_{k}\binom{n}{k}^2=\binom{2n}{n}\) via Vandermonde: \(\binom{n}{k}\binom{n}{n-k}\) and \(\binom{n+n}{n}\).

Example 15 — Expected weight lite

If each subset equally likely, expected size of random subset of \([n]\) is \(\frac{1}{2^n}\sum k\binom{n}{k}=\frac{n}{2}\).

Exercises

1. Expand \((x+2)^5\) fully.
   
2. Coefficient of \(x^2y^5\) in \((x+y)^7\); of \(x^4\) in \((1+x)^{12}\).
   
3. Prove Pascal combinatorially and algebraically (write both).
   
4. Prove \(k\binom{n}{k}=n\binom{n-1}{k-1}\) by double counting.
   
5. Evaluate \(\sum k\binom{n}{k}\) and \(\sum\binom{n}{k}\).
   
6. Prove alternating sum is \(0\) for \(n>0\) by pairing.
   
7. Vandermonde: verify for \(m=4,n=3,r=3\).
   
8. Hockey-stick: verify \(\sum_{i=3}^{7}\binom{i}{3}=\binom{8}{4}\).
   
9. Compute \(C_0\) through \(C_6\) by formula.
   
10. List all Dyck words for \(n=3\).
    
11. Show \(C_n=\binom{2n}{n}-\binom{2n}{n-1}\) equals \(\frac{1}{n+1}\binom{2n}{n}\).
    
12. Use recurrence to get \(C_4\) from smaller values.
    
13. Prove \(\sum\binom{n}{k}^2=\binom{2n}{n}\).
    
14. Coefficient of \(x^3\) in \((2+x)^6\).
    
15. Story for \(\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=2^n\).
    
16. How many subsets of \([10]\) have even size?
    
17. Expand \((x-y)^4\); check alternating pattern.
    
18. CS: number of ways \(2n\) calls push/pop on a stack stay valid—Catalan.
    
19. Multinomial: expand \((x+y+z)^2\).
    
20. Prove \(\binom{n}{k}/\binom{n}{k-1}=(n-k+1)/k\) for \(k\ge 1\).
    
21. Find \(n\) such that \(\binom{n}{2}=45\).
    
22. Row sum of Pascal row 8.
    
23. Challenge: reflection proof sketch for Catalan (optional paragraph).
    
24. Show \(\sum_{k\text{ even}}\binom{n}{k}=2^{n-1}\) for \(n\ge 1\).
    
25. Application: number of binary strings length \(2n\) with \(n\) zeros, \(n\) ones, all prefixes have #zeros ≥ #ones—Catalan.

CS connection

• Complexity / generating functions: \((1+x)^n\) tracks subset weights.
  
• Random algorithms: \(\sum k\binom{n}{k}/2^n=n/2\) average Hamming weight.
  
• Parsing / compilers: Catalan counts valid parenthesis and stack-sortable patterns.
  
• BST shapes: \(C_n\) binary search tree shapes on \(n\) keys (plane binary trees).
  
• Dynamic programming: binomial recurrences and Catalan recurrence are DP prototypes.

Common pitfalls

Pitfall	What to do instead
Mixing \(x^{n-k}y^k\) index conventions	Track which variable’s power is \(k\)
Forgetting \(n>0\) for alternating sum	\((1-1)^0=1\)
Catalan \(\binom{2n}{n}\) without \(1/(n+1)\)	Full central binomial is larger
Algebra only, no story	Both proofs strengthen memory
Off-by-one in Catalan index	\(C_n\) uses \(\binom{2n}{n}\), \(n\) pairs

Checkpoint

• State binomial theorem and prove via expansion story
  
• Pascal: combinatorial + algebraic
  
• Absorption and \(\sum k\binom{n}{k}=n2^{n-1}\)
  
• \(C_n=\frac{1}{n+1}\binom{2n}{n}\) and three interpretations
  
• Compute \(C_4\), \(C_5\) cold
  
• Exercises 1–15
  
• Vandermonde story in one sentence

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

2. \(\binom{7}{5}=21\); \(\binom{12}{4}=495\).
   
3. \(n2^{n-1}\); \(2^n\).
   
4. \(1,1,2,5,14,42,132\).
   
5. \(\binom{2n}{n}-\binom{2n}{n-1}=\binom{2n}{n}\bigl(1-\frac{n}{n+1}\bigr)=\frac{1}{n+1}\binom{2n}{n}\).
   
6. Vandermonde with \(m=n\), \(r=n\).
   
7. \(2^9=512\).
   
8. \(n(n-1)/2=45\Rightarrow n=10\).

Deepening notes

Algebraic induction template for binomial theorem

Base \(n=0\). Assume \((x+y)^{n-1}=\sum\binom{n-1}{k}x^{n-1-k}y^k\). Multiply by \((x+y)\); coefficient of \(x^{n-k}y^k\) is \(\binom{n-1}{k}+\binom{n-1}{k-1}\). Apply Pascal. Write this once without notes.

Generating identities from \((1+x)^n\)

Differentiate: \(n(1+x)^{n-1}=\sum k\binom{n}{k}x^{k-1}\); set \(x=1\) recover \(\sum k\binom{n}{k}=n2^{n-1}\).
Second derivative / \(x\) tricks give \(\sum k(k-1)\binom{n}{k}=n(n-1)2^{n-2}\).

Catalan reflection (outline)

Bad paths \((0,0)\to(n,n)\) that touch \(y=x+1\): reflect prefix until first touch over the line \(y=x+1\) to map bijectively to paths \((0,0)\to(n,n)\) with one extra North early—count \(\binom{2n}{n-1}\). Subtract from \(\binom{2n}{n}\).

Pascal triangle patterns

Row sums powers of 2; alternating row sums 0; hockey-stick along diagonals; binary carry patterns optional.

Extra drills

D1. Expand \((2x-y)^4\).
D2. Prove \(\sum (-1)^k\binom{n}{k}=0\) algebraically via \((1-1)^n\).
D3. Vandermonde numeric \(m=6,n=5,r=4\).
D4. Hockey-stick \(\sum_{i=2}^{8}\binom{i}{2}\).
D5. \(C_6\) by formula and by recurrence.
D6. List BST shapes for 3 keys.
D7. Coefficient of \(x^5\) in \((1+x+x^2/2!+\cdots)\) optional—skip; instead \((3+x)^5\) coeff of \(x^2\).
D8. Story for \(\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}\).

Flash

\((x+y)^n=\sum\binom{n}{k}x^{n-k}y^k\), \(C_n=\frac1{n+1}\binom{2n}{n}\), \(\sum k\binom{n}{k}=n2^{n-1}\).

Exam drill block

E1. Expand \((x+3)^4\) fully.
E2. Coeff of \(x^4y^3\) in \((x+y)^7\); of \(x^5\) in \((2+x)^8\).
E3. Prove Pascal combinatorially in ≤6 lines.
E4. Evaluate \(\sum k\binom{8}{k}\) and \(\sum\binom{8}{k}(-1)^k\).
E5. Vandermonde numeric: \(m=5,n=4,r=3\).
E6. Hockey-stick: \(\sum_{i=4}^{9}\binom{i}{4}\).
E7. Compute \(C_5\) two ways (formula + recurrence).
E8. List Dyck words for \(n=2\); count \(C_2\).
E9. Prove \(\sum\binom{n}{k}^2=\binom{2n}{n}\) via Vandermonde story.
E10. True/false: (i) \(C_n=\binom{2n}{n}\) (ii) \(\sum k\binom{n}{k}=n2^{n-1}\) (iii) alternating sum is \(0\) for \(n=0\).

Mini solutions

E1. \(x^4+12x^3+54x^2+108x+81\).
E2. \(\binom{7}{3}=35\); \(\binom{8}{5}2^{3}=56\cdot 8=448\).
E4. \(8\cdot 2^{7}=1024\); \(0\).
E5. \(\binom{9}{3}=84\).
E6. \(\binom{10}{5}=252\).
E7. \(C_5=42\).
E10. F; T; F (\((1-1)^0=1\)).

Synthesis

The binomial theorem equates algebra (expand products) with counting (choose \(k\) factors for \(y\)). Pascal, absorption, Vandermonde, and hockey-stick are the identity core—always keep a story and an algebra path. Catalan numbers package lattice-path, parentheses, and tree counts into one sequence; remember the \(1/(n+1)\) factor.

S1. Full dual proof of absorption.
S2. Catalan \(C_4\) by formula, recurrence, and parentheses list.
S3. Differentiate \((1+x)^n\) to recover \(\sum k\binom{n}{k}\) once without notes.

Tomorrow

Day 51 — Stars and bars: nonnegative and positive solutions to linear equations; multiset combinations; upper bounds via IE preview.

---

Day 51 — Stars and bars

Stage V · concept day
Goal: Count nonnegative and positive integer solutions to \(x_1+\cdots+x_k=n\); interpret as multiset combinations and identical-item distributions; enforce upper bounds with inclusion–exclusion.

Why this matters

Distributing identical resources (CPU quanta, identical tokens, indistinguishable errors), counting multisets, and solving linear Diophantine equations in the nonnegative orthant are stars and bars. Hash bucket load vectors, integer knapsacks (counting, not optimizing), and “how many ways to make change” lite all use this template. Upper bounds force IE—linking tomorrow.

Theory

The basic problem

Count the number of integer solutions to

\[ x_1 + x_2 + \cdots + x_k = n \]

under various constraints on the \(x_i\).

Nonnegative solutions

If \(x_i\ge 0\) for all \(i\), the number of solutions is

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

Stars-and-bars story. Place \(n\) identical stars (units) in a row and insert \(k-1\) bars (dividers) to split them into \(k\) (possibly empty) groups. Total positions to fill: \(n+(k-1)\); choose positions for bars (or for stars):

\[ \underbrace{*\ *\ \cdots\ *}_{n\text{ stars}} \quad\text{and}\quad \underbrace{|\ \cdots\ |}_{k-1\text{ bars}}. \]

Example: \(n=5\), \(k=3\): **|*|** means \((2,1,2)\).

Bijection with multisets. A multiset of size \(n\) from \(k\) types has \(x_i\) copies of type \(i\); \(\sum x_i=n\), \(x_i\ge 0\). So multiset combinations:

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

Positive solutions

If \(x_i\ge 1\) for all \(i\) (and necessarily \(n\ge k\)), set \(y_i=x_i-1\ge 0\). Then

\[ (y_1+1)+\cdots+(y_k+1)=n \implies y_1+\cdots+y_k=n-k, \]

so number of positive solutions is

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

Direct story: place \(n\) stars in a row; there are \(n-1\) gaps between them; choose \(k-1\) of those gaps to put a bar (forces nonempty groups).

Lower bounds other than 0 or 1

If \(x_i\ge c_i\), set \(y_i=x_i-c_i\ge 0\). Then \(\sum y_i = n-\sum c_i\), nonnegative count.

Upper bounds via inclusion–exclusion

Count nonnegative solutions to \(\sum_{i=1}^{k}x_i=n\) with each \(x_j\le M\).

1. Start with unrestricted nonnegative: \(N=\binom{n+k-1}{k-1}\).
   
2. Let \(A_j\) be solutions with \(x_j\ge M+1\). Set \(x_j'=x_j-(M+1)\ge 0\); then \(\sum x' + \cdots = n-(M+1)\), so \(|A_j|=\binom{(n-M-1)+k-1}{k-1}\) if \(n\ge M+1\), else \(0\).
   
3. \(|A_j\cap A_\ell|\) similarly with \(n-2(M+1)\), etc.
   
4. IE:

\[ \bigl|\overline{\text{violations}}\bigr| = N - \binom{k}{1}|A_1| + \binom{k}{2}|A_1\cap A_2| - \cdots. \]

(Full IE theory Day 52; this is the standard application.)

Distributing identical items to distinct bins

• \(n\) identical items, \(k\) distinct bins, bins may be empty: \(\binom{n+k-1}{k-1}\).
  
• Bins nonempty: \(\binom{n-1}{k-1}\).
  
• If bins are identical, you count integer partitions of \(n\) into at most \(k\) parts—harder, not stars-and-bars (no simple binomial closed form). Always check: are recipients distinguishable?

Distributing distinct items (contrast)

\(n\) distinct items to \(k\) distinct bins: \(k^n\) (each item chooses a bin)—product rule, not stars and bars.
If bins nonempty: surjections \(k!\,S(n,k)\) (Day 52).

Change-making lite

Number of ways to make \(n\) cents with denominations that are unlimited and order of coins irrelevant = nonnegative solutions with one variable per denomination—stars and bars only if every denomination is \(1\) or variables are free; with restricted coin values it is a generating-function / DP problem. Do not force stars-and-bars on arbitrary coin sets.

Worked examples

Example 1 — Nonnegative

\(x+y+z=5\), \(x,y,z\ge 0\): \(\binom{5+3-1}{3-1}=\binom{7}{2}=21\).

Example 2 — Positive

\(x+y+z=5\), \(x,y,z\ge 1\): \(\binom{5-1}{3-1}=\binom{4}{2}=6\).
List: \((1,1,3)\) and perms (3), \((1,2,2)\) and perms (3).

Example 3 — Multisets

Number of multisets of size 6 from 4 colors: \(\binom{4+6-1}{6}=\binom{9}{6}=84\).

Example 4 — Lower bounds

\(x+y+z=10\), \(x\ge 2\), \(y\ge 3\), \(z\ge 0\): set \(x'=x-2\), \(y'=y-3\); \(x'+y'+z=5\); \(\binom{5+2}{2}=\binom{7}{2}=21\).

Example 5 — One upper bound

\(x+y+z=10\), \(x,y,z\ge 0\), \(x\le 4\).
Total: \(\binom{12}{2}=66\).
\(A\): \(x\ge 5\), \(x'=x-5\), \(x'+y+z=5\): \(\binom{7}{2}=21\).
Answer: \(66-21=45\).

Example 6 — All variables capped

\(x+y+z=7\), \(0\le x,y,z\le 4\).
Total: \(\binom{9}{2}=36\).
\(A_i\): \(x_i\ge 5\): \(\binom{7-5+2}{2}=\binom{4}{2}=6\) each; \(\binom{3}{1}\cdot 6=18\).
\(A_i\cap A_j\): \(x_i,x_j\ge 5\) → sum at least 10 > 7: empty.
Answer: \(36-18=18\).

Example 7 — Identical cookies, distinct kids

10 identical cookies, 4 distinct children, any number including zero: \(\binom{10+3}{3}=\binom{13}{3}=286\).
Each child at least one: \(\binom{9}{3}=84\).

Example 8 — Distinct cookies

10 distinct cookies, 4 children: \(4^{10}\) (not stars and bars).

Example 9 — Equations with more variables

\(x_1+\cdots+x_5=3\), \(x_i\ge 0\): \(\binom{3+5-1}{3}=\binom{7}{3}=35\).

Example 10 — Bars visualization

\(n=3,k=2\): stars/bars patterns: ***|, **|*, *|**, |*** → solutions \((3,0),(2,1),(1,2),(0,3)\): \(\binom{4}{1}=4\).

Example 11 — Positive via gaps

\(x_1+x_2+x_3+x_4=10\), \(x_i\ge 1\): \(\binom{9}{3}=84\).

Example 12 — Integer compositions vs partitions

Ordered positive solutions = compositions of \(n\) into \(k\) parts: \(\binom{n-1}{k-1}\).
Unordered = partitions: different problem.

Example 13 — Two equations? (careful)

\(x+y=5\), \(x,y\ge 0\): \(6\) solutions. Not a 2D free problem—one free variable.

Example 14 — IE double cap

\(x+y=10\), \(x,y\ge 0\), \(x\le 6\), \(y\le 6\).
Total 11 solutions \((0,10)\ldots(10,0)\).
Violate \(x\ge 7\): \((7,3),(8,2),(9,1),(10,0)\) — 4; similarly \(y\ge 7\): 4; both impossible.
Answer: \(11-4-4=3\) namely \((4,6),(5,5),(6,4)\). Wait also \((4,6)\)… actually \((4,6),(5,5),(6,4)\) only if both \(\le 6\); also \((3,7)\) removed, etc. List: \((4,6),(5,5),(6,4)\)—only 3? \((7,3)\) removed. What about \((2,8)\)? Removed. Actually also \((6,4),(5,5),(4,6)\)—yes 3. But \((3,7)\) out. Hmm \((10,0)\) out. Correct: \(x\) from \(\max(0,10-6)=4\) to \(\min(10,6)=6\): three values.

Example 15 — CS loads

Distribute 12 identical requests to 3 servers, each server at most 5:
Total \(\binom{12+2}{2}=91\); \(A_i\): one server \(\ge 6\): \(x'=x-6\), sum 6: \(\binom{6+2}{2}=28\); three such; \(A_i\cap A_j\): two servers \(\ge 6\) → sum \(\ge 12\), third \(\ge 0\): sum vars after sub \(12-12=0\): \(\binom{0+2}{2}=1\) each pair; \(\binom{3}{2}=3\); triple: \(12-18<0\): 0.
Answer: \(91-3\cdot 28+3=91-84+3=10\).

Exercises

1. Nonnegative solutions: \(x+y+z+w=6\).
   
2. Positive solutions: \(x+y+z=9\).
   
3. Multisets of size 5 from 7 types.
   
4. \(x_1+\cdots+x_4=10\), each \(x_i\ge 2\).
   
5. \(x+y+z=8\), \(x\ge 0\), \(y\ge 0\), \(z\ge 0\), \(x\le 3\) (one IE/subtraction).
   
6. \(x+y+z=8\), each variable \(\le 5\).
   
7. Identical muffins to 5 distinct students, none empty, 12 muffins.
   
8. Same with empty allowed.
   
9. Distinct muffins (12 distinct) to 5 students: formula.
   
10. Draw all stars-and-bars for \(n=2\), \(k=3\).
    
11. Prove positive formula via \(y_i=x_i-1\).
    
12. Number of compositions of 7 into exactly 3 positive parts.
    
13. Number of compositions of 7 into any number of positive parts (\(2^{6}\)).
    
14. \(x+y=n\), \(x,y\ge 0\): show count is \(n+1\).
    
15. Ways to buy 10 doughnuts from 4 flavors (unlimited each, order irrelevant).
    
16. Same but at least one of each flavor.
    
17. CS: 20 identical jobs, 4 machines, each machine between 3 and 8 inclusive—set up IE.
    
18. Why partitions of 10 into 3 parts ≠ \(\binom{9}{2}\)?
    
19. Nonnegative solutions to \(x_1+\cdots+x_k=n\) with \(x_1=0\) forced.
    
20. Generate function awareness: coefficient of \(x^n\) in \((1+x+x^2+\cdots)^k=(1-x)^{-k}\).
    
21. \(x+2y+z=5\) — explain why plain stars-and-bars fails (not all coeffs 1).
    
22. Distribute 6 identical balls into 3 distinct boxes, no box more than 3.
    
23. Multiset combinations \(\binom{n+k-1}{k}\) vs \(\binom{n}{k}\)—when equal?
    
24. Challenge: positive solutions \(x_1+\cdots+x_k=n\) with each \(x_i\le M\)—write IE form.
    
25. Ice cream: 3 scoops, 5 flavors, rep OK, order irrelevant vs order relevant.

CS connection

• Load vectors: identical tasks on distinct servers → nonnegative compositions of load.
  
• Histogram counts: multiset of bucket hits.
  
• Integer resource allocation in OS / cloud quotas.
  
• Stars and bars in type inhabitation / linear logic lite: resource counting.
  
• Generating functions \((1-x)^{-k}\) encode the same counts for DP.

Common pitfalls

Pitfall	What to do instead
Distinct vs identical items	Distinct → \(k^n\); identical → stars/bars
Identical vs distinct bins	Identical bins → partitions, not \(\binom{n}{k}\)
Forgetting empty bins allowed or not	\(\ge 0\) vs \(\ge 1\) formulas
Upper bounds without IE	Subtract (and add back) systematically
Variables with coefficients \(\neq 1\)	Not pure stars-and-bars
Off-by-one in \(\binom{n+k-1}{k-1}\)	Memorize both \(\binom{n+k-1}{n}\) forms

Checkpoint

• Nonnegative formula + stars/bars story
  
• Positive formula + substitution
  
• Multiset interpretation
  
• One upper-bound IE computation by hand
  
• Distinct items contrast \(k^n\)
  
• Exercises 1–15
  
• Cold: \(x+y+z=10\) nonnegative; positive; each \(\le 6\)

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

1. \(\binom{6+3}{3}=\binom{9}{3}=84\).
   
2. \(\binom{8}{2}=28\).
   
3. \(\binom{7+5-1}{5}=\binom{11}{5}=462\).
   
4. \(y_i=x_i-2\), sum \(y=2\): \(\binom{2+3}{3}=\binom{5}{3}=10\).
   
5. \(\binom{11}{4}=330\).
   
6. \(\binom{12+4}{4}=\binom{16}{4}=1820\).
   
7. \(5^{12}\).
   
8. \(2^{6}=64\).
   
9. \(\binom{10+3}{3}=286\).
   
10. Multiset \(\binom{5+3-1}{3}=35\); ordered \(5^3=125\).

Deepening notes

Two pictures, one formula

Stars and bars: \(n\) stars, \(k-1\) bars, choose positions.
Weak compositions: ordered \(k\)-tuples of nonnegative integers summing to \(n\).
Same count \(\binom{n+k-1}{k-1}\).

Positive via gaps

\(n\) stars in a row create \(n-1\) interior gaps; choose \(k-1\) gaps for bars ⇒ nonempty bins \(\binom{n-1}{k-1}\).

Generating functions link

Each variable \(x_i\) contributes factor \((1+x+x^2+\cdots)=1/(1-x)\). Product \((1-x)^{-k}\); coefficient of \(x^n\) is \(\binom{n+k-1}{k-1}\).

Upper bounds checklist

1. Unrestricted nonnegative count \(N\).
   
2. For each \(j\), force \(x_j\ge M+1\) by substitution.
   
3. IE over the family \(\{A_j\}\).
   
4. Stop when remaining sum negative (term 0).

Identical vs distinct checklist

Items	Bins	Empty OK?	Count
Identical	Distinct	Yes	\(\binom{n+k-1}{k-1}\)
Identical	Distinct	No	\(\binom{n-1}{k-1}\)
Distinct	Distinct	Yes	\(k^n\)
Distinct	Distinct	No	surjections
Identical	Identical	—	partitions (harder)

Extra drills

D1. \(x_1+\cdots+x_6=4\) nonnegative.
D2. Positive solutions \(x+y+z+w=11\).
D3. \(x+y+z=9\), each \(\le 4\).
D4. 15 identical jobs, 4 servers, each ≥2.
D5. Multisets size 7 from 3 types—list when small.
D6. Why \(x+2y=5\) needs cases on \(y\).
D7. Compositions of 8 into 3 parts.
D8. IE: \(x+y+z=10\), each ≤5—compute fully.

Flash

Nonneg: \(\binom{n+k-1}{k-1}\); Pos: \(\binom{n-1}{k-1}\); Multiset size \(k\) from \(n\) types: \(\binom{n+k-1}{k}\).

Exam drill block

E1. Nonnegative solutions: \(x_1+\cdots+x_5=12\).
E2. Positive solutions: \(x_1+\cdots+x_5=12\).
E3. \(x+y+z=10\) with each \(x_i\ge 2\).
E4. Multisets of size 8 from 5 flavors.
E5. \(x+y+z=9\), each \(\le 5\)—set up IE (full count).
E6. Distinguish: identical balls / distinct bins / empty OK vs not.
E7. Number of weak compositions of 7 into 4 parts.
E8. Compositions of 7 into exactly 3 positive parts.
E9. True/false: (i) stars-bars needs identical items (ii) \(k^n\) is stars-bars (iii) upper bounds use IE.
E10. CS: distribute 15 identical requests to 4 servers, each server ≥1.

Mini solutions

E1. \(\binom{12+5-1}{12}=\binom{16}{12}=1820\).
E2. \(\binom{12-1}{5-1}=\binom{11}{4}=330\).
E3. \(y_i=x_i-2\), sum \(y=4\): \(\binom{4+3-1}{4}=15\).
E4. \(\binom{5+8-1}{8}=\binom{12}{8}=495\).
E5. Unrestricted \(\binom{11}{2}=55\); one var ≥6: \(\binom{5}{2}=10\) ×3 =30; two vars ≥6: sum −3 impossible → \(55-30=25\).
E8. \(\binom{6}{2}=15\).
E9. T (story); F (distinct items); T.
E10. Positive: \(\binom{14}{3}=364\).

Synthesis

Stars-and-bars counts identical items into distinct bins. Nonnegative ↔︎ weak compositions \(\binom{n+k-1}{k-1}\); positive ↔︎ strict \(\binom{n-1}{k-1}\) via \(y_i=x_i-1\) or gap method. Multisets are the same count rephrased. Distinct items use \(k^n\) or surjections—not stars-bars. Upper bounds: substitute and inclusion–exclusion (Day 52).

S1. Solve \(x_1+\cdots+x_4=15\), \(0\le x_i\le 6\) fully with IE.
S2. Write the generating-function one-liner for \((1-x)^{-k}\).
S3. Cold: multiset size 5 from 6; positive \(x+y+z+w=10\).

Tomorrow

Day 52 — Inclusion–exclusion: 2–3 sets, general formula, surjections, derangements as IE special case.

---

Day 52 — Inclusion–exclusion

Stage V · concept day
Goal: Apply inclusion–exclusion for 2–3 sets and the general pattern; count surjections and derangements; enforce upper bounds in stars-and-bars; connect to Stirling numbers of the second kind awareness.

Why this matters

Naive sum overcounts unions. Security policies (“violates rule A or B”), covering residual cases, surjective assignments, and “nobody gets their own hat” need inclusion–exclusion (IE). It is the systematic correction to the sum rule when classes overlap. Master the pattern once; re-specialize forever.

Theory

Two sets

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

Why: \(|A|+|B|\) counts \(A\cap B\) twice; subtract once so it is counted once.

Complement form: \(|U\setminus(A\cup B)|=|U|-|A|-|B|+|A\cap B|\) (neither property).

Three sets

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

Venn region check: elements only in \(A\cap B\cap C\) are counted \(3-3+1=1\) time; elements in exactly two sets: \(2-1=1\); elements in exactly one: \(1\).

General formula

For sets \(A_1,\ldots,A_m\subseteq U\),

\[ \Bigl|\bigcup_{i=1}^{m} A_i\Bigr| = \sum_i |A_i| - \sum_{i<j}|A_i\cap A_j| + \sum_{i<j<k}|A_i\cap A_j\cap A_k| - \cdots + (-1)^{m+1}|A_1\cap\cdots\cap A_m|. \]

Sign pattern: intersections of \(r\) sets get sign \((-1)^{r+1}\).

Property form (often best for counting)

Let \(U\) be a universe. Property \(P_i\): element has feature \(i\). Let \(A_i=\{x\in U:x\text{ has }P_i\}\). Number of elements with none of the properties:

\[ N_{\text{none}} = |U| - \sum|A_i| + \sum|A_i\cap A_j| - \sum|A_i\cap A_j\cap A_k| + \cdots + (-1)^m |A_1\cap\cdots\cap A_m|. \]

Number with at least one property: \(|U|-N_{\text{none}}\).

Counting surjections (onto functions)

Number of surjective functions \(f:N\to K\) with \(|N|=n\), \(|K|=k\):

Let \(U=\) all functions: \(|U|=k^n\).
Let \(A_i=\) functions that miss element \(i\) in the codomain (\(|A_i|=(k-1)^n\)).
Then \(A_{i_1}\cap\cdots\cap A_{i_r}\) = functions missing \(r\) particular codomain points: \((k-r)^n\).
Number missing none (i.e. surjections):

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

Stirling numbers of the second kind (awareness)

\(S(n,k)\) = number of ways to partition \(n\) distinct objects into \(k\) nonempty unlabeled subsets. Then

\[ \text{surjections } = k!\, S(n,k), \]

because label the \(k\) blocks by codomain elements. So

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

Derangements as IE special case

Permutations of \([n]\) with no fixed points: \(U=n!\) permutations; \(A_i=\) permutations fixing \(i\); \(|A_{i_1}\cap\cdots\cap A_{i_r}|=(n-r)!\). Thus

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

(Recover Day 48 formula.)

IE + stars and bars (upper bounds)

Nonnegative solutions to \(x_1+\cdots+x_k=n\) with each \(x_j\le M\):
\(U\) = all nonnegative solutions, \(|U|=\binom{n+k-1}{k-1}\);
\(A_j\): \(x_j\ge M+1\); substitute and apply general IE (Day 51 examples).

Divisibility counting

How many integers in \(\{1,\ldots,N\}\) are divisible by \(a\) or \(b\)?
\(|A\cup B|=\lfloor N/a\rfloor+\lfloor N/b\rfloor-\lfloor N/\mathrm{lcm}(a,b)\rfloor\).

Worked examples

Example 1 — Two sets

In a class of 40: 25 take math, 20 take CS, 10 both. Math or CS: \(25+20-10=35\). Neither: \(40-35=5\).

Example 2 — Three sets

\(|A|=20,|B|=15,|C|=10\), \(|A\cap B|=8\), \(|A\cap C|=6\), \(|B\cap C|=5\), \(|A\cap B\cap C|=3\), \(|U|=50\).
Union: \(20+15+10-8-6-5+3=29\). None: \(50-29=21\).

Example 3 — Bit-strings OR

Length-4 bit-strings starting with 1 or ending with 1:
\(|A|=8\), \(|B|=8\), \(|A\cap B|=4\) → \(8+8-4=12\).
Complement: neither = start 0 and end 0: \(2^2=4\); total \(16-4=12\).

Example 4 — Divisibility

\(\{1,\ldots,100\}\) divisible by 2 or 5: \(\lfloor 100/2\rfloor+\lfloor 100/5\rfloor-\lfloor 100/10\rfloor=50+20-10=60\).

Example 5 — Three primes

\(\{1,\ldots,210\}\) divisible by 2, 3, or 5:
\(\lfloor 210/2\rfloor+\lfloor 210/3\rfloor+\lfloor 210/5\rfloor -\lfloor 210/6\rfloor-\lfloor 210/10\rfloor-\lfloor 210/15\rfloor +\lfloor 210/30\rfloor\)
\(=105+70+42-35-21-14+7=154\).

Example 6 — Surjections \([4]\to[2]\)

\(\sum_{i=0}^{2}(-1)^i\binom{2}{i}(2-i)^4 = \binom{2}{0}2^4-\binom{2}{1}1^4+\binom{2}{2}0^4=16-2+0=14\).
Check: \(2^4-2=14\) (exclude 2 constants). \(S(4,2)=7\), and \(2!\cdot 7=14\).

Example 7 — Surjections \([5]\to[3]\)

\(\binom{3}{0}3^5-\binom{3}{1}2^5+\binom{3}{2}1^5-\binom{3}{3}0^5=243-3\cdot 32+3\cdot 1-0=243-96+3=150\).
\(S(5,3)=25\), \(3!\cdot 25=150\).

Example 8 — Derangement \(!4\)

\(4!(1-1+1/2-1/6+1/24)=24\cdot\frac{9}{24}=9\).
Or: \(24-\binom{4}{1}6+\binom{4}{2}2-\binom{4}{3}1+\binom{4}{4}0=24-24+12-4+1=9\).

Example 9 — Derangement \(!5\)

\(120(1-1+1/2-1/6+1/24-1/120)=120\cdot\frac{44}{120}=44\).

Example 10 — Stars-bars + IE

\(x+y+z=7\), \(0\le x,y,z\le 4\):
Total \(\binom{9}{2}=36\); one variable \(\ge 5\): \(\binom{3+2}{2}=\binom{5}{2}=10\)? Wait \(n'=7-5=2\): \(\binom{2+2}{2}=\binom{4}{2}=6\); \(\times 3=18\); pairwise \(\ge 5\) each: \(7-10<0\): 0. Answer \(36-18=18\).

Example 11 — Passwords at least one digit

Length 4 over 26 letters + 10 digits: \(36^4-26^4\) (complement = no digit). Same as IE with one property “is letter-only” actually pure complement.

Example 12 — Onto maps as assignments

Assign 6 distinct jobs to 3 distinct workers so each worker gets at least one: surjections \(3!\,S(6,3)\).
\(S(6,3)=90\), answer \(6\cdot 90=540\).
IE: \(\binom{3}{0}3^6-\binom{3}{1}2^6+\binom{3}{2}1^6=729-3\cdot 64+3=729-192+3=540\).

Example 13 — Exactly one property

Sometimes you want exactly one of \(A,B\): \(|A|+|B|-2|A\cap B|\).
(Exactly the symmetric difference size.)

Example 14 — Missed intersections

If you compute \(|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|\) and forget \(+|A\cap B\cap C|\), triple-overlap elements are undercounted (0 times instead of 1).

Example 15 — Probability of derangement

\(P(\text{random perm is derangement})\to 1/e\). For \(n=5\): \(44/120\approx 0.3667\).

Exercises

1. Two-set IE formula; three-set formula—write from memory.
   
2. Class: 30 French, 25 German, 10 both, 50 total. Neither language?
   
3. Length-5 bit-strings with first bit 1 or last bit 0—compute via IE.
   
4. \(\{1,\ldots,120\}\) divisible by 3 or 4.
   
5. \(\{1,\ldots,120\}\) divisible by 2, 3, or 5.
   
6. Surjections \([3]\to[3]\); \([4]\to[3]\); \([6]\to[4]\).
   
7. Compute \(S(4,2)\) and \(S(5,2)\) from the formula.
   
8. \(!6\) by formula; compare to \(\mathrm{round}(720/e)\).
   
9. Number of permutations of \([7]\) with no fixed points.
   
10. \(x+y+z+w=12\), each \(x_i\le 5\)—set up full IE (compute).
    
11. Functions \([5]\to[5]\) that are not surjective (use total − surjections).
    
12. Exactly 2 of 3 properties: optional formula awareness.
    
13. Prove two-set IE from indicator functions: \(1_{A\cup B}=1_A+1_B-1_{A\cap B}\).
    
14. Integers \(1..1000\) not divisible by 2, 3, or 5.
    
15. Secret Santa: 8 people, no one draws self—count.
    
16. Assign 5 distinct TAs to 3 sections, each section ≥1 TA.
    
17. Prove \(!n=n\cdot!(n-1)+(-1)^n\) for \(n\ge 1\) (optional induction).
    
18. Passwords length 5 from {A..Z,0..9} with at least one letter and at least one digit.
    
19. Why \(0^n\) appears in surjection formula for \(i=k\) when \(n>0\)?
    
20. CS: hash \(n\) distinct keys into \(k\) buckets, every bucket nonempty—count.
    
21. List all derangements of \(\{1,2,3,4\}\) (9 of them)—structure.
    
22. Venn: given all region sizes, recover \(|A\cup B\cup C|\).
    
23. Challenge: number of integers ≤ 1000 divisible by at least one of 6,10,15.
    
24. Multisets vs IE: when do you need both?
    
25. Write general IE for \(m=4\) explicitly (all 15 terms grouped).

CS connection

• Constraint violation counts: logs matching any of several error codes.
  
• Coverage: test cases hitting at least one of critical paths.
  
• Surjective allocations: every shard/replica gets ≥1 item.
  
• Derangements: secure shuffles, mixing networks, hat-check problems.
  
• Bloom filters / set sketches culture: IE appears in pure set-size estimation theory.

Common pitfalls

Pitfall	What to do instead
Stopping after pairwise subtract for 3 sets	Add triple back
Wrong sign pattern	\((-1)^{r+1}\) for union form
Surjection: forgetting \(\binom{k}{i}\)	Choose which \(i\) points are missed
\(S(n,k)\) vs \(k!S(n,k)\)	Unlabeled partitions vs labeled surjections
Applying IE when sets already disjoint	Just sum
Floor functions forgotten in divisibility	Use \(\lfloor N/a\rfloor\)

Checkpoint

• 2-set and 3-set formulas cold
  
• General sign pattern
  
• Surjection formula and one numerical check
  
• Derangement as IE; \(!n\approx n!/e\)
  
• One stars-bars upper bound via IE
  
• Exercises 1–15
  
• \(S(n,k)\) relation to surjections in one line

Two personal takeaways:

1. …
   
2. …

Selected mini-solutions

2. Union \(30+25-10=45\) impossible if total 50—wait 45 in language; neither \(5\).
   
3. \(|A|=2^4=16\), \(|B|=16\), \(|A\cap B|=2^3=8\) → \(24\); total \(32\), etc.
   
4. \(\lfloor 120/3\rfloor+\lfloor 120/4\rfloor-\lfloor 120/12\rfloor=40+30-10=60\).
   
5. \(3!=6\); \(\sum(-1)^i\binom{3}{i}(3-i)^4=81-3\cdot 16+3\cdot 1=36\); \([6]\to[4]\) compute similarly.
   
6. \(!6=265\); \(720/e\approx 264.87\).
   
7. \(5^5-5!S(5,5)=3125-120=3005\) not surj; surjections onto \([5]\) are \(5!=120\).
   
8. \(!8=14833\).

Deepening notes

Indicator proof of 2-set IE

For each \(x\), \(1_{A\cup B}(x)=1_A(x)+1_B(x)-1_{A\cap B}(x)\). Sum over \(x\in U\).

General term intuition

An element in exactly \(t\) of the sets \(A_i\) is counted \(\sum_{r=1}^{t}(-1)^{r+1}\binom{t}{r}=1\) times in the union formula (binomial expansion of \((1-1)^t=0\) for \(t>0\) rearranged).

Surjection–Stirling dictionary

Object	Symbol / formula
Partitions of \(n\) into \(k\) nonempty unlabeled	\(S(n,k)\)
Surjections \([n]\to[k]\)	\(k!S(n,k)=\sum_i(-1)^i\binom{k}{i}(k-i)^n\)
All functions	\(k^n\)
Injections	\(P(k,n)\) if \(n\le k\)

Derangement numerical table

\(n\)	\(!n\)	\(n!/e\) rounded
0	1	—
1	0	0
2	1	1
3	2	2
4	9	9
5	44	44
6	265	265

Extra drills

D1. Three-set Venn with given region sizes → union.
D2. \(\{1..200\}\) div by 6 or 10 or 15.
D3. Surjections \([6]\to[3]\).
D4. \(S(5,3)\) from formula.
D5. \(!7\).
D6. \(x+y+z=9\), each ≤4 via IE.
D7. Passwords length 5 from 36 with ≥1 digit.
D8. Probability random perm of 8 is derangement (approx).

Flash

\(|A\cup B|=|A|+|B|-|A\cap B|\); surj \(=\sum(-1)^i\binom{k}{i}(k-i)^n\); \(!n=n!\sum(-1)^k/k!\).

Exam drill block

E1. Three-set IE: \(|A|=20,|B|=25,|C|=18,|A\cap B|=8,|A\cap C|=6,|B\cap C|=7,|A\cap B\cap C|=3\); find \(|A\cup B\cup C|\).
E2. How many integers in \(\{1,\ldots,100\}\) divisible by 2, 3, or 5?
E3. Surjections \([5]\to[3]\); compare to \(3^5\).
E4. \(S(5,2)\) via \(2!S(5,2)=\) surjections onto 2 labels.
E5. Compute \(!5\) and \(!6\) from the series formula.
E6. Passwords length 4 from \(\{A..Z,0..9\}\) with at least one digit—complement.
E7. \(x+y+z=8\), each \(\le 4\), via IE.
E8. Probability a random perm of \(n=7\) is a derangement \(\approx 1/e\).
E9. True/false: (i) IE requires properties be independent (ii) surjections \(=k!S(n,k)\) (iii) \(!n=\lfloor n!/e+1/2\rfloor\) often.
E10. CS: hash \(n\) keys into \(k\) buckets, none empty—name the count.

Mini solutions

E1. \(20+25+18-8-6-7+3=45\).
E2. \(\lfloor100/2\rfloor+\lfloor100/3\rfloor+\lfloor100/5\rfloor-\lfloor100/6\rfloor-\lfloor100/10\rfloor-\lfloor100/15\rfloor+\lfloor100/30\rfloor=50+33+20-16-10-6+3=74\).
E3. \(\sum(-1)^i\binom{3}{i}(3-i)^5=243-3\cdot 32+3\cdot 1=150\); \(3^5=243\).
E5. \(44\); \(265\).
E7. Unrestricted \(\binom{10}{2}=45\); one ≥5: \(\binom{5}{2}=10\) ×3=30; two ≥5: sum −2 impossible → \(15\).
E9. F; T; T (for \(n\neq 0\) standard rounding).
E10. Surjections \([n]\to[k]\).

Synthesis

Inclusion–exclusion subtracts overcounts systematically: union of properties, surjections (no empty codomain labels), derangements (no fixed points), and bounded stars-bars. The general pattern is \(\sum (-1)^r\) times intersections of \(r\) properties. Always define the universe \(U\) and the bad properties \(A_i\) first.

S1. Full IE writeup for \(\{1..210\}\) divisible by 2, 3, or 7.
S2. Derive \(!n\) from IE with \(A_i=\) “\(i\) fixed.”
S3. Cold: surjections \([6]\to[4]\); \(!4\).

Tomorrow

Day 53 — Counting in CS: passwords, states, hashes, execution trees, bit constraints, protocol spaces, \(\log_2\) size.