Counting Principles — Permutations and Combinations

⚡ Key Takeaways

Counting Principles — Permutations and Combinations are systematic methods for counting the number of ways to arrange or select objects without listing every possibility. Key result: order-sensitive selections of $r$ from $n$ objects number $P(n,r)=\frac{n!}{(n-r)!}$ ; order-blind selections number $C(n,r)=\frac{n!}{r!(n-r)!}$ . Where it applies: probability, combinatorics, algebra (binomial theorem), cryptography, scheduling, and statistics. Who/when: roots in ancient Indian and Chinese mathematics; formalized by Pascal, Fermat, and Leibniz in the 17th century.

💡 The Core Insight

Every counting problem reduces to two questions: (1) Does order matter? and (2) Are repetitions allowed? The answers select one of four standard formulas. Behind all of them lies a single device — the multiplication principle — which says that independent sequential choices multiply. Permutations apply this directly; combinations apply it and then divide out the over-counting caused by indistinguishable orderings.

DefinitionFundamental Counting Principles

The Addition Principle: if one task can be done in $m$ ways and a second, mutually exclusive, task in $n$ ways, then one of the two can be done in $m+n$ ways. The Multiplication Principle: if a procedure consists of a sequence of stages, with $n_1$ choices at stage 1, $n_2$ at stage 2, …, $n_k$ at stage $k$ (each independent of earlier outcomes), then the total number of outcomes is

1

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

Derivation hint: build outcomes as a tree — each stage multiplies the number of branches.

DefinitionFactorial

For a non-negative integer $n$ , the factorial $n!$ is the number of ways to arrange $n$ distinct objects in a row:

2

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

Derivation hint: apply the multiplication principle — $n$ choices for the first slot, $n-1$ for the second, and so on; the empty arrangement gives $0!=1$ . Here $n$ is a non-negative integer; the convention $0!=1$ makes later formulas consistent (there is exactly one way to arrange nothing).

DefinitionPermutations

A permutation of $r$ objects chosen from $n$ distinct objects (no repetition, order matters) is denoted $P(n,r)$ , $^nP_r$ , or $(n)_r$ , and equals

3

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

Derivation hint: $n$ choices for the first position, $n-1$ for the second, …, $n-r+1$ for the $r$ th — a product of $r$ falling factors. Symbols: $n$ = total distinct objects available; $r$ = number selected and arranged, with $0 \le r \le n$ .

DefinitionCombinations

A combination of $r$ objects chosen from $n$ distinct objects (no repetition, order does not matter) is denoted $C(n,r)$ , $^nC_r$ , or $\binom{n}{r}$ , and equals

4

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

Derivation hint: each unordered set of $r$ objects can be ordered in $r!$ ways, so divide the permutation count by $r!$ . Symbols: as above, with $0\le r\le n$ . The quantity $\binom{n}{r}$ is called a binomial coefficient.

TheoremPermutations with Repetition and Multiset Permutations

If repetition is allowed and order matters, the count of length- $r$ sequences from $n$ symbols is

5

\quad N_{\text{rep}} = n^{r}

Derivation hint: each of the $r$ positions independently has $n$ choices, so multiply $n$ by itself $r$ times. If we arrange all $n$ objects but they fall into groups of identical items of sizes $n_1, n_2, \dots, n_k$ (with $n_1+\cdots+n_k=n$ ), the number of distinct arrangements is the multinomial coefficient

6

\quad \frac{n!}{n_1!\,n_2!\cdots n_k!}

Derivation hint: start from $n!$ arrangements, then divide by $n_i!$ for each block of identical items, since permuting identical items changes nothing.

TheoremCombinations with Repetition — Stars and Bars

The number of ways to choose $r$ objects from $n$ types with repetition allowed and order irrelevant (a multiset of size $r$ ) is

7

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

Derivation hint: represent a selection as $r$ stars separated into $n$ groups by $n-1$ bars; arrange $r+(n-1)$ symbols and choose positions for the bars.

ProofDeriving P(n,r) and C(n,r) from the Multiplication Principle

Step 1. Count ordered selections. To fill $r$ ordered positions from $n$ distinct objects, the first position has $n$ candidates. Having used one, the second has $n-1$ , the third $n-2$ , and so on down to $n-r+1$ candidates for the $r$ th position.

Step 2. By the multiplication principle [1], the number of ordered selections is

P(n,r) = n(n-1)\cdots(n-r+1).

Step 3. Multiply and divide by $(n-r)!$ to compactify:

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

establishing [3].

Step 4. Now remove ordering. Group all ordered selections that use the same set of $r$ objects. Each such set can be arranged in $r!$ orders (by [2]), so every unordered selection corresponds to exactly $r!$ ordered ones.

Step 5. Therefore the number of unordered selections is

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

which is [4]. $\blacksquare$

∎

ProofPascal's Rule

We show $\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$ .

Step 1. Fix one distinguished object, say $x$ , among the $n$ .

Step 2. Partition all $r$ -subsets into two classes: those that contain $x$ and those that do not.

Step 3. Subsets containing $x$ are formed by choosing the remaining $r-1$ members from the other $n-1$ objects: $\binom{n-1}{r-1}$ ways.

Step 4. Subsets excluding $x$ are formed by choosing all $r$ members from the other $n-1$ objects: $\binom{n-1}{r}$ ways.

Step 5. By the addition principle these classes are disjoint and exhaustive, so summing gives the result. $\blacksquare$

∎

mathematician · Blaise Pascal | 1623–1662

The French mathematician, physicist, and philosopher Blaise Pascal systematized the arithmetic triangle of binomial coefficients in his Traité du triangle arithmétique (published 1665). Corresponding with Pierre de Fermat in 1654 over a gambling problem (the "problem of points"), Pascal helped lay the foundations of probability theory — and combinatorial counting is its backbone. Pascal's recursive construction of the triangle (each entry the sum of the two above it) is precisely Pascal's rule, and the triangle now bears his name in the Western tradition, though it was known centuries earlier in India, Persia, and China.

🧠 Intuition

Think of filling slots. A permutation is like assigning runners to the gold, silver, and bronze medals: the positions are labeled, so swapping two runners gives a genuinely different outcome. A combination is like choosing a committee of three from a club: the chosen people are just a set, and reordering them changes nothing. The bridge between them is the factor $r!$ — the number of ways to order the chosen group. Permutations keep those orderings as distinct; combinations collapse them into one. So you can always compute a combination by first counting ordered arrangements and then dividing away the orderings you didn't want. When deciding which tool to use, ask the two diagnostic questions and read off the formula:

Figure

Decision flow: order and repetition select the formula

```svg

```

ExampleForming Passwords — A Permutation Count

Given: A system requires a 4-character password using distinct letters from the 26-letter alphabet (case-insensitive, no letter repeated). How many passwords are possible? Then, how many if repetition is allowed?

Step 1 — No repetition, order matters. This is $P(26,4)$ :

P(26,4)=\frac{26!}{22!}=26\cdot25\cdot24\cdot23.

Step 2 — Evaluate. $26\cdot25=650$ ; $650\cdot24=15{,}600$ ; $15{,}600\cdot23=358{,}800$ .

Step 3 — With repetition. By [5], each of 4 slots has 26 choices:

26^4 = 456{,}976.

\boxed{P(26,4)=358{,}800 \text{ passwords; with repetition } 456{,}976 \text{ passwords}}

ExampleChoosing a Committee — A Combination Count

Given: From a club of 12 members, a committee of 5 is to be chosen. (a) How many committees are possible? (b) How many if a specific member, Alice, must serve as one of the five?

Step 1 — (a) Order does not matter. Use $C(12,5)$ :

C(12,5)=\frac{12!}{5!\,7!}=\frac{12\cdot11\cdot10\cdot9\cdot8}{5!}.

Step 2 — Evaluate. Numerator $=12\cdot11\cdot10\cdot9\cdot8=95{,}040$ ; denominator $5!=120$ .

C(12,5)=\frac{95{,}040}{120}=792.

Step 3 — (b) Fix Alice in, then choose the rest. With Alice guaranteed, choose the remaining 4 from the other 11:

C(11,4)=\frac{11\cdot10\cdot9\cdot8}{4!}=\frac{7920}{24}=330.

\boxed{\text{(a) } 792 \text{ committees}; \quad \text{(b) } 330 \text{ committees containing Alice}}

⚠️ Common mistake

Mixing up order. The single most common error is using a combination when order matters (or vice versa). Test phrases: "rank," "arrange," "schedule," "first/second/third," "password," "code" → usually permutation. "Select," "choose," "committee," "subset," "team" → usually combination. When in doubt, ask: if I swap two chosen items, do I get a different outcome? If yes, order matters.

Forgetting $0!=1$ . This convention is not arbitrary — it makes $C(n,n)=\frac{n!}{n!\,0!}=1$ (there is exactly one way to choose everything) and $C(n,0)=1$ (one way to choose nothing) come out correctly.

Double counting in repetition problems. When repetition is allowed and order does not matter, you must use stars and bars [7], not $C(n,r)$ or $n^r$ .

CounterexampleWhy

C(n,r) \ne P(n,r)

for

r\ge 2

Consider choosing 2 letters from $\{A, B, C\}$ .

Permutations $P(3,2)=6$ : $AB, BA, AC, CA, BC, CB$ — six ordered pairs.

Combinations $C(3,2)=3$ : $\{A,B\}, \{A,C\}, \{B,C\}$ — three unordered sets. The ratio is exactly $2! = 2$ , because each unordered pair $\{X,Y\}$ corresponds to the two orderings $XY$ and $YX$ . This concretely shows the division by $r!$ in [4]. Treating these as equal would, for instance, double the probability of every two-element event.

connection

Counting principles are the gateway to several neighbouring areas. They feed directly into Probability, where probabilities of equally likely outcomes are ratios of counts. The combination $\binom{n}{r}$ is the coefficient in the Binomial Theorem, linking counting to algebra: $(a+b)^n=\sum_{r=0}^n\binom{n}{r}a^{n-r}b^r$ . The recursive structure of $\binom{n}{r}$ generates Pascal's Triangle, whose patterns reveal Fibonacci numbers, powers of 2, and the hockey-stick identity. More advanced counting uses the Inclusion-Exclusion Principle to handle overlapping cases, and the multinomial coefficient [6] generalizes to the Multinomial Theorem. The whole subject is the elementary face of Combinatorics.

🔬 Where this appears

⏳ History

- c. 300 BCE – 200 CE (India): The Bhagavati Sutra and later writers compute combinations; the prosodist Pingala studies binary-like arrangements of long and short syllables, implicitly tabulating binomial coefficients.

- c. 850 CE: The Jain mathematician Mahāvīra gives an explicit rule equivalent to

C(n,r)

in his Gaṇita-sāra-saṅgraha.

- c. 1150: Bhāskara II (Līlāvatī) presents combinatorial formulas, including arrangements with repeated digits.

- 11th–13th centuries (China): Jia Xian and later Yang Hui display the arithmetic triangle (now "Yang Hui's triangle") for binomial expansion.

- c. 1320 (Persia): Al-Karaji and successors describe the triangle and the binomial expansion algebraically.

- 1654: Blaise Pascal and Pierre de Fermat exchange letters on the "problem of points," founding probability and formalizing combinatorial counting.

- 1665: Pascal's Traité du triangle arithmétique is published posthumously, systematizing binomial coefficients.

- 1666: Gottfried Wilhelm Leibniz writes Dissertatio de Arte Combinatoria, an early treatise treating combinatorics as a subject in its own right.

- 1713: Jacob Bernoulli's Ars Conjectandi consolidates permutations, combinations, and their use in probability, cementing the modern terminology.

open-problem

Elementary counting formulas are exact, but counting efficiently in complex settings remains deep. Enumerative combinatorics seeks closed forms or generating functions for counts that resist simple formulas — for example, the number of distinct ways to triangulate a polygon (the Catalan numbers) or to partition an integer (the partition function $p(n)$ , which has no simple closed form). In computational complexity, the problem of counting the number of solutions to a Boolean formula (the class #P) is believed to be strictly harder than merely deciding whether a solution exists, even when the decision problem is easy. Thus while $C(n,r)$ is computed in moments, the general question "how many configurations satisfy these constraints?" can be intractable — a frontier connecting combinatorics, algebra, and theoretical computer science.

Counting Principles — Permutations and Combinations

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also