Counting and Combinatorics

How many different passwords can you make from eight characters? How many ways can a committee of 3 be chosen from 20 people? How many possible outcomes are there when you deal a poker hand? You could try to list them all — but the numbers explode so fast that listing is hopeless. Combinatorics is the branch of mathematics that answers "how many?" without writing out every possibility. It gives you a small toolkit of principles that turn overwhelming counting problems into short arithmetic.

Counting well is a superpower that quietly underlies probability, cryptography, computer science, and statistics. Almost every probability is a count divided by a count, so if you cannot count, you cannot compute chances. This page teaches you to reason about counting — to see the structure of a problem — rather than memorize disconnected formulas.

Learning Objectives

• Apply the multiplication (product) principle and the addition principle to break problems into stages.
• Compute permutations (ordered arrangements) and understand factorial notation.
• Compute combinations (unordered selections) and read the binomial coefficient $\binom{n}{k}$.
• Decide correctly whether order matters and whether repetition is allowed.
• Use the pigeonhole principle to prove that certain coincidences are unavoidable.
• Connect counting to probability and to Pascal's triangle.

Quick Answer

Combinatorics counts outcomes without listing them. The multiplication principle says that if a task has stages with $a$, $b$, $c$, … independent choices each, the total number of outcomes is the product $a \times b \times c \times \cdots$. A permutation counts ordered arrangements: the number of ways to arrange $k$ items chosen from $n$ distinct items is $P(n,k) = \frac{n!}{(n-k)!}$. A combination counts unordered selections: $\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$. The key decision is always whether order matters. Finally, the pigeonhole principle guarantees that if you put more than $n$ items into $n$ boxes, some box holds at least two.

Where It Came From

People counted arrangements long before there was a theory of it. Ancient Indian mathematicians studied combinations of syllables and musical rhythms; the Chandaḥśāstra of Piṅgala (roughly 3rd–2nd century BCE) already contained rules equivalent to binomial coefficients, and later commentators like Halayudha described the triangle of numbers we now call Pascal's triangle. Medieval Hebrew and Islamic scholars, including Abraham ibn Ezra and later al-Kāshī, computed combinations for astrological and algebraic purposes.

The subject became a systematic science in 17th-century Europe, and the driving force was gambling. In 1654 a French nobleman and gambler, the Chevalier de Méré, posed dice-and-stakes puzzles to Blaise Pascal. Pascal exchanged a famous series of letters with Pierre de Fermat, and in working out how to fairly divide the stakes of an interrupted game (the "problem of points"), they had to count outcomes carefully. That correspondence is usually credited as the birth of probability theory — and it forced counting techniques into a rigorous shape. Pascal's Treatise on the Arithmetical Triangle organized the binomial coefficients so systematically that the triangle now bears his name. The need, then, was concrete: to answer "in how many ways can this happen?" so that fair odds and fair payouts could be computed. Later, Jacob Bernoulli's Ars Conjectandi (1713) turned these methods into a full theory, and the German philosopher Leibniz even coined the term combinatorics.

The Multiplication Principle: Counting in Stages

The foundational tool is the multiplication principle: if a process consists of a sequence of independent choices, and stage 1 can be done in $a$ ways, stage 2 in $b$ ways, and so on, then the whole process can be done in $a \times b \times \cdots$ ways. The choices must be independent in the sense that the number of options at each stage does not depend on the earlier choice.

Worked example. A cafe offers 3 sizes of coffee, 4 syrup flavours, and 2 types of milk. How many distinct drinks are possible? Each drink is one choice from each stage, so:

$3 \times 4 \times 2 = 24$

There are 24 possible drinks — and we never had to list them.

Worked example (with a twist — no repetition). How many 3-letter "words" (any letter string, not necessarily real words) can be formed from the 26 letters if letters may not repeat? The first letter has 26 options, but once used it is gone, so the second has 25, and the third 24:

$26 \times 25 \times 24 = 15,600$

If repetition were allowed, the count would instead be $26 \times 26 \times 26 = 17,576$. Deciding whether repetition is allowed is half the battle.

There is a companion rule, the addition principle: if a task can be done in one of several mutually exclusive ways — group A with $m$ options or group B with $n$ options, never both — the total is $m + n$. Use "multiply" for stages you do in sequence ("and"), and "add" for separate cases ("or").

Permutations: When Order Matters

A permutation is an ordered arrangement. The number of ways to arrange all $n$ distinct objects in a row is $n$ factorial:

$n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1, \qquad 0! = 1$

The definition $0! = 1$ is a convention that makes the formulas below work; there is exactly one way to arrange zero objects (do nothing).

When you arrange only $k$ of the $n$ objects, you use the permutation formula:

$P(n,k) = \frac{n!}{(n-k)!}$

Worked example. In how many ways can gold, silver, and bronze medals be awarded among 8 runners? Order matters (gold $\neq$ bronze), no repetition:

$P(8,3) = \frac{8!}{5!} = 8 \times 7 \times 6 = 336$

This matches the multiplication principle directly: 8 choices for gold, 7 for silver, 6 for bronze.

Worked example (repeated items). How many distinct arrangements of the letters in BANANA? There are 6 letters, but with 3 A's and 2 N's that are indistinguishable, so we divide out the redundant orderings:

$\frac{6!}{3!\,2!\,1!} = \frac{720}{6 \times 2 \times 1} = 60$

There are 60 distinct arrangements.

Combinations: When Order Does Not Matter

A combination is a selection where order is irrelevant — a committee, a hand of cards, a subset. The number of ways to choose $k$ items from $n$ is the binomial coefficient, read "$n$ choose $k$":

$\binom{n}{k} = \frac{n!}{k!\,(n-k)!}$

The intuition: start from the permutation count $P(n,k)$, then divide by $k!$ because each unordered group of $k$ items was counted $k!$ times (once for each of its orderings).

Worked example. How many ways to choose a 3-person committee from 20 people? Order does not matter:

$\binom{20}{3} = \frac{20!}{3!\,17!} = \frac{20 \times 19 \times 18}{3 \times 2 \times 1} = \frac{6840}{6} = 1140$

Worked example (probability). What is the probability of being dealt 2 aces in a 5-card poker hand? Total hands: $\binom{52}{5} = 2,598,960$. Favourable hands: choose 2 of the 4 aces and 3 of the remaining 48 cards:

$\binom{4}{2}\binom{48}{3} = 6 \times 17,296 = 103,776$

So the probability is $\frac{103,776}{2,598,960} \approx 0.0399$, about 4%. This is combinatorics doing exactly what it was invented for.

A useful identity is the symmetry rule $\binom{n}{k} = \binom{n}{n-k}$: choosing which $k$ to include is the same as choosing which $n-k$ to leave out.

The Pigeonhole Principle: Guaranteed Coincidences

The pigeonhole principle sounds almost too obvious to be useful: if you place $n+1$ items into $n$ boxes, at least one box contains two or more items. Yet it proves surprising facts with no calculation at all.

Worked example. Among any 13 people, at least two share a birth month. There are only 12 months (boxes) and 13 people (pigeons), so two must land in the same month.

Generalized form. If $N$ items go into $k$ boxes, some box holds at least $\left\lceil \frac{N}{k} \right\rceil$ items.

Worked example. In any group of 30 students, at least $\left\lceil \frac{30}{12} \right\rceil = 3$ share a birth month. The principle guarantees the coincidence exists — even though it tells you nothing about which month.

Real-World Applications

• Cryptography and passwords. The strength of a password is literally a multiplication-principle count: an 8-character password from 94 printable symbols has $94^8 \approx 6.1 \times 10^{15}$ possibilities, which sets how long a brute-force attack takes.
• Probability and statistics. Card games, lotteries, quality-control sampling, and hypothesis tests all rest on counting favourable versus total outcomes.
• Genetics and chemistry. Counting possible DNA sequences, protein arrangements, or isomers of a molecule uses permutations and combinations directly.
• Scheduling and networks. Counting possible timetables, tournament pairings, or routes underlies logistics and computer-science algorithms.
• Hashing (pigeonhole). Because a hash maps many inputs to fewer slots, collisions are unavoidable — a direct consequence of the pigeonhole principle.

Common Mistakes

1. Confusing permutations with combinations. Students apply $\binom{n}{k}$ to a problem where order matters (or vice versa). Why it's wrong: a "committee" and a "ranked podium" are structurally different. Correction: ask first, "if I swap two chosen items, is it a different outcome?" If yes, order matters (permutation); if no, use a combination.

2. Adding when you should multiply (or the reverse). Writing $3 + 4 + 2$ for the coffee example instead of $3 \times 4 \times 2$. Why it's wrong: addition is for mutually exclusive cases ("or"), multiplication for sequential independent choices ("and"). Correction: map each stage to "and" (multiply) or each alternative to "or" (add) before computing.

3. Mishandling repetition. Using $P(n,k)$ when items can repeat, e.g. counting 4-digit PINs as $10 \times 9 \times 8 \times 7$ instead of $10^4$. Why it's wrong: a PIN can be 7777, so digits repeat. Correction: check explicitly whether the same item can be reused; if so, each stage keeps its full number of options.

Comparison and Connections

The single most important distinction in counting is whether order matters and whether repetition is allowed. This table summarizes the four cases of choosing $k$ from $n$:

Situation	Order matters?	Repetition?	Formula
Arrangement, no repeats	Yes	No	$P(n,k)=\dfrac{n!}{(n-k)!}$
Arrangement, with repeats	Yes	Yes	$n^k$
Selection, no repeats	No	No	$\dbinom{n}{k}=\dfrac{n!}{k!(n-k)!}$
Selection, with repeats	No	Yes	$\dbinom{n+k-1}{k}$

Combinatorics connects tightly to probability (every equally-likely probability is a ratio of counts), to the binomial theorem (the coefficients in $(a+b)^n$ are exactly $\binom{n}{k}$), and to Pascal's triangle, where each entry is a binomial coefficient built from the rule $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$.

Practice Questions

Recall

State the formulas for $P(n,k)$ and $\binom{n}{k}$, and explain in one sentence how they differ.

Answer: $P(n,k)=\frac{n!}{(n-k)!}$ counts ordered arrangements; $\binom{n}{k}=\frac{n!}{k!(n-k)!}$ counts unordered selections. They differ by the factor $k!$, the number of orderings of each chosen group.

Understanding

Why does $\binom{n}{k} = \binom{n}{n-k}$? Explain without computing.

Answer: Choosing the $k$ items to include automatically determines the $n-k$ items to exclude. Every selection of $k$ corresponds to exactly one selection of the complementary $n-k$, so the two counts are equal.

Application

A pizza shop has 10 toppings. How many pizzas can you make with exactly 3 toppings? What if you also choose one of 2 crusts?

Answer: $\binom{10}{3} = \frac{10 \times 9 \times 8}{6} = 120$ topping-sets. With 2 crusts, multiply: $120 \times 2 = 240$ pizzas.

Analysis

Show that among any 5 points placed inside a unit square, two of them are within distance $\frac{\sqrt{2}}{2}$ of each other.

Answer: Split the unit square into four smaller squares of side $\frac12$. With 5 points and 4 sub-squares, the pigeonhole principle forces two points into the same sub-square. The farthest two points in a $\frac12 \times \frac12$ square are at its diagonal, length $\sqrt{(1/2)^2+(1/2)^2}=\frac{\sqrt2}{2}$, so those two points are within that distance.

FAQ

When exactly do I use a permutation instead of a combination? Use a permutation when rearranging the chosen items produces a genuinely different outcome — rankings, sequences, seat orders, passwords. Use a combination when the items form an unordered group — committees, hands, subsets. Test it: swap two of your chosen items and ask whether anything changed.

Why is $0! = 1$? It is defined that way so formulas stay consistent. For instance $\binom{n}{n}=\frac{n!}{n!\,0!}$ should equal 1 (there is one way to choose everything), which only works if $0! = 1$. Conceptually, there is exactly one arrangement of an empty set: do nothing.

What's the difference between the multiplication principle and permutations? They are the same idea; permutations are just the multiplication principle applied to a specific pattern (choosing without repetition). $P(8,3) = 8 \times 7 \times 6$ is literally the product rule in action. The formula is a shortcut for common cases.

How is this connected to probability? For equally likely outcomes, probability = (favourable outcomes) / (total outcomes), and both are counts. That is why combinatorics and probability grew up together in Pascal and Fermat's letters — you cannot find the odds until you can count the cases.

The pigeonhole principle seems obvious — why is it a big deal? Its power is that it proves existence with zero computation. It tells you a coincidence must occur even when finding it directly would be impossible, which makes it a favourite tool in proofs across number theory and computer science.

Quick Revision

• Multiplication principle: stages in sequence ("and") → multiply the options.
• Addition principle: separate exclusive cases ("or") → add the options.
• Factorial: $n! = n(n-1)\cdots 1$, and $0! = 1$.
• Permutation (order matters): $P(n,k)=\frac{n!}{(n-k)!}$.
• Combination (order doesn't): $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.
• With repetition, ordered: $n^k$. Unordered: $\binom{n+k-1}{k}$.
• Symmetry: $\binom{n}{k}=\binom{n}{n-k}$; Pascal: $\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}$.
• Pigeonhole: $n+1$ items in $n$ boxes → some box has $\ge 2$; generally $\ge \lceil N/k \rceil$.

Related Topics

Prerequisites

• Discrete Mathematics overview

Related Topics

• Probability (Statistics and Probability branch): ../../5._Statistics_and_Probability/index.md
• The binomial theorem and Pascal's triangle (Algebra)

Next Topics

• Graph theory and counting on graphs
• Discrete probability distributions