Combinations

Definition

A combination is an unordered selection of objects. Order doesn't matter.

Combinations without Repetition

Formula

The number of ways to choose $r$ objects from $n$ distinct objects: $C(n, r) = \binom{n}{r} = \frac{n!}{r!(n-r)!}$

Read as "$n$ choose $r$" or "binomial coefficient."

Example: Choose 3 students from 10: $\binom{10}{3} = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Relationship to Permutations

$\binom{n}{r} = \frac{P(n,r)}{r!}$

We divide by $r!$ to remove the ordering of selected items.

Properties of Binomial Coefficients

Symmetry

$\binom{n}{r} = \binom{n}{n-r}$

Choosing $r$ to include = choosing $n-r$ to exclude.

Pascal's Identity

$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$

Either include a specific element (pick $r-1$ more) or don't (pick all $r$ from rest).

Sum of Row

$\sum_{r=0}^{n} \binom{n}{r} = 2^n$

Total subsets of an $n$-set.

Alternating Sum

$\sum_{r=0}^{n} (-1)^r \binom{n}{r} = 0$

Vandermonde's Identity

$\binom{m+n}{r} = \sum_{k=0}^{r} \binom{m}{k} \binom{n}{r-k}$

Choose $r$ from $m+n$ by partitioning the selection.

Hockey Stick Identity

$\sum_{i=r}^{n} \binom{i}{r} = \binom{n+1}{r+1}$

Pascal's Triangle

Each entry is the sum of two entries above it.

         1
        1 1
       1 2 1
      1 3 3 1
     1 4 6 4 1
    1 5 10 10 5 1

Row $n$ contains $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$.

Combinations with Repetition

When items can be selected more than once (multiset selection):

Formula

Choose $r$ items from $n$ types (with unlimited copies): $\binom{n+r-1}{r} = \binom{n+r-1}{n-1}$

Stars and Bars interpretation:

• $r$ identical stars (items to choose)
• $n-1$ bars (dividers between types)
• Arrange $r$ stars and $n-1$ bars

Example: Buy 5 donuts from 3 flavors: $\binom{3+5-1}{5} = \binom{7}{5} = 21$

Counting Subsets

Type	Count
All subsets of $n$-set	$2^n$
Subsets of size exactly $k$	$\binom{n}{k}$
Subsets of size at most $k$	$\sum_{i=0}^{k} \binom{n}{i}$
Subsets of size at least $k$	$\sum_{i=k}^{n} \binom{n}{i}$
Non-empty subsets	$2^n - 1$

Distributing Objects

Distinct Objects into Distinct Boxes

Each object goes to one of $k$ boxes: $k^n$

Identical Objects into Distinct Boxes

Distribute $n$ identical balls into $k$ boxes: $\binom{n+k-1}{n} = \binom{n+k-1}{k-1}$

With Minimum Requirements

Each of $k$ boxes must have at least 1: $\binom{n-1}{k-1}$

(Place $n$ balls in a row, choose $k-1$ dividers among $n-1$ gaps)

Committee Problems

Basic Committee

Choose committee of $k$ from $n$ people: $\binom{n}{k}$

Committee with Chair

Choose committee of $k$ with a chair: $\binom{n}{k} \times k = k \binom{n}{k}$

Or: $\binom{n}{1} \times \binom{n-1}{k-1} = n \binom{n-1}{k-1}$

Committee from Groups

From 5 men and 7 women, form committee of 4 with at least 2 women:

• 2 women, 2 men: $\binom{7}{2}\binom{5}{2} = 21 \times 10 = 210$
• 3 women, 1 man: $\binom{7}{3}\binom{5}{1} = 35 \times 5 = 175$
• 4 women, 0 men: $\binom{7}{4}\binom{5}{0} = 35 \times 1 = 35$
• Total: $210 + 175 + 35 = 420$

Lattice Paths

Paths from $(0,0)$ to $(m,n)$ using only right (R) and up (U) moves: $\binom{m+n}{m} = \binom{m+n}{n}$

Choose which $m$ of the $m+n$ steps are rightward.

Example: Paths from $(0,0)$ to $(4,3)$: $\binom{7}{4} = 35$