2.3 Combinations without repetition

Combinations and their characteristics

Definition and Key Properties

A combination is a way of selecting items from a larger set where the order of selection doesn't matter. Unlike permutations, which count every different arrangement as distinct, combinations only care about which items you pick, not the sequence you pick them in.

Each object can be selected at most once (no repetitions), and the number of combinations is always less than or equal to the number of permutations for the same values of $n$ and $r$. This makes sense: once you stop caring about order, many permutations collapse into a single combination.

The standard notation is $C(n, r)$ or $\binom{n}{r}$ (read "n choose r"), where:

• $n$ = total number of objects available
• $r$ = number of objects you're choosing

Examples and Applications

A few concrete examples show how quickly combination counts grow:

• Committee selection: Choosing 3 people from a group of 10 gives $C(10, 3) = 120$ possible committees.
• Poker hands: Choosing 5 cards from a standard 52-card deck gives $C(52, 5) = 2{,}598{,}960$ possible hands.
• Lottery draws: Many lotteries ask you to pick 6 numbers from 49, yielding $C(49, 6) = 13{,}983{,}816$ possible tickets.

Beyond games of chance, combinations show up in biology (counting possible genetic trait combinations), chemistry (analyzing molecular structures), and statistics (choosing samples from populations).

Combinations using binomial coefficients

Calculating Combinations

The binomial coefficient $\binom{n}{r}$ gives the number of ways to choose $r$ objects from $n$ objects. The formula is:

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

Here's how to apply it step by step:

1. Identify $n$ (total items) and $r$ (items chosen).

2. Compute $n!$, $r!$, and $(n - r)!$.

3. Divide $n!$ by the product $r! \cdot (n - r)!$.

Example: How many ways can you choose 3 people from a group of 10?

$C(10, 3) = \frac{10!}{3! \cdot 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120$

Notice that in step 3 you can cancel $7!$ from the numerator and denominator, which is why the numerator simplifies to just $10 \times 9 \times 8$. This shortcut comes from the equivalent product formula:

$C(n, r) = \frac{n \times (n-1) \times \cdots \times (n - r + 1)}{r!}$

This version is much more practical for computation, especially with larger numbers.

One important property is symmetry:

$C(n, r) = C(n, n - r)$

This means choosing which items to include is the same count as choosing which items to leave out. For instance, $C(10, 3) = C(10, 7) = 120$.

Pascal's Triangle and Binomial Coefficients

Pascal's Triangle is a triangular array where each entry equals the sum of the two entries directly above it. Each row corresponds to a value of $n$, and each position within that row corresponds to a value of $r$.

Row 0 through Row 4 look like this:

Row 4, for example, gives $C(4,0) = 1$, $C(4,1) = 4$, $C(4,2) = 6$, $C(4,3) = 4$, $C(4,4) = 1$.

The rule that generates each entry is called Pascal's Identity:

$C(n, r) = C(n-1, r-1) + C(n-1, r)$

This works because when you add a new element to a set, each combination of size $r$ either includes that new element (counted by $C(n-1, r-1)$) or it doesn't (counted by $C(n-1, r)$).

Pascal's Triangle is handy for quickly looking up small binomial coefficients without doing any factorial arithmetic.

Permutations vs Combinations

Key Differences

The core distinction: permutations count arrangements (order matters), while combinations count selections (order doesn't matter).

Because of this, the number of permutations is always greater than or equal to the number of combinations for the same $n$ and $r$. The exact relationship is:

$P(n, r) = C(n, r) \times r!$

This makes intuitive sense. For every single combination of $r$ items, there are $r!$ ways to arrange those items. So permutations "inflate" the combination count by a factor of $r!$.

You can also see this in the formulas side by side:

• Permutations: $P(n, r) = \frac{n!}{(n-r)!}$
• Combinations: $C(n, r) = \frac{n!}{r!(n-r)!}$

The only difference is the extra $r!$ in the denominator of the combination formula, which divides out all the redundant orderings.

Problem-Solving Indicators

Word problems usually signal which formula to use through specific language:

• Permutation clues: "arrange," "order," "sequence," "rank," "first/second/third"
  • Arranging 5 people in a line: $P(5, 5) = 120$
• Combination clues: "select," "choose," "group," "committee," "team"
  • Selecting 3 people from 5 for a committee: $C(5, 3) = 10$

A useful test: ask yourself, "If I rearranged the same items, would it count as a different outcome?" If yes, use permutations. If no, use combinations.

Watch out for tricky wording. "How many PIN combinations are possible?" actually refers to permutations, because the order of digits matters. Don't let everyday use of the word "combination" mislead you.

Applications of combinations

Probability and Statistics

Combinations are central to probability calculations whenever you're counting equally likely outcomes. The binomial probability formula, for instance, uses $C(n, k)$ to count the number of ways to get exactly $k$ successes in $n$ independent trials:

$P(X = k) = C(n, k) \cdot p^k \cdot (1-p)^{n-k}$

They also appear in:

• Sampling: Calculating how many distinct samples of size $r$ can be drawn from a population of size $n$
• Poker and lottery odds: Finding the probability of specific hands or number draws
• Binomial theorem: The coefficients in the expansion of $(a + b)^n$ are exactly the binomial coefficients $C(n, 0), C(n, 1), \ldots, C(n, n)$

Other Fields and Applications

• Computer Science: Generating all subsets of a set, analyzing algorithm complexity, and designing cryptographic systems all rely on combination counting.
• Genetics: Calculating the probability of inheriting specific allele combinations, studying genetic diversity in populations, and modeling mutation possibilities.
• Chemistry: Determining possible molecular structures and analyzing potential reaction pathways between sets of reagents.
• Economics and Finance: Selecting portfolios from a set of available assets, and modeling strategic choices in game theory.