7.2 Combinations

Definition of combinations

A combination is a way of selecting items from a larger set where the order of selection doesn't matter. If you pick players A, B, and C for a team, that's the same combination as picking C, A, and B. This is the core distinction that separates combinations from permutations.

Combinations vs permutations

The difference comes down to one question: does order matter?

• Combinations count the number of ways to choose r items from n items, ignoring order. Picking {A, B, C} is the same as picking {C, B, A}.
• Permutations count the number of ways to arrange r items from n items, where order matters. Picking A-B-C is different from C-B-A.

For example, choosing 3 people for a committee is a combination (the group is the same regardless of selection order). Choosing a president, vice president, and treasurer from 3 people is a permutation (each arrangement gives different roles).

Notation for combinations

Combinations are written as $\binom{n}{r}$ or $C(n,r)$, where:

• $n$ is the total number of items to choose from
• $r$ is the number of items being chosen

You read this as "n choose r." So $\binom{10}{3}$ means "10 choose 3," or the number of ways to select 3 items from a set of 10.

Fundamental counting principle

Before diving into the combination formula, you need the fundamental counting principle. It gives you a way to break complex counting problems into simpler pieces.

Multiplication rule

When you're making a sequence of independent choices, multiply the number of options at each step. If you're picking an outfit from 4 shirts, 3 pants, and 2 pairs of shoes, the total number of outfits is $4 \times 3 \times 2 = 24$.

This works whenever one choice doesn't affect the options available for the next choice.

Addition rule

When you're counting outcomes from mutually exclusive categories (situations that can't overlap), add them together. If a café offers 5 types of muffins or 3 types of scones, and you're picking one item, you have $5 + 3 = 8$ options.

The addition rule applies when you're choosing between alternatives, while the multiplication rule applies when you're combining choices in sequence.

Combination formula

Factorial notation

The combination formula relies on factorials. The factorial of a positive integer $n$, written $n!$, is the product of all positive integers from 1 to $n$:

$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1$

So $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$. One special case to memorize: $0! = 1$ by definition.

Derivation of formula

The combination formula is:

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

Here's where it comes from. The number of permutations of r items chosen from n is $\frac{n!}{(n-r)!}$. But since combinations don't care about order, every group of r items has been counted $r!$ times (once for each possible arrangement). Dividing by $r!$ removes that overcounting:

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

Worked example: How many ways can you choose 3 books from a shelf of 8?

1. Identify $n = 8$ and $r = 3$
2. Plug into the formula: $\binom{8}{3} = \frac{8!}{3!(8-3)!} = \frac{8!}{3! \cdot 5!}$
3. Simplify by canceling $5!$ from numerator and denominator: $\frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56$

There are 56 ways to choose 3 books from 8.

Properties of combinations

Symmetry property

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

Choosing r items to include is the same as choosing $n - r$ items to leave out. So $\binom{10}{3} = \binom{10}{7}$. This is useful for simplifying calculations: if $r$ is large, compute with $n - r$ instead.

Pascal's triangle

Pascal's triangle is a triangular array where each entry is a binomial coefficient. The rows are indexed starting from 0:

• Row 0: 1
• Row 1: 1, 1
• Row 2: 1, 2, 1
• Row 3: 1, 3, 3, 1
• Row 4: 1, 4, 6, 4, 1

Each number is the sum of the two numbers directly above it. This reflects the identity:

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

Pascal's triangle gives you a quick way to look up small combination values and to find coefficients for binomial expansions.

Combinations with repetition

Formula for repetition

Standard combinations assume each item can only be chosen once. But sometimes you can select the same item more than once. The formula for combinations with repetition is:

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

Here $n$ is the number of types of items available, and $r$ is the number of selections you're making.

This formula comes from the stars and bars technique: you're distributing $r$ identical selections among $n$ categories, which is equivalent to arranging $r$ stars and $n - 1$ dividing bars.

Example: You're at an ice cream shop with 4 flavors and want 3 scoops (repeats allowed). The number of possible selections is $\binom{4+3-1}{3} = \binom{6}{3} = 20$.

Applications in real life

• Inventory management: Selecting quantities of products from available types
• Resource allocation: Distributing a budget across investment categories
• Genetics: Counting possible allele combinations when the same allele can appear multiple times

Binomial theorem

Expansion of binomial expressions

The binomial theorem connects combinations directly to algebra. It states:

$(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k} y^k$

Each term in the expansion has a coefficient given by $\binom{n}{k}$. For example:

$(x + y)^3 = \binom{3}{0}x^3 + \binom{3}{1}x^2y + \binom{3}{2}xy^2 + \binom{3}{3}y^3 = x^3 + 3x^2y + 3xy^2 + y^3$

Notice the coefficients (1, 3, 3, 1) match row 3 of Pascal's triangle.

Binomial coefficients

The coefficients $\binom{n}{k}$ in the binomial expansion are called binomial coefficients. They're the same values you compute with the combination formula, and they're the entries in Pascal's triangle. This is why combinations show up in so many areas of math: they sit at the intersection of counting, algebra, and probability.

Probability and combinations

Probability of events

When every outcome in a sample space is equally likely, probability reduces to counting:

$P(A) = \frac{\text{number of favorable outcomes}}{\text{total number of possible outcomes}}$

Combinations let you compute both the numerator and denominator.

Example: What's the probability of being dealt exactly 2 hearts in a 5-card poker hand?

1. Total possible hands: $\binom{52}{5} = 2{,}598{,}960$
2. Ways to choose 2 hearts from 13: $\binom{13}{2} = 78$
3. Ways to choose 3 non-hearts from 39: $\binom{39}{3} = 9{,}139$
4. Favorable outcomes: $78 \times 9{,}139 = 712{,}842$
5. Probability: $\frac{712{,}842}{2{,}598{,}960} \approx 0.274$

Conditional probability

Conditional probability measures the likelihood of event A given that event B has already occurred:

$P(A|B) = \frac{P(A \cap B)}{P(B)}$

Combinations help you calculate the reduced sample space after a condition is imposed. For instance, if you know the first card drawn from a deck was a heart, the remaining sample space shrinks, and you'd use combinations on the reduced deck to find probabilities for subsequent draws.

Problem-solving strategies

Identifying combination problems

Look for these clues in a problem:

• Words like "select," "choose," "group," or "committee"
• The problem asks how many groups rather than how many arrangements
• Order clearly doesn't matter (a team of 3 is the same regardless of selection order)

Then determine:

• What is $n$ (the total pool)?
• What is $r$ (how many you're choosing)?
• Is repetition allowed?
• Does the problem involve multiple steps (requiring the multiplication or addition rule)?

Step-by-step approach

1. Read carefully and identify whether order matters (combination vs. permutation)
2. Define your values: identify $n$ and $r$
3. Break compound problems into parts. If you're choosing a committee of 3 men from 10 and 2 women from 8, compute each combination separately, then multiply
4. Apply the formula: $\binom{n}{r} = \frac{n!}{r!(n-r)!}$
5. Simplify by canceling factorials before multiplying (this avoids huge numbers)
6. Check your answer: Does it seem reasonable? A combination should always be smaller than or equal to the corresponding permutation

Applications of combinations

Lottery and gambling

• Lottery odds: A 6/49 lottery requires choosing 6 numbers from 49. The number of possible tickets is $\binom{49}{6} = 13{,}983{,}816$, so your odds of winning with one ticket are about 1 in 14 million.
• Poker hands: The number of possible 5-card hands is $\binom{52}{5} = 2{,}598{,}960$. Probabilities of specific hands (flush, full house, etc.) all rely on combination calculations.

Genetics and biology

• Calculating probabilities of inheriting specific gene combinations from parents
• Modeling how alleles combine across generations using combinatorial methods
• Designing experiments that test multiple genetic variables simultaneously

Computer science algorithms

• Combinatorial optimization: Finding the best subset from a large set (e.g., the traveling salesman problem)
• Cryptography: Key generation often depends on the difficulty of combinatorial problems
• Algorithm analysis: Counting the number of possible inputs or states to determine complexity

Advanced combination concepts

Stirling numbers

Stirling numbers come in two types and handle more complex partitioning problems:

• Stirling numbers of the first kind $s(n,k)$: count the number of permutations of $n$ elements with exactly $k$ disjoint cycles
• Stirling numbers of the second kind $S(n,k)$: count the number of ways to partition $n$ elements into exactly $k$ non-empty subsets

These show up in advanced counting problems and in the theory of generating functions.

Catalan numbers

The $n$th Catalan number is defined as:

$C_n = \frac{1}{n+1}\binom{2n}{n}$

The first several values are 1, 1, 2, 5, 14, 42, 132, ...

Catalan numbers count a surprising variety of structures: the number of ways to correctly match $n$ pairs of parentheses, the number of ways to triangulate a polygon with $n+2$ sides, and the number of distinct binary trees with $n$ nodes. They appear frequently in computer science, particularly in problems involving recursive structures.