Combinatorics: Counting Without Counting

How many ways can you arrange a deck of 52 cards?

If you started listing them—ace of spades first, then ace of hearts, then ace of diamonds, trying every possible order—you'd die before making a dent. So would your children. And their children. And every human who has ever lived, combined, working full-time since the Big Bang.

The number is 52 factorial. Written as 52!, it equals:

80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000

That's roughly 8 × 10⁶⁷. For scale: there are about 10⁸⁰ atoms in the observable universe.

You'll never enumerate all the arrangements of a single deck of cards. But you can count them. And that's what combinatorics does: it counts without counting.

The Central Insight

Combinatorics is the mathematics of counting, arrangement, and selection.

Not counting like "one, two, three." Counting like: How many possible configurations exist? How many ways can things be arranged, selected, combined, or partitioned?

The power comes from finding patterns and formulas that give you the answer without exhaustively listing every possibility. Instead of writing out every arrangement of 52 cards, you recognize a structure: 52 choices for the first position, 51 for the second, 50 for the third, down to 1 for the last. Multiply them: 52 × 51 × 50 × ... × 1 = 52!.

You didn't count the arrangements. You counted how to count them.

This leap—from enumeration to structural reasoning—is what makes combinatorics powerful. It turns brute-force impossibility into elegant certainty.

Why Counting Gets Hard

Counting small things is trivial. Three apples on a table: you count them.

But combinatorics deals with counting configurations: arrangements, selections, groupings, pathways through possibility spaces. And these grow explosively.

Consider passwords. An 8-character password using lowercase letters has 26⁸ = 208,827,064,576 possibilities. Add uppercase and it's 52⁸ = 53,459,728,531,456. Add digits and symbols and you're in the trillions.

Security depends on this growth. A 6-character password might have millions of possibilities—sounds large, but a modern computer can try them all in seconds. A 12-character password with full character variety has so many possibilities that brute-force becomes computationally infeasible.

The difference isn't just "more"—it's a phase transition from tractable to impossible.

Combinatorics lets you calculate these numbers precisely, which means you can reason about security, probability, algorithm complexity, and decision spaces without running the experiment.

The Fundamental Counting Principles

Combinatorics rests on two foundational rules that turn intuitive reasoning into mathematical certainty.

The Multiplication Principle (AND)

If you perform one task in m ways and another task in n ways, and the tasks are independent, then you can perform both tasks in m × n ways.

Example: You're getting dressed. You have 5 shirts and 3 pairs of pants. How many outfits? 5 × 3 = 15.

Each shirt can pair with each pair of pants. The choices multiply.

This extends to any number of independent choices:

• License plates with 3 letters and 4 digits: 26³ × 10⁴ = 175,760,000 possibilities
• Binary strings of length 8: 2⁸ = 256 possibilities (each position is 0 or 1)
• Arrangements of 5 books on a shelf: 5! = 120 (5 choices for first position, 4 for second, etc.)

The multiplication principle is why possibilities explode. Each new independent choice multiplies the total.

The Addition Principle (OR)

If you can perform a task in m ways or in n ways (but not both simultaneously), then there are m + n ways total.

Example: You can travel from City A to City B by 3 train routes or 2 flights. How many travel options? 3 + 2 = 5.

You take a train or a flight, not both. The choices add.

Why this matters: These two principles compose. Complex counting problems decompose into sequences of multiplications (independent choices) and additions (mutually exclusive alternatives).

Factorials: The Arrangement Explosion

The factorial function—written n!—counts the number of ways to arrange n distinct objects in a row.

Definition: n! = n × (n-1) × (n-2) × ... × 2 × 1

Why? You have n choices for the first position, then n-1 remaining choices for the second, n-2 for the third, and so on. By the multiplication principle, the total is the product of all these choices.

Examples:

• 3! = 3 × 2 × 1 = 6 (six ways to arrange A, B, C: ABC, ACB, BAC, BCA, CAB, CBA)
• 5! = 120 (ways to arrange 5 people in line)
• 10! = 3,628,800 (ways to arrange 10 books)
• 52! ≈ 8 × 10⁶⁷ (ways to shuffle a deck)

Factorials grow fast. This is called super-exponential growth. Even 20! is already 2.4 quintillion. By 70!, you've exceeded the number of atoms in the universe.

This explosive growth is why brute-force enumeration fails. You cannot try all arrangements. You must reason about structure.

Permutations: When Order Matters

A permutation is an arrangement where order matters.

If you're picking 3 people from a group of 10 to be president, vice president, and treasurer, the order matters. Alice-Bob-Carol is different from Carol-Bob-Alice.

The formula for permutations of k objects from n total:

P(n, k) = n! / (n - k)!

Or equivalently: n × (n-1) × (n-2) × ... × (n-k+1).

Why it works:

• n choices for the first position
• n-1 choices for the second
• n-2 choices for the third
• Continue for k positions
• Multiply them all

Example: How many ways to award gold, silver, bronze medals to 3 people out of 8 runners? P(8, 3) = 8 × 7 × 6 = 336.

The division by (n-k)! in the formula cancels out the unwanted positions. When k = n (arranging all n objects), P(n,n) = n!.

Combinations: When Order Doesn't Matter

A combination is a selection where order doesn't matter.

If you're choosing 3 people from 10 to form a committee, Alice-Bob-Carol is the same committee as Carol-Bob-Alice. You're selecting, not arranging.

The formula for combinations of k objects from n total:

C(n, k) = n! / (k! × (n - k)!)

Also written as "n choose k" or ⎛n⎞ ⎝k⎠

Why it works: Start with permutations: P(n, k) counts ordered selections. But combinations don't care about order. Each combination of k objects gets counted k! times in the permutation count (once for each arrangement of those k objects). So divide by k! to remove the overcounting.

Example: How many ways to choose 3 committee members from 10 people? C(10, 3) = 10! / (3! × 7!) = (10 × 9 × 8) / (3 × 2 × 1) = 120.

Compare to permutations: P(10, 3) = 336. The difference is that 336 counts all ordered triples, while 120 counts only the distinct sets.

The Binomial Coefficient

The combination formula C(n, k) is also called the binomial coefficient because it appears in the binomial theorem (which we'll explore in another article). These numbers 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. The nth row contains the coefficients of (a + b)ⁿ when expanded.

But binomial coefficients aren't just algebraic curiosities. They count real combinatorial objects:

• C(n, k) = ways to choose k items from n
• C(n, k) = number of k-element subsets of an n-element set
• C(n, k) = paths through a grid (right k times, up n-k times)

Example: How many ways to walk from (0,0) to (3,2) on a grid if you can only move right or up?

You need 3 rights and 2 ups—5 moves total. The question is: which 3 of those 5 moves are "right"? C(5, 3) = 10 paths.

Same structure, different interpretation. Combinatorics reveals these hidden equivalences.

Combinations with Repetition

What if you can choose the same object multiple times?

Example: You have 3 types of fruit (apples, bananas, cherries) and you want to buy 5 pieces. How many combinations?

This isn't C(3, 5)—that would mean choosing 5 from 3, which makes no sense when k > n. You need combinations with repetition.

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

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

Why this formula? It's a clever trick. Imagine arranging 5 pieces of fruit and 2 dividers (to separate the 3 types). For instance:

• AA|BB|C means 2 apples, 2 bananas, 1 cherry
• |BBB|CC means 0 apples, 3 bananas, 2 cherries

You have 7 positions (5 fruit + 2 dividers), and you're choosing which 5 are fruit. That's C(7, 5).

This technique—transforming a problem into a different combinatorial structure—is everywhere in combinatorics.

The Pigeonhole Principle

One of the simplest yet most powerful ideas in combinatorics:

If you put n+1 pigeons into n holes, at least one hole contains more than one pigeon.

Trivial, right? Yet it leads to surprising results.

Example: In any group of 13 people, at least two were born in the same month. Why? 13 people (pigeons), 12 months (holes). By the pigeonhole principle, some month must contain at least two birthdays.

Example: In any sequence of n²+1 distinct integers, there exists either an increasing subsequence of length n+1 or a decreasing subsequence of length n+1.

This is the Erdős–Szekeres theorem, and it's proven using the pigeonhole principle. It guarantees structure in seemingly random sequences.

The principle seems too simple to be useful, but it's a forcing function: it proves existence without construction. You don't need to find which hole has multiple pigeons—you know one must.

Applications in Computer Science

Combinatorics isn't abstract theory. It's the mathematics underlying computational possibility spaces.

Cryptography

Modern encryption relies on combinatorial explosions. RSA encryption uses large prime numbers—finding the prime factors of a 2048-bit number requires searching a space so large that brute force is infeasible. The security comes from counting: there are too many possibilities to try them all.

Algorithm Analysis

How many comparisons does a sorting algorithm make? Combinatorics gives the answer. Sorting n items requires at least n log n comparisons in the worst case because there are n! possible orderings, and each comparison gives you at most 1 bit of information. To distinguish between n! possibilities with binary questions requires log₂(n!) ≈ n log n questions.

This isn't just theory—it's a fundamental limit on sorting efficiency.

Data Structures

Hash tables distribute n items into m buckets. The birthday problem (a combinatorial classic) predicts collisions: with 23 people in a room, there's a 50% chance two share a birthday. With n items hashed into m buckets, collisions appear faster than intuition suggests. Combinatorics tells you when and why.

Network Routing

How many paths exist between two nodes in a network? Combinatorics counts them. Google Maps doesn't try every possible route—it prunes based on combinatorial structure (graph theory, which we'll explore later).

Machine Learning

Training a neural network involves exploring a high-dimensional parameter space. How many possible configurations of weights exist? Combinatorics (and probability) characterize this space, informing optimization strategies.

The Inclusion-Exclusion Principle

Counting gets tricky when categories overlap.

Problem: In a class of 30 students, 18 study French, 15 study Spanish, and 7 study both. How many study at least one language?

You might add 18 + 15 = 33, but that's more than 30 students. Why? You counted the 7 who study both languages twice.

Inclusion-Exclusion Principle: |A ∪ B| = |A| + |B| - |A ∩ B|

Translation: The size of the union equals the sum of individual sizes minus the overlap.

For our problem: 18 + 15 - 7 = 26 students study at least one language.

This extends to more sets: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

You add individual sizes, subtract pairwise overlaps, add back triple overlaps, and so on. The pattern alternates: add singles, subtract pairs, add triples, subtract quadruples...

This principle solves counting problems with overlapping categories—common in probability, logic, and database queries.

Generating Functions: Counting in Disguise

Here's a wild idea: encode counting problems into polynomials.

Suppose you want to count ways to make change for a dollar using quarters (25¢), dimes (10¢), and nickels (5¢).

Define a generating function: G(x) = (1 + x²⁵ + x⁵⁰ + x⁷⁵ + x¹⁰⁰) × (1 + x¹⁰ + x²⁰ + x³⁰ + ... + x¹⁰⁰) × (1 + x⁵ + x¹⁰ + x¹⁵ + ... + x¹⁰⁰)

Each factor represents one coin type. The exponent represents the value in cents.

When you multiply these polynomials and expand, the coefficient of x¹⁰⁰ (the term for 100 cents) counts the number of ways to make a dollar.

This seems absurd—turning a counting problem into algebra—but it works. Generating functions transform combinatorial questions into algebraic manipulations. You can use calculus, series expansions, and algebraic tricks to extract combinatorial answers.

Donald Knuth, in Concrete Mathematics, calls generating functions "the most important tool in enumeration." They unify disparate counting problems under a single framework.

Catalan Numbers: Counting Balanced Structures

Some combinatorial sequences appear everywhere.

The Catalan numbers (1, 1, 2, 5, 14, 42, 132, ...) count:

• Balanced parentheses strings of length 2n
• Binary trees with n internal nodes
• Ways to triangulate a convex polygon with n+2 sides
• Paths from (0,0) to (n,n) that don't cross the diagonal
• Ways to multiply n+1 matrices (order of associative operations)

Wait—these problems seem unrelated. Why the same sequence?

Because they're structurally equivalent. Combinatorics reveals that seemingly different problems share hidden structure. A balanced parentheses string corresponds to a binary tree, which corresponds to a triangulated polygon.

The Catalan numbers appear in parsing algorithms (syntax trees), computational geometry (polygon triangulation), and even in quantum mechanics (lattice path models).

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

You don't need to enumerate all binary trees with 5 nodes—just calculate C₅ = 42.

Stirling Numbers: Partitioning Sets

How many ways can you partition n distinct objects into k non-empty subsets?

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

Example: How many ways can you partition 4 people into 2 groups? S(4, 2) = 7.

You can verify: {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}.

Seven ways.

Stirling numbers appear in:

• Clustering problems (partition n items into k clusters)
• Set partitions in probability
• Polynomial interpolation

Another variant, Stirling numbers of the first kind, counts permutations with a given number of cycles. These numbers connect combinatorics, algebra, and number theory.

Derangements: Counting Disorder

A derangement is a permutation where no element stays in its original position.

Example: Four people check their coats. The coat check mixes them up. How many ways can all four people get the wrong coat?

This is a derangement of 4 objects: D(4) = 9.

The formula for derangements: D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + 1/4! - ... ± 1/n!)

Astonishingly, as n grows, the probability that a random permutation is a derangement approaches 1/e ≈ 36.8%.

Derangements appear in probability (matching problems), cryptography (avoiding fixed points), and even in secret Santa assignments (everyone must give to someone else).

Why Combinatorics Feels Hard

Unlike calculus, where you learn techniques and apply them, combinatorics often feels like puzzle-solving. Each problem requires recognizing structure, choosing the right model, and avoiding subtle overcounting or undercounting errors.

There's no single "combinatorics algorithm." Instead, you have a toolkit:

• Multiplication and addition principles
• Permutations and combinations
• Inclusion-exclusion
• Generating functions
• Recursive counting (which leads to recurrence relations, our next topic)

Mastery comes from recognizing which tool fits which problem. And that requires practice, pattern recognition, and a bit of creativity.

But here's the payoff: once you see combinatorial structure, you see it everywhere. Password security, genetic variation, network resilience, machine learning model spaces—they're all counting problems in disguise.

The Unreasonable Effectiveness of Counting

Combinatorics doesn't just count. It characterizes possibility spaces.

When you know there are 52! ways to shuffle a deck, you know every shuffle you've ever done has produced a unique sequence never before seen in human history. The space is too large for repetition.

When you know a 12-character password has 10¹⁵ possibilities, you know brute-force cracking takes centuries.

When you know a sorting algorithm requires at least n log n comparisons, you know you've hit a fundamental limit—no algorithm can do better.

Combinatorics doesn't just answer "how many?" It answers "what's possible?" and "what's impossible?" It maps the boundaries of computational feasibility.

And in a world increasingly shaped by algorithms, networks, and digital systems, understanding those boundaries is understanding the structure of reality itself.

Further Reading

• Graham, Ronald L., Donald E. Knuth, and Oren Patashnik. Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 2nd edition, 1994.
• Stanley, Richard P. Enumerative Combinatorics (2 volumes). Cambridge University Press, 1997–1999.
• Wilf, Herbert S. Generatingfunctionology. A K Peters, 3rd edition, 2005.
• Lovász, László. Combinatorial Problems and Exercises. North-Holland, 2nd edition, 1993.
• Erdős, Paul, and George Szekeres. "A combinatorial problem in geometry." Compositio Mathematica, 1935. (The pigeonhole principle in action)

This is Part 2 of the Discrete Mathematics series, exploring the foundational math of computer science, algorithms, and computational thinking. Next: "Permutations Explained — When Order Matters."

Part 2 of the Discrete Mathematics series.

Previous: What Is Discrete Mathematics? The Math of Distinct Objects Next: Permutations: Ordered Arrangements