Counting Techniques

⚡ Key Takeaways

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.

💡 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.

DefinitionMultiplication 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.

1

\quad N = n_1 \times n_2 \times \cdots \times n_k = \prod_{i=1}^{k} n_i

Derivation hint: 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.

2

\quad N = a_1 + a_2 + \cdots + a_k = \sum_{i=1}^{k} a_i

Derivation hint: 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=\varnothing$ .

DefinitionFactorial

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

3

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

Derivation hint: 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$ .

DefinitionPermutations

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

4

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

Derivation hint: 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)!$ .

DefinitionCombinations

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

5

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

Derivation hint: each unordered selection of $r$ items can be ordered in $r!$ ways; since permutations count those orderings separately, divide $P(n,r)$ by $r!$ .

TheoremSymmetry and Pascal's Rule

The binomial coefficients satisfy:

6

\quad \binom{n}{r} = \binom{n}{n-r}, \qquad \binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}

Derivation hint: 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).

TheoremSelections 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:

7

\quad n^r, \qquad \frac{n!}{n_1!\,n_2!\cdots n_k!}, \qquad \binom{n+r-1}{r}

Derivation hint: 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.

ProofCombinations via Division by Symmetry

We prove equation [5], that $\binom{n}{r}=P(n,r)/r!$ . 1. 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)!$ . 2. 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. 3. Each combination is overcounted $r!$ times. Therefore the $P(n,r)$ ordered selections fall into groups of exactly $r!$ , one group per combination. 4. Divide to remove overcounting. The number of combinations is $\binom{n}{r} = P(n,r)/r! = n!/(r!(n-r)!)$ . $\blacksquare$

∎

ProofStars and Bars

We prove the combinations-with-repetition formula $\binom{n+r-1}{r}$ in [7]. 1. 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+\cdots+x_n = r$ . 2. Represent with symbols. Write $r$ identical stars ( $\star$ ) and $n-1$ bars ( $|$ ). The bars partition the stars into $n$ groups; group $i$ 's star count is $x_i$ . 3. 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. 4. Choose star positions. Such arrangements number $\binom{n+r-1}{r}$ — pick which $r$ of the $n+r-1$ positions hold stars. $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

```svg

```

ExampleForming 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$ .

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

> Answer: (a) $\boxed{1320 \text{ ordered selections}}$ (b) $\boxed{220 \text{ committees}}$

ExampleArrangements 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: 1. If all 11 letters were distinct, there would be $11!$ orderings. 2. 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. 3. 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: $\boxed{34\,650 \text{ distinct arrangements}}$

⚠️ Common mistake

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 $10^4 = 10000$ , not $P(10,4)=5040$ .

Counterexample

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

Why it fails: $52^5 = 380\,204\,032$ 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:

\binom{52}{5} = \frac{52!}{5!\,47!} = 2\,598\,960.

The erroneous figure overcounts by allowing impossible repeats and by treating each of the $5!=120$ orderings of a hand as distinct.

connection

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 $\binom{n}{r}$ 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.

🔬 Where this appears

⏳ History

- 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.

open-problem

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.

Formal Statement

Why It Holds

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also