Day 49 — Combinations

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.