Key Concepts in Combinations

Why This Matters

Combinations form the backbone of counting problems throughout algebraic combinatorics, and you'll encounter them everywhere—from basic probability calculations to advanced generating function techniques. The core question combinations answer is deceptively simple: how many ways can we select items when order doesn't matter? But this single idea branches into powerful tools like Pascal's Triangle, the Binomial Theorem, and partition theory that appear repeatedly on exams.

You're being tested not just on whether you can compute $\binom{n}{k}$, but on whether you understand why certain formulas work and when to apply each technique. The concepts here connect to polynomial expansions, probability distributions, and abstract counting arguments. Don't just memorize formulas—know what problem type each method solves and how the identities relate to one another.

---

Foundational Definitions and Formulas

Before diving into advanced techniques, you need rock-solid command of the basic combination framework. These formulas are the building blocks for everything else in this guide.

Definition of Combinations

• Selection without order—combinations count the number of ways to choose $k$ items from $n$ items where arrangement doesn't matter
• Notation: written as $\binom{n}{k}$, $C(n,k)$, or "$n$ choose $k$"—all three forms appear on exams
• Key distinction from permutations—choosing {A, B, C} counts as one combination but six permutations

Combination Formula (nCr)

• The formula: $\binom{n}{k} = \frac{n!}{k!(n-k)!}$—memorize this cold, as it's the foundation for all combination calculations
• Factorial meaning: $n!$ represents $n \times (n-1) \times (n-2) \times \cdots \times 1$, the product of all positive integers up to n
• Why it works—we divide by $k!$ to eliminate the overcounting from arrangements within our selection

Combinations vs. Permutations

• Order matters vs. doesn't—permutations count arrangements ($P(n,k) = \frac{n!}{(n-k)!}$), combinations count selections
• Relationship: $\binom{n}{k} = \frac{P(n,k)}{k!}$—combinations are always smaller since we're collapsing equivalent arrangements
• Exam strategy—ask yourself "does rearranging change the outcome?" to determine which formula applies

---

Visual and Structural Tools

These techniques give you ways to see combinations and their relationships, making calculations faster and proofs more intuitive.

Pascal's Triangle

• Construction rule—each entry equals the sum of the two entries directly above it: $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$
• Row interpretation—the $n$th row contains all values $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$, giving binomial coefficients at a glance
• Symmetry property—the triangle is symmetric because $\binom{n}{k} = \binom{n}{n-k}$, a fact that simplifies many calculations

Combination Identities

• Symmetry identity: $\binom{n}{k} = \binom{n}{n-k}$—choosing what to include is equivalent to choosing what to exclude
• Hockey Stick Identity: $\sum_{i=0}^{r}\binom{n+i}{i} = \binom{n+r+1}{r}$—trace a diagonal in Pascal's Triangle, then move one step right
• Vandermonde's Identity: $\binom{m+n}{r} = \sum_{k=0}^{r}\binom{m}{k}\binom{n}{r-k}$—essential for convolution-style counting problems

Binomial Theorem

• The expansion: $(a+b)^n = \sum_{k=0}^{n}\binom{n}{k}a^{n-k}b^k$—connects combinations directly to polynomial coefficients
• Coefficient extraction—the coefficient of $a^{n-k}b^k$ is exactly $\binom{n}{k}$, which is why we call them binomial coefficients
• Special cases—setting $a=b=1$ gives $2^n = \sum_{k=0}^{n}\binom{n}{k}$, the total number of subsets of an $n$-element set

---

Extended Counting Techniques

When standard combinations aren't enough, these methods handle more complex selection scenarios involving repetition, distribution, and overlapping sets.

Combinations with Repetition

• The setup—select $k$ items from $n$ types where the same type can be chosen multiple times
• The formula: $\binom{n+k-1}{k}$—think of it as placing $k$ identical balls into $n$ distinct bins
• Multiset interpretation—you're counting multisets of size $k$ drawn from $n$ element types

Stars and Bars Method

• Visual technique—represent $k$ identical objects as stars (★) and $n-1$ dividers as bars (|) to separate into $n$ groups
• Counting argument—arrange $k$ stars and $n-1$ bars in a row; choose positions for bars gives $\binom{n+k-1}{n-1}$
• Application—solves "distribute $k$ identical items into $n$ distinct boxes" problems directly

Inclusion-Exclusion Principle

• The formula: $|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum|A_i| - \sum|A_i \cap A_j| + \sum|A_i \cap A_j \cap A_k| - \cdots$
• Overcounting correction—we add individual sets, subtract pairwise overlaps, add back triple overlaps, and so on
• Exam applications—counting integers with forbidden divisors, derangements, and "at least one" probability problems

---

Generalized Coefficients

These extend the basic combination formula to handle multiple categories and more complex partitioning scenarios.

Multinomial Coefficients

• The formula: $\binom{n}{k_1, k_2, \ldots, k_r} = \frac{n!}{k_1! k_2! \cdots k_r!}$ where $k_1 + k_2 + \cdots + k_r = n$
• Interpretation—counts ways to partition $n$ distinct objects into $r$ labeled groups of specified sizes
• Multinomial Theorem: $(x_1 + x_2 + \cdots + x_r)^n = \sum \binom{n}{k_1, \ldots, k_r}x_1^{k_1} \cdots x_r^{k_r}$

Stirling Numbers of the Second Kind

• Definition: $S(n,k)$ counts partitions of $n$ distinct objects into exactly $k$ non-empty, unlabeled subsets
• Recurrence relation: $S(n,k) = k \cdot S(n-1,k) + S(n-1,k-1)$—either add the new element to an existing group or start a new one
• Connection to Bell numbers—$B_n = \sum_{k=0}^{n}S(n,k)$ counts all partitions regardless of number of parts

---

Generating Functions and Sequences

These advanced tools encode entire sequences of combinatorial numbers, enabling powerful algebraic manipulation.

Generating Functions for Combinations

• Ordinary generating function—encode a sequence $(a_0, a_1, a_2, \ldots)$ as $\sum_{n=0}^{\infty}a_n x^n$
• Key example: $(1+x)^n = \sum_{k=0}^{n}\binom{n}{k}x^k$—the generating function for the $n$th row of Pascal's Triangle
• Problem-solving power—multiply generating functions to combine independent choices; extract coefficients for answers

Catalan Numbers

• The formula: $C_n = \frac{1}{n+1}\binom{2n}{n}$—this elegant expression counts an astonishing variety of structures
• Classic interpretations—valid parenthesizations, binary trees with $n$ nodes, paths that don't cross the diagonal, and dozens more
• Recurrence: $C_n = \sum_{i=0}^{n-1}C_i C_{n-1-i}$—reflects the recursive structure of the objects being counted

Partition Numbers

• Definition: $p(n)$ counts ways to write $n$ as a sum of positive integers, ignoring order
• No closed formula—unlike combinations, partition numbers require generating functions or recurrences: $\prod_{k=1}^{\infty}\frac{1}{1-x^k}$
• Growth behavior—partition numbers grow rapidly; $p(100) = 190,569,292$, illustrating the complexity of this sequence

---

Applications in Probability

Combinations provide the counting foundation for calculating probabilities when outcomes are equally likely and order doesn't matter.

Combination Applications in Probability

• Basic probability formula: $P(\text{event}) = \frac{\text{favorable outcomes}}{\text{total outcomes}} = \frac{\binom{n}{k}_{\text{favorable}}}{\binom{n}{k}_{\text{total}}}$
• Sampling without replacement—choosing $k$ items from $n$ where each selection removes an item uses standard combinations
• Hypergeometric distribution—probability of $k$ successes when sampling without replacement: $P(X=k) = \frac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$

---

Quick Reference Table

---

Self-Check Questions

1. Identification: A problem asks for the number of ways to distribute 10 identical candies among 4 children. Which technique applies—standard combinations, stars and bars, or multinomial coefficients?

2. Compare and contrast: Both $\binom{n}{k}$ and $S(n,k)$ involve selecting or grouping objects. What is the fundamental difference in what they count, and when would you use each?

3. Formula application: Using the Binomial Theorem, what is the sum $\sum_{k=0}^{n}(-1)^k\binom{n}{k}$? Explain why this result makes sense combinatorially.

4. Connection: How does Pascal's Triangle encode the Hockey Stick Identity visually? Describe the pattern you would trace.

5. FRQ-style: A committee of 5 people is chosen from 8 men and 6 women. Set up (but don't compute) the expression for the probability that the committee contains exactly 2 women, and identify which counting principle justifies each part of your expression.