Subsets and paths

Idea: Take the order back out

A committee is a roster with the job titles removed.

• $12\times 11\times 10=1320$ ordered lists
• Each group of $3$ appears $3!=6$ times
• Committees: $\frac{1320}{6}=220$

Formula: n choose k

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\frac{n!}{k!\times (n-k)!}$

Line up n people and take the first k. Reordering inside either group changes nothing.

Idea: Choose the smaller side

Choosing who is in is the same as choosing who is out.

• $\left(\genfrac{}{}{0ex}{}{12}{3}\right)=\left(\genfrac{}{}{0ex}{}{12}{9}\right)=220$
• Compute with the smaller of k and n − k

Common mistake: C(n,k) when roles differ

A committee of $3$ with a chair is not $\left(\genfrac{}{}{0ex}{}{12}{3}\right)$.

Instead Swap test: swap $2$ people; if the outcome changes, roles matter. Here $\left(\genfrac{}{}{0ex}{}{12}{3}\right)\times 3=660$.

Formula: Pascal's rule

$\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{k}\right)$

Split on one element: either it is in or it is not.

Idea: All subsets at once

Each of n elements is in or out, so there are $2^n$ subsets.

• $5$ elements: $2^5=32$ subsets
• With or without one trader: $\left(\genfrac{}{}{0ex}{}{11}{2}\right)+\left(\genfrac{}{}{0ex}{}{11}{3}\right)=220$

Example: Paths on a grid

Walk from $(0,0)$ to $(5,4)$, moving only right or up. How many paths?

1. Every path has $5+4=9$ steps
2. Choose which $4$ go up: $\left(\genfrac{}{}{0ex}{}{9}{4}\right)=126$

Quick check: Through a point

How many paths from $(0,0)$ to $(5,4)$, right or up, pass through $(2,1)$?

Idea: Walk them through it

Say whether order matters and show the swap test in one sentence.

• When you divide, say what you divide out
• On a grid, give the path length, then which steps you choose