What does it mean to count? Addition, multiplication, and surjections

Counting is the act of measuring the cardinality of a set. Whether you add or multiply depends on whether your set decomposes as a disjoint union or a Cartesian product. From this single viewpoint, permutations, combinations, and the surjection formula all emerge naturally.

Folio Official

March 1, 2026

Open a combinatorics textbook and you will be greeted, almost immediately, by the formulas for permutations $P (n, r)$ and combinations $(r n)$ . But have you ever stopped to ask a more primitive question: what does it actually mean to count something? This article takes the position that counting is fundamentally an operation on sets, and from that single insight the addition principle, the multiplication principle, permutations, combinations, and the surjection formula all follow in a unified way.

1 Counting is cardinality

Definition 1 (The essence of counting).

To count a finite set

S

is to determine

∣ S ∣

, the cardinality (number of elements) of

S

This may seem tautological, but it is a perspective of genuine importance. The question "how many outcomes are there when rolling a die?" becomes a precise mathematical statement once we rephrase it as "what is $∣ {1, 2, 3, 4, 5, 6} ∣$ ?" Until the set is identified, there is nothing rigorous to compute.

Remark 2.

The first step in any counting problem is to define exactly which set you are counting. Vague formulations – "how many ways can we arrange..." without specifying the universe – are the primary source of double-counting and missed cases. If you cannot name the set, you cannot count it correctly.

2 The addition principle: disjoint union means addition

Theorem 3 (Addition principle).

If finite sets

A

and

B

are disjoint (

A \cap B = \emptyset

), then

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

More generally, if

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

are pairwise disjoint, then

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

Remark 4.

In the language of set theory, the addition principle is a statement about the disjoint union (coproduct). When

A \cap B = \emptyset

, we write

A \cup B = A ⊔ B

, and the principle becomes

∣ A ⊔ B ∣ = ∣ A ∣ + ∣ B ∣

. The question "should I add?" is therefore equivalent to "can I partition my set into disjoint pieces?"

Example 5 (Case analysis).

From a standard deck of 52 cards, the number of cards that are either hearts or spades is

13 + 13 = 26

, because the set of hearts and the set of spades are disjoint.

3 The multiplication principle: Cartesian product means multiplication

Theorem 6 (Multiplication principle).

For finite sets

A

and

B

, the Cartesian product

A \times B = {(a, b) ∣ a \in A, b \in B}

satisfies

∣ A \times B ∣ = ∣ A ∣ \cdot ∣ B ∣.

Remark 7.

The multiplication principle applies whenever you make a sequence of independent choices: choose one element from

A

, then one from

B

. The key requirement is that the set of available choices in

B

does not depend on what was chosen from

A

. When that independence holds, the total number of outcomes is the product

∣ A ∣ \cdot ∣ B ∣

Example 8 (Passwords).

A password consisting of two uppercase English letters followed by three decimal digits can be formed in

2 6^{2} \times 1 0^{3} = 676, 000

ways. Each character is chosen independently, so the multiplication principle applies directly.

4 Permutations and combinations: the multiplication principle in action

Definition 9 (Permutation).

The number of ways to choose

r

objects from

n

distinct objects and arrange them in order is denoted

P (n, r)

and equals

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

This is a direct application of the multiplication principle. The first position can be filled in $n$ ways, the second in $n - 1$ ways (since one object has been used), and so on down to $n - r + 1$ for the $r$ -th position.

Definition 10 (Combination).

The number of ways to choose

r

objects from

n

distinct objects without regard to order is denoted

(r n)

and equals

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

Remark 11.

The division by

r!

has a clean explanation. A permutation selects

r

objects and arranges them; every subset of size

r

is thereby counted once for each of its

r!

possible orderings. If we care only about which objects are chosen, not how they are arranged, we divide by

r!

to collapse each group of

r!

orderings into a single subset. In the language of algebra, we are passing to the quotient by the action of the symmetric group $S_{r}$ .

5 Counting surjections: a preview of inclusion–exclusion

Definition 12 (Number of surjections).

The number of surjections (onto functions) from an

n

-element set

X

to an

m

-element set

Y

(where

n \geq m

) is

S (n, m) = k = 0 \sum m (- 1)^{k} (k m) (m - k)^{n} .

Remark 13.

Why the alternating signs? This formula is a prototypical application of the inclusion–exclusion principle, which we will examine in detail in the third article of this series. The intuition is that we must correct for the overcounting that arises when at least one element of

Y

is missed by the function. Each correction introduces an error of its own, which the next term corrects, and so on.

Example 14 (A concrete counting problem).

"In how many ways can

N

balls be placed into

M

boxes so that every box is non-empty?" This is precisely the number of surjections from

{1, \dots, N}

{1, \dots, M}

. Framing the problem set-theoretically strips away all ambiguity and brings the surjection formula directly into play.

6 Takeaway

Counting is the act of determining the cardinality of a set.
The addition principle corresponds to disjoint union.
The multiplication principle corresponds to Cartesian product (independent choices).
Permutations and combinations are natural consequences of the multiplication principle.
The surjection formula is a gateway to inclusion–exclusion.

In the next article, we turn to the binomial coefficient $(r n)$ and ask why this single number appears in so many seemingly unrelated contexts.

Combinatorics Mathematics Between the Lines

Folio Official

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

1 フォロワー·105 記事

What does it mean to count? Addition, multiplication, and surjections

1 Counting is cardinality

2 The addition principle: disjoint union means addition

3 The multiplication principle: Cartesian product means multiplication

4 Permutations and combinations: the multiplication principle in action

5 Counting surjections: a preview of inclusion–exclusion

6 Takeaway

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

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