Combinations

Combinatorics is the branch of mathematics devoted to counting, arranging, this post and organizing sets of elements. At the heart of this field lies a fundamental concept used across probability theory, computer science, statistics, and decision-making: combinations.

Whether selecting a committee from a pool of candidates, dealing a hand of cards, or sampling data for a machine learning model, combinations provide the core framework for answering a basic question: In how many ways can we choose a subset of items when the order of selection does not matter?

What is a Combination?

In mathematics, a combination is a selection of items from a set such that the order of the items chosen does not affect the outcome.

To understand combinations, it helps to contrast them directly with permutations. Both concepts deal with selecting subsets from a larger pool, but they differ on one crucial rule: order.

Permutations (Order Matters): If you are setting a passcode for a security vault and the code is 1-2-3, entering 3-2-1 will fail. The arrangement of elements creates distinct outcomes.
Combinations (Order Does Not Matter): If you are making a fruit smoothie with apples, bananas, and strawberries, putting strawberries in first followed by apples and bananas produces the exact same smoothie as blending them in reverse order. The set $\{ \text{Apple}, \text{Banana}, \text{Strawberry} \}$ is identical to $\{ \text{Strawberry}, \text{Banana}, \text{Apple} \}$.

A Common Misnomer: The term “combination lock” used on modern padlocks is actually a mathematical misnomer. Because the numbers must be entered in a specific sequence (e.g., $31\text{-}14\text{-}22$), it is technically a permutation lock.

The Combination Formula

To compute the number of possible combinations when choosing $r$ unique items from a set of $n$ distinct items without repetition, we use the standard combination formula, often pronounced as “$n$ choose $r$“:

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

Breaking Down the Variables:

$n$: The total number of items in the set.
$r$: The number of items to select from the set ($0 \le r \le n$).
$!$ (Factorial): The product of all positive integers less than or equal to that number (e.g., $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$). By convention, $0! = 1$.

Why Does the Formula Work?

The formula can be derived logically from permutations:

First, calculate how many ordered ways we can pick $r$ items from $n$. That gives the permutation count:
$$P(n, r) = \frac{n!}{(n – r)!}$$
Next, acknowledge that for any chosen group of $r$ items, there are $r!$ ways to arrange or sequence them internally.
Since order does not matter in combinations, all $r!$ arrangements represent the exact same subset. Dividing by $r!$ eliminates all duplicate orderings, leaving the combination formula:
$$\binom{n}{r} = \frac{P(n, r)}{r!} = \frac{n!}{r!(n – r)!}$$

Step-by-Step Example Calculations

Example 1: Selecting a Committee

Suppose a company has 10 employees and needs to form a project committee of 3 people. How many distinct committees can be formed?

Here, $n = 10$ and $r = 3$.
Order does not matter because a committee of (Alice, Bob, Charlie) is identical to (Charlie, Alice, Bob).

Using the formula:

$$\binom{10}{3} = \frac{10!}{3!(10 – 3)!} = \frac{10!}{3! \times 7!}$$

Expanding the factorials to simplify:

$$\binom{10}{3} = \frac{10 \times 9 \times 8 \times 7!}{ (3 \times 2 \times 1) \times 7!} = \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{720}{6} = 120$$

There are 120 possible committees.

Example 2: Poker Hands

In a standard deck of 52 cards, a poker hand consists of 5 cards dealt to a player. index How many unique 5-card hands are possible?

Here, $n = 52$ and $r = 5$.

$$\binom{52}{5} = \frac{52!}{5!(52 – 5)!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{5 \times 4 \times 3 \times 2 \times 1} = 2,598,960$$

There are 2,598,960 possible unique poker hands.

Fundamental Properties of Combinations

Combinations possess symmetry and operational properties that make complex calculations easier:

Property	Formula	Description / Intuition
Symmetry	$\binom{n}{r} = \binom{n}{n – r}$	Choosing $r$ items to keep is identical to choosing $n – r$ items to leave behind. For example, $\binom{10}{3} = \binom{10}{7} = 120$.
Boundary Cases	$\binom{n}{0} = 1$ and $\binom{n}{n} = 1$	There is only 1 way to pick nothing, and only 1 way to select everything in the set.
Single Item	$\binom{n}{1} = n$	Picking 1 item out of $n$ yields $n$ possibilities.
Pascal’s Identity	$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$	Forms the algebraic foundation of Pascal’s Triangle.

Pascal’s Triangle and Binomial Expansion

Combinations connect directly to algebra through Pascal’s Triangle and the Binomial Theorem.

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 entry in row $n$ at position $k$ corresponds to the combination value $\binom{n}{k}$.

The Binomial Theorem

When expanding an algebraic expression like $(x + y)^n$, the coefficient of each term $x^{n-k}y^k$ is given by the combination $\binom{n}{k}$:

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

For instance, expanding $(x + y)^4$:

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

$$(x + y)^4 = 1x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + 1y^4$$

Notice that the coefficients $(1, 4, 6, 4, 1)$ match Row 4 of Pascal’s Triangle.

Variations: Combinations with Repetition

Standard combinations assume selection without replacement (each item can be chosen at most once). However, when selection with replacement is allowed and order still does not matter, we use combinations with repetition.

The formula for selecting $r$ items from $n$ types with replacement is:

$$CR(n, r) = \binom{n + r – 1}{r} = \frac{(n + r – 1)!}{r!(n – 1)!}$$

Practical Example: Ice Cream Scoops

Suppose an ice cream shop offers 4 flavors ($n = 4$) and you want to buy a bowl with 3 scoops ($r = 3$). You can pick multiple scoops of the same flavor (e.g., 2 vanilla and 1 chocolate).

Using the combination with repetition formula:

$$\binom{4 + 3 – 1}{3} = \binom{6}{3} = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$$

There are 20 ways to select your 3 scoops.

Real-World Applications of Combinations

Combinations extend beyond theoretical mathematics into everyday fields:

Lotteries and Gaming: State lotteries rely on combinations to establish odds. In a “6/49” lottery where players select 6 numbers from 1 to 49, the total number of tickets is $\binom{49}{6} = 13,983,816$, giving a single ticket a $1 \text{ in } 13,983,816$ chance of winning.
Computer Science & Algorithms: Combinatorial algorithms power optimization problems, network routing, feature selection in machine learning, and brute-force search strategies.
Data Science & Sampling: When selecting random hyperparameter grids or official website generating random cross-validation folds, data scientists rely on combinations to sample representative subsets.
Finance & Portfolio Management: Selecting a set of assets from a broader universe of equities to construct a diversified portfolio involves combinational choice constrained by risk parameters.

Summary Key Takeaways

Definition: A combination counts unordered selections of $r$ elements from an $n$-element set.
Primary Formula:$\binom{n}{r} = \frac{n!}{r!(n-r)!}$
Key Distinction: Order does not matter for combinations, whereas order does matter for permutations.
Core Property:$\binom{n}{r} = \binom{n}{n-r}$ (Symmetry).