Combinations

Why you need a new counting tool (motivation)

In permutations, order matters. If you arrange books on a shelf, “A then B” is different from “B then A.” But many real questions aren’t about order:

• •picking a committee
• •choosing toppings on a pizza
• •selecting which features to include in a release
• •choosing k cards from a deck (ignoring the order you drew them)

In these situations, the selection is what matters, not the sequence.

A classic symptom that you need combinations: you can easily list multiple “different” answers that are actually the same outcome because they contain the same elements.

Definition

A combination is an unordered selection of k distinct elements from a set of n distinct elements.

• •“unordered” means {A, B, C} is the same as {C, B, A}
• •“distinct” means no repetition (each item used at most once)
• •“exactly k” means you choose a subset of size k

We denote the number of such selections by the binomial coefficient:

• •C(n,k) or (n choose k)

Read as: “n choose k.”

Intuition: combinations are k-subsets

If S is a set with |S| = n, then a combination corresponds to picking a k-subset T ⊂ S such that |T| = k.

So the counting question becomes:

How many k-subsets does an n-element set have?

That number is C(n,k).

Boundary cases (sanity checks)

These help you detect mistakes later.

• •C(n,0) = 1 (there’s exactly one way to choose nothing: the empty set ∅)
• •C(n,n) = 1 (choose everything)
• •C(n,1) = n (choose any one element)
• •C(n,k) = 0 if k > n (you can’t choose 5 distinct items from 3 items)

These are not special tricks—they fall naturally out of the definition.

Why this works (the key idea)

You already know permutations: the number of ordered selections of k distinct items from n is

• •nP k = n! / (n−k)!

But for combinations, order is irrelevant. A single team of k people can be arranged internally in k! different orders.

So if you:

1) count ordered selections (permutations)

2) then collapse all sequences that represent the same set

…you should divide by the number of internal reorderings, which is k!.

That’s the whole bridge:

combinations = permutations ÷ (ways to reorder the chosen items)

Derivation (showing the work)

Start with permutations:

nP k = n! / (n−k)!

Each unique k-element set corresponds to exactly k! permutations (all possible orderings of those k items). Therefore:

C(n,k) = (nP k) / k!

Now substitute the formula for nP k:

C(n,k) = (n! / (n−k)!) / k!

Rewrite as a single fraction:

C(n,k) = n! / (k!(n−k)!)

This is the standard closed form.

What the factorials are “doing”

It’s easy to memorize the formula and still misunderstand it. Here’s the meaning:

• •n! counts all orderings of all n items
• •dividing by (n−k)! removes orderings of the items you did not pick
• •dividing by k! removes orderings among the items you did pick (because order doesn’t matter)

Quick comparison table

When not to use this formula

This node is about selection without repetition (each item used at most once). If repetition is allowed (“choose 3 scoops, flavors may repeat”), that’s a different tool (often called combinations with repetition / stars and bars).

Staying disciplined about the assumptions is half of discrete math.

Why properties matter

Even if you can compute C(n,k) with a calculator, properties help you:

• •simplify expressions without huge factorials
• •check if an answer is plausible
• •connect combinations to probability and algebra later

We’ll focus on three high-value properties.

1) Symmetry: C(n,k) = C(n,n−k)

Intuition

Choosing k items to include is equivalent to choosing n−k items to exclude.

Example: “Choose 2 students to be captains” out of 10 is the same as “choose 8 students to not be captains.”

Algebraic proof (showing the work)

Start with the formula:

C(n,k) = n! / (k!(n−k)!)

Swap k with n−k:

C(n,n−k) = n! / ((n−k)! (n−(n−k))!)

Simplify the last factorial:

n−(n−k) = k

So:

C(n,n−k) = n! / ((n−k)! k!)

That equals C(n,k) since multiplication is commutative:

C(n,k) = C(n,n−k)

2) Multiplicative ratio (useful for simplification)

A very practical identity is:

C(n,k) = n(n−1)…(n−k+1) / k!

This comes from expanding n!/(n−k)!:

n!/(n−k)! = n(n−1)(n−2)…(n−k+1)

So:

C(n,k) = [n(n−1)…(n−k+1)] / k!

Why you care: it avoids gigantic factorials and makes cancellation easier.

Example pattern: compute C(100,3) without writing 100!.

3) Pascal’s Identity: C(n,k) = C(n−1,k) + C(n−1,k−1)

Why it’s true (combinatorial reasoning)

Take an n-element set and pick a particular “special” element x.

Count k-subsets in two disjoint cases:

1) subsets that do not include x

• •then you must choose all k elements from the remaining n−1
• •count: C(n−1,k)

2) subsets that do include x

• •you already took x, so choose the remaining k−1 elements from the remaining n−1
• •count: C(n−1,k−1)

Add the cases:

C(n,k) = C(n−1,k) + C(n−1,k−1)

What it gives you

This identity generates Pascal’s Triangle and is the backbone of many proofs in probability and algebra.

Mini-sanity checks using these properties

• •Symmetry implies C(10,2) = C(10,8). If your computations don’t match, something is wrong.
• •Pascal’s identity implies C(5,2) should equal C(4,2)+C(4,1) = 6+4 = 10.

These are quick “unit tests” for your counting.

1) Counting subsets and search spaces

In CS, combinations appear whenever you have to consider subsets:

• •feature selection (choose k features out of n)
• •choosing a set of servers for a shard
• •selecting k test cases out of a suite

The number of possibilities often grows quickly. Knowing that the count is C(n,k) helps you reason about feasibility.

Example: even with moderate n, C(n,k) can be huge, which hints that brute force might be impossible.

2) Probability (preview)

Many probabilities are “favorable combinations ÷ total combinations.”

For instance, in card problems, the order of the hand doesn’t matter, so combinations are the natural denominator.

You’ll later see expressions like:

P(event) = C(favorable, k) / C(total, k)

3) Binomial coefficients and algebra (preview)

The name “binomial coefficient” comes from the Binomial Theorem, where coefficients are combinations:

(x + y)ⁿ = ∑ₖ₌₀ⁿ C(n,k) xᵏ yⁿ⁻ᵏ

You don’t need to master this now, but it explains why C(n,k) is so central: it connects counting to polynomial expansion.

4) Relationship to vectors (light connection)

In linear algebra and ML, you’ll sometimes represent a chosen subset using a 0–1 indicator vector v ∈ {0,1}ⁿ with exactly k ones.

Each such v corresponds to a k-subset, and the number of these vectors is exactly C(n,k).

This is a quiet but powerful bridge: combinations count the number of “k-hot” binary vectors.

A decision checklist

Before you compute anything, ask:

1) Am I selecting items or arranging them?

• •arranging ⇒ permutations
• •selecting ⇒ keep going

2) Does order matter in the final outcome?

• •yes ⇒ permutations
• •no ⇒ combinations

3) Is repetition allowed?

• •no ⇒ this node’s C(n,k)
• •yes ⇒ different tool (combinations with repetition)

Getting these questions right is more important than memorizing the formula.