Combinations

Combinations represent the selection of $r$ items from a total set of $n$ distinct objects where the sequence or arrangement does not change the result. In this context, a set containing {A, B} is considered identical to a set containing {B, A} because the membership is the same.

The term 'n choose r' is commonly used to describe this operation, denoted mathematically as $\binom{n}{r}$ or $nC_r$. This value represents the number of unique subsets of size $r$ that can be formed from $n$ elements.

This concept is essential in probability and statistics for calculating the size of a sample space when the order of events or selections is not a factor in the outcome.

The mathematical foundation of combinations is built upon removing the redundancy found in permutations. Since there are $r!$ ways to arrange $r$ items, we divide the total number of permutations by $r!$ to collapse all identical sets into one.

This logic leads to the relationship $nC_r = \frac{nP_r}{r!}$. By dividing by the factorial of the subset size, we effectively 'un-order' the selection, ensuring that each unique group is counted only once.

The use of factorials ($n!$) accounts for the total possible arrangements of the entire set, while the $(n-r)!$ term in the denominator removes the arrangements of the items not selected, leaving only the arrangements of the chosen subset.

To calculate the number of combinations, use the standard formula: $nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}$ where $n$ is the total number of items and $r$ is the number of items being chosen.

Step 1: Identify Parameters: Determine the total population ($n$) and the size of the selection ($r$). Ensure that the items are distinct and the order of selection truly does not matter.

Step 2: Simplify the Factorial: Before calculating large factorials, simplify the expression by canceling out $(n-r)!$ from the numerator. For example, $\binom{10}{3} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1}$.

Step 3: Apply Symmetry: If $r$ is more than half of $n$, use the property $\binom{n}{r} = \binom{n}{n-r}$ to make the calculation easier. Choosing 98 items out of 100 is the same as choosing the 2 items to leave behind.

Keyword Recognition: Look for words like 'select', 'choose', or 'subset' which typically signal combinations. Conversely, words like 'arrangement', 'letters in a word', or 'digits in a code' usually imply permutations.

The 'And' vs 'Or' Rule: When a problem requires selecting from multiple groups (e.g., choosing men AND women), calculate the combinations for each group separately and multiply them. If the problem allows for one group OR another, add the results.

Sanity Check: Always remember that $\binom{n}{0} = 1$ and $\binom{n}{n} = 1$. There is only one way to choose nothing, and only one way to choose everything from a set.

Symmetry Property: Use $\binom{n}{r} = \binom{n}{n-r}$ to save time. If an exam asks for $\binom{20}{18}$, calculate $\binom{20}{2}$ instead, as it involves much smaller numbers and less risk of calculation error.