Fundamentals of Counting: The Addition Principle, Multiplication Principle, Permutations, and Combinations

Starting from the addition and multiplication principles, we define and prove the formulas for permutations P(n,r), combinations C(n,r), permutations with repetition, and combinations with repetition H(n,r). We conclude with the enumeration of injections and surjections.

Folio Official

March 1, 2026

1 The Addition and Multiplication Principles

Definition 1 (Addition principle).

Let

A_{1}, A_{2}, \dots, A_{k}

be finite sets that are pairwise disjoint (

A_{i} \cap A_{j} = \emptyset

for

i \neq = j

). Then

∣ A_{1} ⊔ A_{2} ⊔ \dots ⊔ A_{k} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{k} ∣.

This is called the addition principle (rule of sum).

Definition 2 (Multiplication principle).

For finite sets

A_{1}, A_{2}, \dots, A_{k}

∣ A_{1} \times A_{2} \times \dots \times A_{k} ∣ = ∣ A_{1} ∣ \cdot ∣ A_{2} ∣ \dots ∣ A_{k} ∣.

This is called the multiplication principle (rule of product).

Remark 3.

The addition principle concerns the cardinality of a disjoint union, while the multiplication principle concerns the cardinality of a Cartesian product. The vast majority of counting arguments in combinatorics reduce to repeated applications of these two principles.

2 Permutations

Definition 4 (Permutation).

The number of ways to choose

r

elements from a set of

n

distinct elements and arrange them in a row is called the number of permutations, denoted

P (n, r)

Theorem 5.

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

Proof.

By the multiplication principle: there are

n

choices for the first position,

n - 1

for the second, and so on, down to

n - r + 1

choices for the

r

-th position. Hence

P (n, r) = n (n - 1) \dots (n - r + 1)

. □

Definition 6 (Permutation with repetition).

The number of ways to choose

r

elements from

n

types with repetition allowed and arrange them in a row is

n^{r}

3 Combinations

Definition 7 (Combination).

The number of ways to choose

r

elements from a set of

n

distinct elements without regard to order is called the number of combinations, denoted

(r n)

C (n, r)

Theorem 8.

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

Proof.

The number of ways to choose

r

elements and then arrange them is

P (n, r)

. Since the same set of

r

elements corresponds to

r!

different arrangements, we have

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

. □

4 Combinations with Repetition

Definition 9 (Combination with repetition).

The number of ways to choose

r

elements from

n

types, with repetition allowed and without regard to order, is called the number of combinations with repetition, denoted

H (n, r)

Theorem 10.

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

Proof.

Label the

n

types

x_{1}, x_{2}, \dots, x_{n}

, and let

a_{i}

denote the number of times

x_{i}

is chosen. The problem amounts to counting the number of nonneg\/ative integer solutions to

a_{1} + a_{2} + \dots + a_{n} = r

. This is equivalent to the classical "stars and bars" problem: arrange

r

stars and

n - 1

bars in a row, where the bars serve as dividers. The total number of positions is

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

, and we must choose

n - 1

of them for the bars, giving

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

. □

5 Counting Injections and Surjections

Theorem 11 (Number of injections).

Let

∣ A ∣ = r

and

∣ B ∣ = n

with

r \leq n

. The number of injections from

A

B

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

Proof.

An injection

f : A \to B

assigns distinct elements of

B

to the elements of

A

. By the multiplication principle, this can be done in

P (n, r)

ways. □

Theorem 12 (Number of surjections).

Let

∣ A ∣ = n

and

∣ B ∣ = k

with

n \geq k

. The number of surjections from

A

onto

B

j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n} .

Proof.

We use the inclusion–exclusion principle. Write

B = {b_{1}, \dots, b_{k}}

and define

S_{i} = {f : A \to B ∣ b_{i} \in / Im (f)}

. The set of non-surjective maps is

S_{1} \cup \dots \cup S_{k}

. Since

∣ S_{i_{1}} \cap \dots \cap S_{i_{j}} ∣ = (k - j)^{n}

, inclusion–exclusion gives the number of surjections as

k^{n} - ∣ S_{1} \cup \dots \cup S_{k} ∣ = \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}

. □

Example 13.

When

A = {1, 2, 3, 4}

and

B = {a, b}

, the number of surjections is

\sum_{j = 0}^{2} (- 1)^{j} (j 2) (2 - j)^{4} = 2^{4} - 2 \cdot 1^{4} + 0 = 14

Combinatorics Discrete Mathematics Textbook Counting Permutations Combinations

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Fundamentals of Counting: The Addition Principle, Multiplication Principle, Permutations, and Combinations

Folio Official

March 1, 2026

1 The Addition and Multiplication Principles

Definition 1 (Addition principle).

Let

A_{1}, A_{2}, \dots, A_{k}

be finite sets that are pairwise disjoint (

A_{i} \cap A_{j} = \emptyset

for

i \neq = j

). Then

∣ A_{1} ⊔ A_{2} ⊔ \dots ⊔ A_{k} ∣ = ∣ A_{1} ∣ + ∣ A_{2} ∣ + \dots + ∣ A_{k} ∣.

This is called the addition principle (rule of sum).

Definition 2 (Multiplication principle).

For finite sets

A_{1}, A_{2}, \dots, A_{k}

∣ A_{1} \times A_{2} \times \dots \times A_{k} ∣ = ∣ A_{1} ∣ \cdot ∣ A_{2} ∣ \dots ∣ A_{k} ∣.

This is called the multiplication principle (rule of product).

Remark 3.

2 Permutations

Definition 4 (Permutation).

The number of ways to choose

r

elements from a set of

n

distinct elements and arrange them in a row is called the number of permutations, denoted

P (n, r)

Theorem 5.

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

Proof.

By the multiplication principle: there are

n

choices for the first position,

n - 1

for the second, and so on, down to

n - r + 1

choices for the

r

-th position. Hence

P (n, r) = n (n - 1) \dots (n - r + 1)

. □

Definition 6 (Permutation with repetition).

The number of ways to choose

r

elements from

n

types with repetition allowed and arrange them in a row is

n^{r}

3 Combinations

Definition 7 (Combination).

The number of ways to choose

r

elements from a set of

n

distinct elements without regard to order is called the number of combinations, denoted

(r n)

C (n, r)

Theorem 8.

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

Proof.

The number of ways to choose

r

elements and then arrange them is

P (n, r)

. Since the same set of

r

elements corresponds to

r!

different arrangements, we have

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

. □

4 Combinations with Repetition

Definition 9 (Combination with repetition).

The number of ways to choose

r

elements from

n

types, with repetition allowed and without regard to order, is called the number of combinations with repetition, denoted

H (n, r)

Theorem 10.

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

Proof.

Label the

n

types

x_{1}, x_{2}, \dots, x_{n}

, and let

a_{i}

denote the number of times

x_{i}

is chosen. The problem amounts to counting the number of nonneg\/ative integer solutions to

a_{1} + a_{2} + \dots + a_{n} = r

. This is equivalent to the classical "stars and bars" problem: arrange

r

stars and

n - 1

bars in a row, where the bars serve as dividers. The total number of positions is

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

, and we must choose

n - 1

of them for the bars, giving

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

. □

5 Counting Injections and Surjections

Theorem 11 (Number of injections).

Let

∣ A ∣ = r

and

∣ B ∣ = n

with

r \leq n

. The number of injections from

A

B

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

Proof.

An injection

f : A \to B

assigns distinct elements of

B

to the elements of

A

. By the multiplication principle, this can be done in

P (n, r)

ways. □

Theorem 12 (Number of surjections).

Let

∣ A ∣ = n

and

∣ B ∣ = k

with

n \geq k

. The number of surjections from

A

onto

B

j = 0 \sum k (- 1)^{j} (j k) (k - j)^{n} .

Proof.

We use the inclusion–exclusion principle. Write

B = {b_{1}, \dots, b_{k}}

and define

S_{i} = {f : A \to B ∣ b_{i} \in / Im (f)}

. The set of non-surjective maps is

S_{1} \cup \dots \cup S_{k}

. Since

∣ S_{i_{1}} \cap \dots \cap S_{i_{j}} ∣ = (k - j)^{n}

, inclusion–exclusion gives the number of surjections as

k^{n} - ∣ S_{1} \cup \dots \cup S_{k} ∣ = \sum_{j = 0}^{k} (- 1)^{j} (j k) (k - j)^{n}

. □

Example 13.

When

A = {1, 2, 3, 4}

and

B = {a, b}

, the number of surjections is

\sum_{j = 0}^{2} (- 1)^{j} (j 2) (2 - j)^{4} = 2^{4} - 2 \cdot 1^{4} + 0 = 14

Combinatorics Discrete Mathematics Textbook Counting Permutations Combinations

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 followers·107 articles

Fundamentals of Counting: The Addition Principle, Multiplication Principle, Permutations, and Combinations

1 The Addition and Multiplication Principles

2 Permutations

3 Combinations

4 Combinations with Repetition

5 Counting Injections and Surjections

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry

Fundamentals of Counting: The Addition Principle, Multiplication Principle, Permutations, and Combinations

1 The Addition and Multiplication Principles

2 Permutations

3 Combinations

4 Combinations with Repetition

5 Counting Injections and Surjections

Share your expertise with the world

More from Folio Official

Recurrence Relations and Counting: Solving Linear Recurrences

The Inclusion--Exclusion Principle: Counting by Alternating Sums

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry