Combinations: Unordered Selections

You're forming a committee. You need three people from a group of ten.

Alice, Bob, and Carol volunteer. That's your committee.

Bob, Carol, and Alice volunteer. Same committee.

Carol, Alice, and Bob. Still the same committee.

The order you pick them doesn't matter. You're selecting a set, not a sequence. ABC = BAC = CAB. They're all the same combination.

This is what makes combinations different from permutations: order doesn't matter. You're counting sets, not arrangements. And when order doesn't matter, the number of possibilities shrinks—but the structure deepens.

The Definition

A combination is a selection of objects where order is irrelevant.

If you're choosing k objects from n total, the number of combinations is written C(n, k), or "n choose k," sometimes notated as ⎛n⎞ ⎝k⎠

The formula: C(n, k) = n! / (k! × (n - k)!)

Why it works: Start with permutations: P(n, k) = n!/(n-k)! counts ordered selections of k from n.

But in combinations, order doesn't matter. Each set of k objects gets counted k! times in the permutation count (once for each arrangement).

So divide permutations by k!: C(n, k) = P(n, k) / k! = [n!/(n-k)!] / k! = n! / (k! × (n-k)!)

Example: Choosing 3 people from 10 for a committee: C(10, 3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 720 / 6 = 120

There are 120 possible committees, versus 720 possible ordered selections (permutations).

The factor of 6 difference? That's 3! = the number of ways to arrange the same 3 people.

Combinations vs. Permutations: The Core Distinction

Let's make this concrete.

Permutation problem: Choose a president, vice president, and treasurer from 10 people. P(10, 3) = 720. Order matters. Alice-Bob-Carol (Alice as president) ≠ Bob-Alice-Carol (Bob as president).

Combination problem: Choose a 3-person committee from 10 people. C(10, 3) = 120. Order doesn't matter. Alice, Bob, Carol is the same committee regardless of who's listed first.

The relationship: C(n, k) = P(n, k) / k!

Every combination corresponds to k! permutations. That's why combinations count fewer possibilities—they collapse equivalent orderings into a single set.

Why Combinations Matter

Combinations appear everywhere you're selecting subsets without regard to order.

Lotteries

Pick 6 numbers from 49. Order doesn't matter—{3, 12, 23, 31, 42, 47} wins whether you picked them in that order or not.

C(49, 6) = 13,983,816 possible tickets.

That's why lotteries are profitable. The number of combinations is large enough that most tickets lose, but small enough that someone occasionally wins (generating buzz and continued play).

Poker Hands

A 5-card poker hand is a combination—order doesn't matter, only which 5 cards you have.

From a 52-card deck: C(52, 5) = 2,598,960 possible hands.

Royal flush (10, J, Q, K, A of the same suit): exactly 4 hands (one per suit). Probability: 4 / 2,598,960 ≈ 0.00015%. That's 1 in 649,740.

Poker probabilities are combinations. The entire game is navigating a discrete space of 2.6 million possibilities.

Team Selection

You have 15 players and need to field a starting lineup of 5. How many possible lineups? C(15, 5) = 3,003.

If positions mattered (point guard, shooting guard, etc.), it would be P(15, 5) = 360,360. But if you're just choosing the best 5 players regardless of role, it's combinations.

Experimental Design

You're testing 10 drugs and want to try combinations of 3 at a time. C(10, 3) = 120 combinations to test.

This is combinatorial explosion in drug development. Testing all combinations of treatments becomes infeasible as the number of drugs grows. At 20 drugs with 3-drug combos, you're at 1,140 experiments. At 30 drugs, 4,060 experiments. The space scales too fast for exhaustive testing.

Pascal's Triangle: Combinations in Geometry

The binomial coefficients C(n, k) form Pascal's triangle:

           1
         1   1
       1   2   1
     1   3   3   1
   1   4   6   4   1
 1   5  10  10   5   1

Each number is the sum of the two above it. Row n contains C(n, 0), C(n, 1), ..., C(n, n).

Properties:

• Symmetry: C(n, k) = C(n, n-k). Choosing 3 from 10 is the same as choosing which 7 to exclude.
• Recurrence: C(n, k) = C(n-1, k-1) + C(n-1, k). The number of ways to choose k from n equals the ways that include a specific element plus the ways that don't.
• Row sums: The sum of row n is 2ⁿ. C(n, 0) + C(n, 1) + ... + C(n, n) = 2ⁿ. This counts all subsets of an n-element set.

Pascal's triangle isn't just algebra—it's a geometric encoding of combinatorial structure.

The Power Set: All Possible Subsets

How many subsets does a set have?

For a set with n elements, there are 2ⁿ subsets (including the empty set and the full set).

Why? For each element, you make a binary choice: include it or exclude it. By the multiplication principle, n independent binary choices yield 2ⁿ outcomes.

Equivalently: Total subsets = C(n, 0) + C(n, 1) + C(n, 2) + ... + C(n, n) = 2ⁿ.

Example: A set {A, B, C} has 2³ = 8 subsets: {}, {A}, {B}, {C}, {AB}, {AC}, {BC}, {ABC}.

This exponential growth is why exhaustive subset search is intractable. A set of 20 elements has over a million subsets. A set of 30 has over a billion.

Combinations in Probability

Probability questions often reduce to counting combinations.

Example: A class has 12 women and 8 men. You randomly select 5 students. What's the probability that exactly 3 are women?

Total outcomes: C(20, 5) = 15,504 (ways to choose 5 from 20).

Favorable outcomes: Choose 3 women from 12 and 2 men from 8. C(12, 3) × C(8, 2) = 220 × 28 = 6,160.

Probability: 6,160 / 15,504 ≈ 39.7%.

Combinatorics turns probability into counting. You don't need to simulate—just calculate.

Multiset Combinations: Choosing with Repetition

What if you can choose the same object multiple times?

Example: You're buying 5 pieces of fruit. The store has apples, bananas, and cherries. How many different combinations?

This isn't C(3, 5)—you can't choose 5 from 3 when order doesn't matter and repetition isn't allowed. You need combinations with repetition.

The formula: C(n + k - 1, k)

Where n is the number of types and k is the number of selections.

For our fruit problem: C(3 + 5 - 1, 5) = C(7, 5) = 21.

Why does this work? It's a stars-and-bars trick. Represent 5 fruits as stars (*) and 2 dividers (|) to separate 3 types:

• ** | * | ** means 2 apples, 1 banana, 2 cherries
• | *** | ** means 0 apples, 3 bananas, 2 cherries
• ***** | | means 5 apples, 0 bananas, 0 cherries

You have 7 positions (5 stars + 2 bars) and you choose which 5 are stars. That's C(7, 5).

Another example: Distributing 10 identical candies to 4 children. C(4 + 10 - 1, 10) = C(13, 10) = 286 ways.

This appears in integer partition problems, resource allocation, and even quantum statistics (Bose-Einstein statistics for indistinguishable particles).

Vandermonde's Identity: Combining from Two Groups

Suppose you have two groups: 5 red balls and 3 blue balls. You want to choose 4 balls total. How many ways?

You can break this down: choose k red and 4-k blue, for k = 0, 1, 2, 3, 4.

C(5, 0)×C(3, 4) + C(5, 1)×C(3, 3) + C(5, 2)×C(3, 2) + C(5, 3)×C(3, 1) + C(5, 4)×C(3, 0) = 0 + 5 + 30 + 30 + 5 = 70.

But there's another way: just choose 4 from the 8 total balls. C(8, 4) = 70.

They match. This is Vandermonde's identity: C(m + n, k) = Σ C(m, i) × C(n, k - i), summing over all valid i.

This identity connects combinations across different groups. It's used in probability (hypergeometric distribution), algebra (polynomial expansions), and combinatorial proofs.

The Handshake Problem

In a room with n people, everyone shakes hands with everyone else exactly once. How many handshakes?

Each handshake involves 2 people. You're choosing 2 from n: C(n, 2) = n(n-1)/2.

Examples:

• 10 people: C(10, 2) = 45 handshakes
• 20 people: C(20, 2) = 190 handshakes
• 100 people: C(100, 2) = 4,950 handshakes

This structure appears everywhere:

• Network connections: In a fully connected network of n nodes, there are C(n, 2) edges.
• Pairwise comparisons: Testing all pairs from n items requires C(n, 2) tests.
• Tournament scheduling: A round-robin tournament with n teams has C(n, 2) matches.

The handshake problem is combinatorics disguised as social etiquette.

Catalan Numbers (Again)

Remember Catalan numbers from the combinatorics article? They count balanced parentheses, binary trees, and path problems.

The nth Catalan number: C_n = (1/(n+1)) × C(2n, n)

This is a combination formula in disguise. C(2n, n) counts lattice paths from (0,0) to (n,n). Dividing by (n+1) enforces a constraint (paths that don't cross the diagonal).

Catalan numbers show how combinations encode constrained structures. You're not just choosing—you're choosing with rules.

Combinations in Graph Theory

A graph with n vertices can have up to C(n, 2) edges (a complete graph). Each edge connects 2 vertices—a combination.

Example: A complete graph on 5 vertices has C(5, 2) = 10 edges. That's the maximum. Most graphs have fewer (sparse graphs).

Combinations count:

• Subgraphs: Choose k vertices from n, there are C(n, k) possible subgraphs on those vertices.
• Cliques: A clique of size k is a complete subgraph on k vertices. Finding the largest clique is NP-hard because the number of candidate cliques grows combinatorially.

Combinations define the structure of networks.

Combinations and Binomial Coefficients

The binomial coefficient is called that because it appears in the binomial theorem:

(a + b)ⁿ = Σ C(n, k) × aⁿ⁻ᵏ × bᵏ

Each term corresponds to choosing k factors to contribute b (and the rest contribute a).

Example: (a + b)³ = a³ + 3a²b + 3ab² + b³

Coefficients: 1, 3, 3, 1 → C(3, 0), C(3, 1), C(3, 2), C(3, 3).

Combinations aren't just counting—they're algebraic coefficients that encode structure in polynomial expansions.

Stirling Numbers of the Second Kind

Combinations count k-element subsets from n elements. But what if you want to partition n elements into k non-empty subsets (where the subsets aren't ordered)?

This is counted by Stirling numbers of the second kind, S(n, k).

Example: Partition 4 people into 2 non-empty groups. S(4, 2) = 7.

{A,B,C}{D}, {A,B,D}{C}, {A,C,D}{B}, {B,C,D}{A}, {A,B}{C,D}, {A,C}{B,D}, {A,D}{B,C}.

Stirling numbers generalize combinations to partitioning problems. They appear in:

• Bell numbers: Total number of ways to partition n elements (sum of S(n, k) over all k).
• Set partition problems: Clustering, grouping, classification.

Combinations are the tip of the iceberg. Stirling numbers dive deeper into set structure.

Real-World Combination Problems

DNA and Genetics

A genetic test screens for 10 possible mutations. A patient might have any subset. How many possible genetic profiles?

2¹⁰ = 1,024 profiles (including none and all).

If you're testing combinations of 2 mutations at a time: C(10, 2) = 45 tests.

If you're testing combinations of 3 at a time: C(10, 3) = 120 tests.

Combinatorial explosion limits exhaustive genetic testing.

Machine Learning Feature Selection

You have 50 features and want to select the best 5 for your model. C(50, 5) = 2,118,760 possible feature sets.

Brute-force testing all combinations is infeasible. Instead, algorithms use heuristics (greedy selection, regularization) to navigate the space.

Restaurant Menu Combinations

A sandwich shop offers 5 breads, 8 meats, 6 cheeses, and 10 toppings. If you choose one of each category, how many sandwiches? 5 × 8 × 6 × 10 = 2,400 (multiplication principle).

But if you can choose any subset of toppings (from 0 to 10): 5 × 8 × 6 × 2¹⁰ = 24,576,000 possible sandwiches.

Combinatorics explains why "customization" explodes possibility spaces.

Combinations in Cryptography

Modern cryptography uses combinations to define key spaces.

Example: A password must contain 3 uppercase letters, 2 digits, and 1 symbol. How many combinations?

Choose 3 from 26 uppercase: C(26, 3) × (order matters for arrangement). Wait—actually, this is more complex. The positions matter, so it's a mixed problem.

Let's simplify: If you're choosing which 3 positions (out of 6 total) are uppercase: C(6, 3) = 20 ways to position the character types. Then 26³ × 10² × symbol_count for the actual characters.

Combinations define the structural constraints of password policies.

The Birthday Problem

In a room of n people, what's the probability that at least two share a birthday?

This is a classic combination problem.

Total outcomes: 365ⁿ (each person can have any of 365 birthdays).

Favorable outcomes (all different): 365 × 364 × 363 × ... × (365 - n + 1). That's P(365, n).

Probability all different: P(365, n) / 365ⁿ.

Probability at least two match: 1 - P(365, n) / 365ⁿ.

For n = 23, this probability exceeds 50%.

Why so low? Because you're comparing pairs. The number of pairs is C(23, 2) = 253. With 253 pairwise comparisons and 365 possible birthdays, collisions become likely.

The birthday problem is why hash collisions appear faster than intuition suggests.

Combinations and Complexity

The number of combinations grows polynomially (compared to permutations' factorial growth), but it's still explosive.

C(n, k) grows as O(nᵏ) when k is fixed. But when k varies (like k = n/2), it grows exponentially.

C(n, n/2) ≈ 2ⁿ / √n (by Stirling's approximation).

Why this matters:

• Subset search problems (e.g., subset sum, knapsack) are NP-hard because the number of subsets is exponential.
• Combinatorial optimization (choosing the best subset) is often intractable.
• Approximation algorithms navigate combination spaces without exhaustive enumeration.

Combinations scale better than permutations, but they still hit computational limits.

Combinations as Symmetry

In algebra, combinations represent symmetric functions—expressions unchanged by permuting variables.

The elementary symmetric polynomials are sums over combinations:

• e₁ = x₁ + x₂ + ... + xₙ (C(n, 1) terms)
• e₂ = x₁x₂ + x₁x₃ + ... (C(n, 2) terms)
• e₃ = x₁x₂x₃ + ... (C(n, 3) terms)

These appear in:

• Vieta's formulas (relating polynomial roots to coefficients)
• Eigenvalue problems (characteristic polynomials)
• Generating functions (combinatorial structures)

Combinations encode symmetry in mathematics.

Why Order Doesn't Matter (And Why It Does)

We began with committees: order doesn't matter.

But context determines whether order matters. The same scenario can be modeled as combinations or permutations depending on what you care about.

• Committee selection: Combination (just who's on it)
• Committee with roles: Permutation (president, VP, treasurer)
• Poker hand: Combination (which 5 cards)
• Drawing cards one at a time: Permutation (sequence matters for gameplay)
• Choosing toppings: Combination (pepperoni + mushrooms = mushrooms + pepperoni)
• Layering a sandwich: Permutation (bread-cheese-meat ≠ bread-meat-cheese)

The mathematics doesn't change—your model does. Combinations and permutations are lenses for viewing selection problems. Choose the right lens, and the problem clarifies.

Further Reading

• Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 2nd edition, 1994. (Binomial coefficients, identities)
• Stanley, Richard P. Enumerative Combinatorics, Volume 1. Cambridge University Press, 2nd edition, 2011. (Generating functions, Catalan numbers)
• Rosen, Kenneth H. Discrete Mathematics and Its Applications. McGraw-Hill, 8th edition, 2018. (Combinations, Pascal's triangle)
• Wilf, Herbert S. Generatingfunctionology. A K Peters, 3rd edition, 2005. (Combinatorial identities via generating functions)
• Feller, William. An Introduction to Probability Theory and Its Applications. Wiley, 3rd edition, 1968. (Birthday problem, probability via combinations)

This is Part 4 of the Discrete Mathematics series, exploring the foundational math of computer science, algorithms, and computational thinking. Next: "The Binomial Theorem Explained — Pascal's Triangle Unlocked."

Part 4 of the Discrete Mathematics series.

Previous: Permutations: Ordered Arrangements Next: The Binomial Theorem: Expanding Powers