Folioby Interconnected
Log InSign Up

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.

FO
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 (rn​). 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∩B=∅), then
∣A∪B∣=∣A∣+∣B∣.
More generally, if A1​,A2​,…,Ak​ are pairwise disjoint, then
∣A1​∪A2​∪⋯∪Ak​∣=∣A1​∣+∣A2​∣+⋯+∣Ak​∣.
Remark 4.
In the language of set theory, the addition principle is a statement about the disjoint union (coproduct). When A∩B=∅, we write A∪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 productA×B={(a,b)∣a∈A,b∈B} satisfies
∣A×B∣=∣A∣⋅∣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∣⋅∣B∣.
Example 8 (Passwords).
A password consisting of two uppercase English letters followed by three decimal digits can be formed in 262×103=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)⋯(n−r+1)=(n−r)!n!​.

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 (rn​) and equals
(rn​)=r!P(n,r)​=r!(n−r)!n!​.
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 groupSr​.

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≥m) is
S(n,m)=k=0∑m​(−1)k(km​)(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,…,N} to {1,…,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 (rn​) and ask why this single number appears in so many seemingly unrelated contexts.

CombinatoricsMathematicsBetween the Lines
FO
Folio Official

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

1 followers·107 articles
Combinatorics — Between the LinesPart 1 of 8
No previous article
Next
The many faces of the binomial coefficient: why nCr is so ubiquitous

Share your expertise with the world

Write articles with LaTeX support, build your audience, and earn from your knowledge.

Start Writing — It's Free

More from Folio Official

Folio Official·March 1, 2026

Recurrences and generating functions: what happens when you turn a sequence into a function

A generating function is the "business card" of a sequence. Multiplication becomes convolution, and recurrences become algebraic equations. We derive the closed form for the Fibonacci numbers (Binet's formula) as a showcase of the method.

CombinatoricsMathematicsBetween the Lines
Folio Official·March 1, 2026

Combinatorics meets dynamic programming: when counting becomes computation

Dynamic programming is bottom-up evaluation of a recurrence; a generating function is its analytic closed form. We draw the correspondence between the knapsack DP and generating function multiplication, discuss convolution and FFT, and survey the connections across the entire series.

CombinatoricsMathematicsBetween the Lines
Folio Official·March 1, 2026

Inclusion--exclusion: why the alternating signs work

The inclusion--exclusion principle corrects for overcounting by alternately adding and subtracting intersection sizes. We prove the general formula using indicator functions, apply it to count derangements, and trace the thread forward to the Mobius inversion formula on partially ordered sets.

CombinatoricsMathematicsBetween the Lines
Folio Official·March 1, 2026

Counting under symmetry: Burnside's lemma and Polya's enumeration theorem

When objects related by rotation or reflection are considered identical -- as with necklaces -- naive counting fails. Using the language of group actions, Burnside's lemma reduces the problem to a clean formula: the number of distinct objects equals the average number of fixed points across the group.

CombinatoricsMathematicsBetween the Lines