Counting Principles — Permutations and Combinations

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.

A permutation is an arrangement of objects in which order matters, while a combination is a selection of objects in which order does not matter. These ideas rest on two foundational counting rules — the addition principle (for mutually exclusive choices) and the multiplication principle (for sequential choices) — which together let us count enormous sets without enumeration. The subject matters because counting is the silent engine behind probability: to find a probability you usually must count favorable outcomes and total outcomes. A surprising fact is that the same number $C (n, r)$ that counts subsets also appears as the coefficients in $(a + b)^{n}$ and as the entries of Pascal's triangle — a deep unity linking algebra, geometry, and counting.

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.

Formal Statement

Fundamental 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

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

⟳build outcomes as a tree — each stage multiplies the number of branches.

Factorial

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

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

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

Permutations

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

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

⟳

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 \leq r \leq n$ .

Combinations

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

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

⟳each unordered set of

r

objects can be ordered in

r!

ways, so divide the permutation count by

r!

Symbols: as above, with $0 \leq r \leq n$ . The quantity $(r n)$ is called a binomial coefficient.

Permutations with Repetition and Multiset Permutations

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

N_{rep} = n^{r}

⟳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} + \dots + n_{k} = n$ ), the number of distinct arrangements is the multinomial coefficient

\frac{n !}{n _{1} ! n _{2} ! \dots n _{k} !}

⟳start from

n!

arrangements, then divide by

n_{i}!

for each block of identical items, since permuting identical items changes nothing.

Combinations 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

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

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

Why It Holds / Derivation

Deriving 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) \dots (n - r + 1) .

Step 3. Multiply and divide by

(n - r)!

to compactify:

P (n, r) = \frac{n ( n - 1 ) \dots ( 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].

■

Pascal's Rule

We show $(r n) = (r - 1 n - 1) + (r n - 1)$ .

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:

(r - 1 n - 1)

ways. Step 4. Subsets excluding

x

are formed by choosing all

r

members from the other

n - 1

objects:

(r n - 1)

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

■

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.

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

Decision flow: order and repetition select the formula

<svg viewBox="0 0 640 400" xmlns="http://www.w3.org/2000/svg">
<rect width="640" height="400" fill="#0a0e17"/>
<rect x="240" y="20" width="160" height="44" rx="6" fill="none" stroke="#94a3b8"/>
<text x="320" y="47" fill="#e2e8f0" font-size="14" text-anchor="middle">Does ORDER matter?</text>

<line x1="290" y1="64" x2="150" y2="120" stroke="#94a3b8"/>
<line x1="350" y1="64" x2="490" y2="120" stroke="#94a3b8"/>
<text x="200" y="98" fill="#d4a853" font-size="13">YES</text>
<text x="430" y="98" fill="#d4a853" font-size="13">NO</text>

<rect x="60" y="120" width="180" height="44" rx="6" fill="none" stroke="#94a3b8"/>
<text x="150" y="147" fill="#e2e8f0" font-size="13" text-anchor="middle">Repetition allowed?</text>
<rect x="400" y="120" width="180" height="44" rx="6" fill="none" stroke="#94a3b8"/>
<text x="490" y="147" fill="#e2e8f0" font-size="13" text-anchor="middle">Repetition allowed?</text>

<line x1="110" y1="164" x2="80" y2="220" stroke="#94a3b8"/>
<line x1="190" y1="164" x2="220" y2="220" stroke="#94a3b8"/>
<line x1="450" y1="164" x2="420" y2="220" stroke="#94a3b8"/>
<line x1="530" y1="164" x2="560" y2="220" stroke="#94a3b8"/>

<rect x="20" y="220" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="80" y="242" fill="#e2e8f0" font-size="12" text-anchor="middle">YES rep</text>
<text x="80" y="260" fill="#d4a853" font-size="14" text-anchor="middle">n^r</text>

<rect x="160" y="220" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="220" y="242" fill="#e2e8f0" font-size="12" text-anchor="middle">NO rep</text>
<text x="220" y="260" fill="#d4a853" font-size="14" text-anchor="middle">P(n,r)=n!/(n-r)!</text>

<rect x="360" y="220" width="130" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="425" y="242" fill="#e2e8f0" font-size="12" text-anchor="middle">YES rep</text>
<text x="425" y="260" fill="#d4a853" font-size="13" text-anchor="middle">C(n+r-1, r)</text>

<rect x="510" y="220" width="120" height="50" rx="6" fill="none" stroke="#d4a853"/>
<text x="570" y="242" fill="#e2e8f0" font-size="12" text-anchor="middle">NO rep</text>
<text x="570" y="260" fill="#d4a853" font-size="13" text-anchor="middle">C(n,r)</text>

<text x="150" y="200" fill="#94a3b8" font-size="12" text-anchor="middle">PERMUTATIONS</text>
<text x="490" y="200" fill="#94a3b8" font-size="12" text-anchor="middle">COMBINATIONS</text>

<text x="320" y="340" fill="#e2e8f0" font-size="13" text-anchor="middle">Two questions fix the formula:</text>
<text x="320" y="362" fill="#94a3b8" font-size="12" text-anchor="middle">order? (left=yes) and repetition? (left of each pair=yes)</text>
</svg>

Worked Examples

Forming 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 \cdot 25 \cdot 24 \cdot 23.

Step 2 — Evaluate.

26 \cdot 25 = 650

;

650 \cdot 24 = 15, 600

;

15, 600 \cdot 23 = 358, 800

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

2 6^{4} = 456, 976.

P (26, 4) = 358, 800 passwords; with repetition 456, 976 passwords

Choosing 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 \cdot 11 \cdot 10 \cdot 9 \cdot 8}{5 !} .

Step 2 — Evaluate. Numerator

= 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 = 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 \cdot 10 \cdot 9 \cdot 8}{4 !} = \frac{7920}{24} = 330.

(a) 792 committees; (b) 330 committees containing Alice

Common Misconceptions

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)

n^{r}

Why $C(n,r) \ne P(n,r)$ for $r\ge 2$

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

Permutations

P (3, 2) = 6

A B, B A, A C, C A, B C, C B

— 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 $X Y$ and $Y X$ . This concretely shows the division by $r!$ in [4]. Treating these as equal would, for instance, double the probability of every two-element event.

Connections

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 $(r n)$ is the coefficient in the Binomial Theorem, linking counting to algebra: $(a + b)^{n} = \sum_{r = 0}^{n} (r n) a^{n - r} b^{r}$ . The recursive structure of $(r n)$ 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.

Real-World Applications

Lotteries. The odds of winning a 6-from-49 lottery are $1/ C (49, 6) = 1/13, 983, 816$ — a direct combination count, since the order of drawn numbers is irrelevant.
Cryptography & passwords. Estimating keyspace size uses $n^{r}$ (with repetition) to gauge how hard a brute-force attack is; a 12-character password from 95 printable ASCII symbols gives $9 5^{12} \approx 5.4 \times 1 0^{23}$ possibilities.
Genetics. Counting distinct gametes and genotype combinations (e.g., the number of unique allele combinations) relies on multiplication and combination principles.
Sports scheduling. A round-robin tournament among $n$ teams requires $C (n, 2)$ games, since each unordered pair plays once.
Network design. The number of possible direct links among $n$ nodes is $C (n, 2)$ ; this governs cabling and routing complexity.
Quality control & sampling. Statistical sampling without replacement uses $C (n, r)$ to count possible samples, underpinning the hypergeometric distribution.
Card games (poker). The number of 5-card hands is $C (52, 5) = 2, 598, 960$ ; counting flushes, straights, and full houses is pure combination arithmetic.

Historical Development

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.

Subtleties & Limits

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.