Combinations

In combinatorics, combinations are a way of counting selections where order does not matter. This chapter focuses on how to recognize when combinations are appropriate, how to compute them, and how they relate to other counting ideas.

What a Combination Counts

A combination counts how many different subsets of a given size can be chosen from a larger set, when:

• each item can be chosen at most once,
• the order of the chosen items does not matter.

Typical phrase cues that suggest combinations:

• “choose 3 students from 10”
• “select a committee of 4”
• “how many different 5-card hands”
• “pick 2 toppings for a pizza” (if the set cheese + pepperoni is the same as pepperoni + cheese)

By contrast, if the order does matter (“arrange 3 students in a line,” “how many 3-digit codes”), then you are dealing with permutations, not combinations.

Notation for Combinations

The standard notation for “the number of ways to choose $k$ elements from $n$ distinct elements” is:

• $C(n,k)$ or $^nC_k$
• $\binom{n}{k}$ (read “$n$ choose $k$”)

All of these mean the same quantity. In this chapter we’ll mostly use the binomial coefficient notation $\binom{n}{k}$.

So, $\binom{n}{k}$ is defined as:

• the number of $k$-element subsets you can form from an $n$-element set.

Examples of reading the notation:

• $\binom{5}{2}$: “5 choose 2” = number of ways to choose 2 items from 5.
• $\binom{10}{4}$: “10 choose 4” = number of 4-person committees from 10 people.

Formula for Combinations

To derive the formula, start from permutations (order matters) and adjust.

• The number of ordered selections (permutations) of $k$ distinct elements from $n$ is:
  $$P(n,k) = \frac{n!}{(n-k)!}.$$

But for combinations, we don’t want to distinguish between different orders of the same chosen elements. For a fixed set of $k$ chosen elements, there are $k!$ different orders of those $k$ elements. Thus each combination corresponds to $k!$ permutations.

So:
$$
\binom{n}{k} = \frac{\text{number of permutations}}{\text{number of orders per set}}
= \frac{\dfrac{n!}{(n-k)!}}{k!}
= \frac{n!}{k!(n-k)!}.
$$

This is the standard formula for combinations.

Basic values

Some values follow directly from the formula:

• $\displaystyle \binom{n}{0} = 1$ (there is exactly one way to choose nothing).
• $\displaystyle \binom{n}{1} = n$ (choose 1 element from $n$).
• $\displaystyle \binom{n}{n} = 1$ (choose all elements).
• $\displaystyle \binom{n}{k} = 0$ if $k>n$ (cannot choose more elements than exist).

Example calculations:

• $\displaystyle \binom{5}{2} = \frac{5!}{2!3!} = \frac{120}{2\cdot 6} = 10$.
• $\displaystyle \binom{10}{3} = \frac{10!}{3!7!} = \frac{10\cdot 9\cdot 8}{3\cdot 2\cdot 1} = 120$.

In practice, you nearly always cancel factorials before multiplying everything out.

Identifying Combinations in Word Problems

The key question: “Does order matter in what I’m counting?”

Use combinations if:

• you are forming groups, subsets, committees, hands, selections,
• and you do not care about arrangement within the group.

Use permutations if:

• you are forming arrangements, rankings, line-ups, ordered lists,
• and different orders count as different outcomes.

Example:

• “How many 3-person committees can be formed from 8 people?”

A committee is an unordered group: use combinations:
$$
\binom{8}{3} = \frac{8!}{3!5!} = 56.
$$

• “In how many ways can 3 of 8 people stand in a line?”

A line has order: use permutations (covered in the permutations chapter), not combinations.

Symmetry Property: $\binom{n}{k} = \binom{n}{n-k}$

Combinations satisfy a simple but important symmetry:

$$
\binom{n}{k} = \binom{n}{n-k}.
$$

Algebraically, this is immediate from the formula:
$$
\binom{n}{k} = \frac{n!}{k!(n-k)!},\qquad
\binom{n}{n-k} = \frac{n!}{(n-k)!k!},
$$
which are identical.

Combinatorially (by reasoning about sets): choosing $k$ elements to include is the same as choosing the $n-k$ elements to leave out. These two perspectives count the same thing.

Example:

• $\displaystyle \binom{10}{3} = \binom{10}{7} = 120$.

Choosing 3 people to be on the committee is equivalent to choosing 7 people who are not on the committee.

This symmetry is often useful for simplifying calculations: if $k$ is large, use $n-k$ instead.

Pascal’s Identity

Another key property of combinations is the recurrence known as Pascal’s identity:

$$
\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1},
$$
valid when $1 \le k \le n-1$.

Combinatorial reasoning: Suppose you have $n$ distinct elements, and you fix one special element, call it $x$.

To count all $k$-element subsets, divide them into two types:

• subsets that do not contain $x$: there are $\binom{n-1}{k}$ of these (choose all $k$ from the remaining $n-1$ elements);
• subsets that do contain $x$: there are $\binom{n-1}{k-1}$ of these (you must include $x$, and choose the remaining $k-1$ elements from the other $n-1$).

So the total is the sum.

Pascal’s identity underlies Pascal’s triangle, where each entry is the sum of the two above it.

Pascal’s Triangle and Binomial Coefficients

Pascal’s triangle is a triangular arrangement of numbers where each interior number is the sum of the two numbers directly above it:

Row 0: $1$
Row 1: $1\quad 1$
Row 2: $1\quad 2\quad 1$
Row 3: $1\quad 3\quad 3\quad 1$
Row 4: $1\quad 4\quad 6\quad 4\quad 1$
Row 5: $1\quad 5\quad 10\quad 10\quad 5\quad 1$

The $n$‑th row (starting with row 0) consists of:
$$
\binom{n}{0},\ \binom{n}{1},\ \ldots,\ \binom{n}{n}.
$$

Pascal’s triangle:

• encodes the values of $\binom{n}{k}$,
• visually demonstrates Pascal’s identity: each entry is the sum of the two above it,
• provides a quick way to compute small binomial coefficients without factorials.

For example, from row 5 we see immediately that:

• $\binom{5}{0} = 1$,
• $\binom{5}{1} = 5$,
• $\binom{5}{2} = 10$,
• $\binom{5}{3} = 10$,
• $\binom{5}{4} = 5$,
• $\binom{5}{5} = 1$.

Combinations and the Binomial Theorem (Overview)

Combinations appear naturally in the expansion of powers of a sum. The binomial theorem states that:

$$
(a+b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k.
$$

Here:

• the coefficient of $a^{n-k} b^k$ is exactly $\binom{n}{k}$,
• so binomial coefficients are the “weights” in a binomial expansion.

The detailed study of the binomial theorem and its proof belongs in another chapter, but it is useful here to know that $\binom{n}{k}$ shows up in algebra as well as in counting problems.

Example (just to see the pattern):

• $(a+b)^3 = \binom{3}{0}a^3b^0 + \binom{3}{1}a^2b^1 + \binom{3}{2}a^1b^2 + \binom{3}{3}a^0b^3
  = a^3 + 3a^2b + 3ab^2 + b^3.$

The coefficients $1,3,3,1$ are the entries in row 3 of Pascal’s triangle.

Typical Combination Problems

Here are a few standard question types that specifically use combinations.

Forming committees and groups

Example: A club has 12 members. How many different 5-person committees can be formed?

Order does not matter; committees are just sets of people:

$$
\binom{12}{5} = \frac{12!}{5!7!} = \frac{12\cdot 11\cdot 10\cdot 9\cdot 8}{5\cdot 4\cdot 3\cdot 2\cdot 1} = 792.
$$

Choosing cards or items

Example: How many different 3-card hands can you draw from a 52-card deck?

Again, order does not matter in a hand:

$$
\binom{52}{3} = \frac{52!}{3!49!} = \frac{52\cdot 51\cdot 50}{3\cdot 2\cdot 1} = 22{,}100.
$$

Using symmetry to simplify

Example: How many ways to choose 8 students from a class of 30?

Directly:
$$
\binom{30}{8} = \frac{30!}{8!22!},
$$
but that involves large numbers. Use symmetry:

$$
\binom{30}{8} = \binom{30}{22},
$$
so you can compute or approximate using the smaller of $8$ and $22$; in practice, any calculation will already cancel down to a product of 8 terms over $8!$.

Multiple-step selections

Sometimes problems involve more than one independent combination selection.

Example: A team of 9 people must be split into a 3-person leadership group and a 2-person review group, with no overlap between the two groups. How many ways is this possible?

One way (using combinations step by step):

• Choose 3 leaders from 9: $\binom{9}{3}$ ways.
• From the remaining 6 people, choose 2 reviewers: $\binom{6}{2}$ ways.
• Total: $\binom{9}{3}\binom{6}{2}$.

Since groups are unlabeled within their type and order inside a group does not matter, combinations are appropriate for each step.

Note that this is not the same as just $\binom{9}{5}$, because that would count choosing a single 5-person group, not two distinct roles.

Common Pitfalls

When working with combinations, watch for these frequent mistakes:

1. Using permutations where combinations are needed.
   If the situation does not care about order (committees, subsets, hands), do not use permutation formulas.
2. Using formulas with $k>n$.
   If you see something like $\binom{5}{6}$ in your calculation, it should be
$, but more often it signals that you’ve misinterpreted the problem.
3. Forgetting the factorial in the denominator.
   The full formula is $\dfrac{n!}{k!(n-k)!}$; leaving out $k!$ or $(n-k)!$ changes the meaning.
4. Counting the same selection multiple times.
   When you multiply combinations (for multi-step selections), be careful that the steps are genuinely distinct and you’re not double-counting the same outcome via different paths.

Summary

• A combination counts selections where each element is chosen at most once and order does not matter.
• The number of $k$-element subsets of an $n$-element set is:
  $$
  \binom{n}{k} = \frac{n!}{k!(n-k)!}.
  $$
• Important properties:
• Symmetry: $\binom{n}{k} = \binom{n}{n-k}$.
• Pascal’s identity: $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$.
• Combinations appear in:
• group/committee/hand counting,
• Pascal’s triangle,
• coefficients in the binomial expansion $(a+b)^n$.

Recognizing when combinations apply, and being able to compute and manipulate $\binom{n}{k}$, is one of the core skills in combinatorics.