Counting Techniques

Counting techniques are systematic methods for determining the number of outcomes, arrangements, or selections in a finite set without listing them all. The core results are the multiplication principle, permutations (ordered)

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

, and combinations (unordered)

C (n, r) = n! / (r! (n - r)!)

. They apply throughout probability, statistics, computer science, and discrete mathematics. The field grew from gambling problems studied by Pascal and Fermat (1654) and the combinatorial work of Pascal, Bernoulli, and Euler.

Counting techniques, the foundation of enumerative combinatorics, answer the question "how many ways?" by exploiting structure rather than brute-force listing. They matter because almost every probability calculation reduces to counting favorable outcomes and dividing by total outcomes, and because many problems involve quantities far too large to enumerate by hand — a 52-card deck can be arranged in roughly $8 \times 1 0^{67}$ ways. The central distinction is between situations where order matters (permutations) and where it does not (combinations), and between selecting with or without repetition. A surprising fact: the number of ways to choose a committee of any size from $n$ people equals $2^{n}$ , the same as the number of binary strings of length $n$ — counting reveals deep equivalences between seemingly unrelated structures.

The Core Insight

Every counting problem is built from two atomic operations. If a task can be done in stages where you do stage 1 and stage 2 and ..., you multiply the counts. If a task can be done by choosing alternative methods — method A or method B — and these never overlap, you add the counts. All of permutations, combinations, and their variants are just disciplined applications of "multiply for AND, add for OR," combined with division to correct for overcounting equivalent arrangements.

Formal Statement

Multiplication and Addition Principles

The Multiplication Principle: if a procedure consists of $k$ independent stages, with $n_{1}$ choices at stage 1, $n_{2}$ at stage 2, ..., $n_{k}$ at stage $k$ , the total number of outcomes is the product.

N = n_{1} \times n_{2} \times \dots \times n_{k} = i = 1 \prod k n_{i}

⟳build the outcome stage by stage; each choice at one stage pairs with every choice at the next, forming a tree whose leaf count is the product.

The Addition Principle: if a task can be accomplished by one of $k$ mutually exclusive (disjoint) categories with $a_{1}, a_{2}, \dots, a_{k}$ ways respectively, the total is the sum.

N = a_{1} + a_{2} + \dots + a_{k} = i = 1 \sum k a_{i}

⟳disjoint sets share no elements, so the size of their union equals the sum of sizes — formalized by the cardinality rule

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣

when

A \cap B = \emptyset

Factorial

For a non-negative integer $n$ , the factorial $n!$ counts the orderings (permutations) of $n$ distinct objects.

n! = n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1, 0! = 1

⟳the first position has

n

choices, the second

n - 1

(one used), and so on by the multiplication principle; the empty arrangement gives

0! = 1

Permutations

A permutation is an ordered selection of $r$ objects from $n$ distinct objects (no repetition). The count is denoted $P (n, r)$ , $_{n} P_{r}$ , or $P_{r}^{n}$ .

P (n, r) = \frac{n !}{( n - r )!} = n (n - 1) (n - 2) \dots (n - r + 1)

⟳fill

r

ordered slots — the first has

n

choices, the next

n - 1

, down to

n - r + 1

for the

r

-th; this product equals

n! / (n - r)!

Combinations

A combination is an unordered selection of $r$ objects from $n$ distinct objects (no repetition). The count is denoted $C (n, r)$ , $_{n} C_{r}$ , or the binomial coefficient $(r n)$ .

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

⟳each unordered selection of

r

items can be ordered in

r!

ways; since permutations count those orderings separately, divide

P (n, r)

r!

Symmetry and Pascal's Rule

The binomial coefficients satisfy:

(r n) = (n - r n), (r n) = (r - 1 n - 1) + (r n - 1)

⟳symmetry — choosing

r

to keep is equivalent to choosing

n - r

to discard. Pascal's rule — split selections by whether a fixed element is included (left term) or excluded (right term).

Selections with Repetition

Permutations with repetition (each of

r

slots independently chosen from

n

options):

n^{r}

. Permutations of a multiset with

n

total objects of types having counts

n_{1}, \dots, n_{k}

(with

\sum n_{i} = n

): the multinomial count. Combinations with repetition (unordered, repeats allowed) choosing

r

from

n

types:

n^{r}, \frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}, (r n + r - 1)

⟳independent slots multiply (

n^{r}

). The multiset formula divides

n!

by the internal orderings of identical objects. Combinations with repetition use the "stars and bars" bijection placing

r

stars into

n

bins via

n - 1

dividers.

Why It Holds

Combinations via Division by Symmetry

We prove equation [5], that $(r n) = P (n, r) / r!$ .

Count ordered selections. By [4], the number of ways to pick $r$ objects from $n$ with order mattering is $P (n, r) = n! / (n - r)!$ .
Group equivalent orderings. Take any single unordered set of $r$ chosen objects. Those same $r$ objects can be arranged in $r!$ distinct orders (by [3]). All $r!$ of these orderings are different permutations but represent the same combination.
Each combination is overcounted $r!$ times. Therefore the $P (n, r)$ ordered selections fall into groups of exactly $r!$ , one group per combination.
Divide to remove overcounting. The number of combinations is $(r n) = P (n, r) / r! = n! / (r! (n - r)!)$ . $■$

Stars and Bars

We prove the combinations-with-repetition formula $(r n + r - 1)$ in [7].

Encode a selection as a sequence. Choosing $r$ items from $n$ types with repetition is the same as deciding how many of each type, i.e. non-negative integers $x_{1} + x_{2} + \dots + x_{n} = r$ .
Represent with symbols. Write $r$ identical stars ( $⋆$ ) and $n - 1$ bars ( $∣$ ). The bars partition the stars into $n$ groups; group $i$ 's star count is $x_{i}$ .
Count the arrangements. A valid solution corresponds bijectively to an arrangement of $r$ stars and $n - 1$ bars in a row of $n + r - 1$ symbols.
Choose star positions. Such arrangements number $(r n + r - 1)$ — pick which $r$ of the $n + r - 1$ positions hold stars. $■$

Blaise Pascal | 1623–1662

French mathematician, physicist, and philosopher. In a famous 1654 correspondence with Pierre de Fermat over the "problem of points" (how to fairly divide stakes in an interrupted game of chance), Pascal laid foundations for both probability theory and systematic combinatorics. His Traité du triangle arithmétique (published 1665) organized the binomial coefficients into the arithmetical triangle now bearing his name, proving Pascal's rule and connecting it to combinations and to the binomial theorem. He united algebraic identities with combinatorial counting, a synthesis at the heart of the subject.

Building Intuition

Picture filling boxes left to right. Permutations = "lining people up for a photo": position one, position two — order is visible, so swapping two people gives a genuinely different photo. Combinations = "picking a team": once chosen, the team is the same regardless of who you named first, so you must divide out the irrelevant orderings.

A reliable decision rule: ask "if I swap two of my chosen items, is it a different outcome?" If yes → permutation. If no → combination. The division by $r!$ in [5] is precisely the "swapping doesn't matter" correction.

Decision tree for choosing a counting method based on order and repetition

<svg viewBox="0 0 640 420" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="420" fill="#0a0e17"/>
<rect x="240" y="20" width="160" height="46" rx="6" fill="none" stroke="#94a3b8"/>
<text x="320" y="40" fill="#e2e8f0" font-size="13" text-anchor="middle">Selecting r from n?</text>
<text x="320" y="57" fill="#e2e8f0" font-size="13" text-anchor="middle">Does ORDER matter?</text>

<line x1="290" y1="66" x2="150" y2="120" stroke="#94a3b8"/>
<line x1="350" y1="66" x2="490" y2="120" stroke="#94a3b8"/>
<text x="200" y="100" fill="#d4a853" font-size="13">YES (ordered)</text>
<text x="420" y="100" fill="#d4a853" font-size="13">NO (unordered)</text>

<rect x="70" y="122" width="170" height="44" rx="6" fill="none" stroke="#94a3b8"/>
<text x="155" y="148" fill="#e2e8f0" font-size="12" text-anchor="middle">Repetition allowed?</text>
<rect x="405" y="122" width="170" height="44" rx="6" fill="none" stroke="#94a3b8"/>
<text x="490" y="148" fill="#e2e8f0" font-size="12" text-anchor="middle">Repetition allowed?</text>

<line x1="110" y1="166" x2="70" y2="220" stroke="#94a3b8"/>
<line x1="200" y1="166" x2="240" y2="220" stroke="#94a3b8"/>
<line x1="450" y1="166" x2="410" y2="220" stroke="#94a3b8"/>
<line x1="540" y1="166" x2="580" y2="220" stroke="#94a3b8"/>

<rect x="10" y="222" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="70" y="243" fill="#e2e8f0" font-size="12" text-anchor="middle">YES</text>
<text x="70" y="261" fill="#d4a853" font-size="14" text-anchor="middle">n^r</text>

<rect x="180" y="222" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="240" y="243" fill="#e2e8f0" font-size="12" text-anchor="middle">NO</text>
<text x="240" y="261" fill="#d4a853" font-size="13" text-anchor="middle">n!/(n−r)!</text>

<rect x="350" y="222" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="410" y="243" fill="#e2e8f0" font-size="12" text-anchor="middle">YES</text>
<text x="410" y="261" fill="#d4a853" font-size="13" text-anchor="middle">C(n+r−1, r)</text>

<rect x="520" y="222" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="580" y="243" fill="#e2e8f0" font-size="12" text-anchor="middle">NO</text>
<text x="580" y="261" fill="#d4a853" font-size="13" text-anchor="middle">C(n, r)</text>

<text x="320" y="330" fill="#e2e8f0" font-size="13" text-anchor="middle">Permutations (left) — order distinguishes outcomes</text>
<text x="320" y="352" fill="#e2e8f0" font-size="13" text-anchor="middle">Combinations (right) — order ignored, divide by r!</text>
<text x="320" y="386" fill="#94a3b8" font-size="11" text-anchor="middle">Multiplication principle underlies every branch</text>
</svg>

Worked Examples

Forming a Committee with Roles vs. Without

Given: A club of 12 members. (a) How many ways to choose a president, secretary, and treasurer (distinct roles)? (b) How many ways to choose a 3-person committee (no roles)? Solution (a): Roles make order matter → permutation with

n = 12

r = 3

P (12, 3) = \frac{12 !}{9 !} = 12 \times 11 \times 10 = 1320.

Solution (b): No roles → combination; divide the permutation count by

3! = 6

(3 12) = \frac{P ( 12 , 3 )}{3 !} = \frac{1320}{6} = 220.

Answer: (a) $1320 ordered selections$ (b) $220 committees$

Arrangements of a Word with Repeated Letters

Given: Count the distinct arrangements of the letters in MISSISSIPPI (11 letters: M×1, I×4, S×4, P×2). Steps:

If all 11 letters were distinct, there would be $11!$ orderings.
Identical letters create indistinguishable repeats. Divide by the internal orderings of each repeated group using formula [7]: $4!$ for the I's, $4!$ for the S's, $2!$ for the P's, $1!$ for M.
Compute:

\frac{11 !}{1 ! 4 ! 4 ! 2 !} = \frac{39 916 800}{1 \cdot 24 \cdot 24 \cdot 2} = \frac{39 916 800}{1152} = 34 650.

Answer: $34650 distinct arrangements$

Common Misconceptions

Confusing permutations and combinations is the single most frequent error. Always ask whether reordering the same chosen items produces a new outcome. Lottery numbers (unordered) → combination. PIN codes or race finishing positions (ordered) → permutation. A second trap: forgetting that "with repetition" changes the formula entirely — a 4-digit PIN allowing repeats gives

1 0^{4} = 10000

, not

P (10, 4) = 5040

. Claim (false): "To count 5-card poker hands, since there are 52 cards and 5 positions, the answer is

5 2^{5}

." Why it fails:

5 2^{5} = 380204032

counts ordered draws with repetition — but a hand cannot contain the same physical card twice, and the order you receive cards is irrelevant. The correct count is unordered, without repetition:

(5 52) = \frac{52 !}{5 ! 47 !} = 2598 960.

The erroneous figure overcounts by allowing impossible repeats and by treating each of the

5! = 120

orderings of a hand as distinct.

Connections

Counting techniques are the computational backbone of Probability Theory: a probability is favorable outcomes divided by total outcomes, each obtained by counting. The binomial coefficient $(r n)$ in [5] reappears as the coefficient in the Binomial Theorem expansion of $(a + b)^{n}$ , and arranged in a triangle it is Pascal's Triangle. The addition and multiplication principles generalize to Set Theory via the Inclusion-Exclusion Principle for overlapping cases, and the entire framework forms the introductory layer of Combinatorics and underlies the Binomial Distribution in statistics.

Real-World Applications

Cryptography and passwords: estimating keyspace size — an 8-character password from 95 printable ASCII symbols yields $9 5^{8} \approx 6.6 \times 1 0^{15}$ possibilities, guiding brute-force resistance.
Lottery and gambling odds: the U.S. Powerball jackpot odds derive from $(5 69) \times 26 = 292201338$ combinations.
Genetics and DNA: counting possible codons ( $4^{3} = 64$ from four bases in triplets) and offspring genotype distributions.
Network routing and IP addressing: IPv4 provides $2^{32} \approx 4.3$ billion addresses; counting determines exhaustion.
Scheduling and tournaments: a round-robin with $n$ teams requires $(2 n)$ matches.
Quality control sampling: counting the ways to draw defective and good items underlies acceptance-sampling statistics.
Error-correcting codes: Hamming and other codes use combinatorial counts to bound how many bit-patterns a code can distinguish.

Historical Development

c. 1150 — India: Bhāskara II's Līlāvatī gives combinatorial rules for permutations and combinations, including arrangements of objects with repeats.
c. 1300 — China: Zhu Shijie's Jade Mirror of the Four Unknowns depicts the binomial-coefficient triangle ("Yang Hui's triangle"), known earlier to Jia Xian (~1050).
1654 — France: Pascal and Fermat exchange letters on the "problem of points," founding probability and rigorous counting.
1665 — France: Pascal's Traité du triangle arithmétique posthumously published, systematizing binomial coefficients.
1713 — Switzerland: Jacob Bernoulli's Ars Conjectandi formalizes permutations, combinations, and the binomial distribution.
1736 — Russia: Euler solves the Seven Bridges of Königsberg, launching graph-theoretic and structural counting.
1830s — Britain: development of generating-function methods; later formalized in the 20th century for advanced enumeration.
1854 — Britain: George Boole's logic foundations underpin set-based counting and inclusion–exclusion.
20th century: combinatorics matures into a discipline (Riordan, Rota), with applications exploding in computer science and coding theory.

Subtleties & Limits

Elementary counting handles independent, well-structured selections, but real problems often involve constraints (forbidden adjacencies, mandatory inclusions) that elementary formulas cannot directly express; these require Inclusion-Exclusion Principle, generating functions, or recursion. Counting structures up to symmetry (e.g., distinct necklaces, colorings of a cube) needs Burnside's lemma and Pólya enumeration — beyond introductory scope. Moreover, some counting questions are computationally hard: the general problem of counting the number of solutions to combinatorial systems (the complexity class #P) is believed intractable, so even when a count is well-defined, no efficient formula may exist. Determining exact formulas for many lattice-path and partition counts remains an active research frontier.