Math Core

A combination is a selection where order doesn't matter: a committee, a hand of cards, a set of pizza toppings. Combinations count handshakes, diagonals, triangles, grid paths and ways to share identical objects. They are the most-used formula on the counting problems of the AMC 8.

From permutations to combinations

How many ways can you choose $3$ toppings from $8$ ? If order mattered, there would be $8 \cdot 7 \cdot 6 = 336$ ordered choices. But each set of $3$ toppings (say mushroom, onion, pepper) appears $3! = 6$ times in that list, once for each order. So there are $336 \div 6 = 56$ sets.

Combinations

The number of ways to choose $k$ objects from $n$ different objects, when order doesn't matter, is

$\binom{n}{k} = \frac{n \cdot (n-1) \cdots (n-k+1)}{k!} = \frac{n!}{k!\,(n-k)!}.$

Read $\binom{n}{k}$ as " $n$ choose $k$ ."

Two facts save time:

Symmetry: $\dbinom{n}{k} = \dbinom{n}{n-k}$ . Choosing $3$ people to go is the same as choosing $n - 3$ to stay. So $\binom{10}{8} = \binom{10}{2} = 45$ .
Pairs: $\dbinom{n}{2} = \dfrac{n(n-1)}{2}$ . This counts handshakes, games in a round robin, and segments between $n$ points.

Ask: does order matter?

Choosing a president, vice president and treasurer is a permutation (the jobs are different). Choosing a $3$ -person committee is a combination (the members are equal). If swapping two chosen items gives a different result, use permutations; if it gives the same result, use combinations.

Worked example: A committee with two groups

A club has $6$ boys and $5$ girls. How many $5$ -person committees have exactly $3$ boys and $2$ girls?

Choose the boys and the girls separately, then multiply: $\dbinom{6}{3} \cdot \dbinom{5}{2} = 20 \cdot 10 = 200$ .

Grid paths

To walk from the bottom-left corner to the top-right corner of a $4 \times 3$ grid, moving only right or up, you make $4$ right moves and $3$ up moves, $7$ moves in all.

A 4 by 3 grid. Every shortest path from the bottom-left corner to the top-right corner uses 4 right moves and 3 up moves.

A path is decided by which $3$ of the $7$ moves are "up." So there are $\dbinom{7}{3} = 35$ paths.

Worked example: Paths through a point

On the grid above, how many shortest paths pass through the point $(2, 1)$ ?

Split the walk at $(2, 1)$ . From $(0, 0)$ to $(2, 1)$ : $2$ rights and $1$ up, $\binom{3}{1} = 3$ paths. From $(2, 1)$ to $(4, 3)$ : $2$ rights and $2$ ups, $\binom{4}{2} = 6$ paths. Total: $3 \cdot 6 = 18$ .

Sharing identical objects (stars and bars)

Worked example: Stars and bars

In how many ways can $10$ identical candies be given to $3$ children (a child may get none)?

Line up the $10$ candies as stars and insert $2$ bars to split them into $3$ groups: $\star\star\star \mid \star\star\star\star\star \mid \star\star$ means $3$ , $5$ , $2$ . Every arrangement of $10$ stars and $2$ bars gives one sharing, and every sharing gives one arrangement. So count the ways to choose the $2$ bar positions among $12$ spots: $\dbinom{12}{2} = 66$ .

If each child must get at least one, first hand one candy to each child, then share the remaining $7$ freely: $\dbinom{9}{2} = 36$ .

Common mistake

Stars and bars only works when the objects are identical. Giving $10$ different prizes to $3$ children is a multiplication problem: $3^{10}$ , since each prize independently picks a child.

Practice

Practice 1

Seven people are at a party, and each person shakes hands with every other person exactly once. How many handshakes take place?