Counting Surjections

How many ways can you distribute nn distinct letters into kk distinct mailboxes? Every mailbox must receive at least one letter. This is the question of counting surjections. Surjections are functions from an nn-element set onto a kk-element set. It is one of the cleanest nontrivial applications of the Principle of Inclusion-Exclusion. Naively counting functions is trivial (knk^n of them). But insisting that every element of the codomain be hit introduces dependencies. These dependencies make direct counting hard. Inclusion-exclusion resolves this by systematically correcting for the functions that miss one or more codomain elements. This problem matters far beyond its cute mailbox phrasing. Surjection counts are the combinatorial engine behind the Stirling Numbers of the Second Kind. These numbers count set partitions. Surjection counts also lie behind the general classification of counting problems known as the Twelvefold Way. This organizes every basic way of counting functions between finite sets. It does so by whether domain/codomain elements are distinguishable. It also depends on whether the function must be injective, surjective, or arbitrary. Surjection counts also appear whenever one counts multi-set orderings, exponential generating functions, or the number of ways a group of people can be split into labeled nonempty teams. The big picture is this: surjections onto a kk-set are exactly the functions from nn elements to kk elements. They avoid missing any of the kk targets. And "avoiding a bad event for each target" is precisely what inclusion-exclusion is built to compute. We phrase "target ii is missed" as a property. We count functions violating any chosen subset of these properties. This is easy, since they land in a smaller codomain. We then alternately add and subtract over all subsets. This article gives the precise definition of a surjection. It builds intuition through a small worked case. It states and completely proves the closed-form counting theorem. It works two nontrivial numerical examples. It shows exactly what breaks if a hypothesis of the theorem is dropped. It closes by connecting the surjection count formula to Stirling numbers. It also connects to real applications in combinatorics, probability, and computer science.

Key takeaways
  • A surjection (onto function) f:[n]→[k]f : [n] \to [k] hits every element of the codomain at least once.
  • Counting surjections directly is hard because "every element is hit" is a global condition coupling all kk targets.
  • Inclusion-Exclusion turns this into a sum over subsets of "missed targets," each easy to count.
  • The result is the explicit alternating sum Surj(n,k)=∑j=0k(−1)j(kj)(k−j)n\mathrm{Surj}(n,k)=\sum_{j=0}^{k}(-1)^j\binom{k}{j}(k-j)^n.
  • Dividing by k!k! gives S(n,k)S(n,k), the Stirling Numbers of the Second Kind, counting partitions into kk unlabeled blocks.
  • Key idea: count all functions, then alternately subtract and add back functions missing each possible subset of codomain elements.

Where this lives today

The surjection-counting formula and its Stirling-number cousin appear throughout discrete mathematics and its applications. In enumerative combinatorics, they are the seed computation for the Twelvefold Way, the table organizing all twelve basic ways of counting functions between finite sets by distinguishability and injectivity/surjectivity constraints. In probability and statistics, the same alternating sum computes the probability that a random function (e.g., a hash function, or a random assignment of balls to bins) covers every bin at least once — this is the classical coupon collector and balls-into-bins covering problem, central to the analysis of hashing schemes and load balancing in computer science. In algebraic combinatorics, surjection counts are the coefficients arising from the exponential generating function identity

∑n≥0Surj(n,k) xnn!  =  (ex−1)k,\sum_{n \ge 0} \mathrm{Surj}(n,k)\,\frac{x^n}{n!} \;=\; (e^x - 1)^k,

a fact provable independently via the exponential formula for labeled structures, and this connects surjection counting to the broader machinery of generating functions used throughout combinatorial species theory. In cryptography and coding theory, surjectivity of key-derivation or scrambling functions onto their output space is a design desideratum, and counting/estimating the number of such surjective maps informs security-margin arguments. In statistical physics, the same alternating-sum technique (inclusion-exclusion over "missed states") appears in computing partition functions and occupation-number statistics for distinguishable particles filling distinguishable states with no state left empty.

Ask the tutor: How does the surjection-counting formula generalize when we require each of the kk target "boxes" to receive at least mm elements instead of just at least 11?

DefinitionSurjection and the surjection count

Let n,kn,k be positive integers, let [n]={1,2,…,n}[n]=\{1,2,\dots,n\}, and let [k]={1,2,…,k}[k]=\{1,2,\dots,k\}. A function f:[n]→[k]f:[n]\to[k] is a surjection (or is onto) if for every y∈[k]y\in[k] there exists x∈[n]x\in[n] with f(x)=yf(x)=y. Equivalently, f([n])=[k]f([n])=[k], i.e. the image of ff is the entire codomain. The surjection number Surj(n,k)\mathrm{Surj}(n,k) is the number of surjections from [n][n] to [k][k]:

Surj(n,k)  =  #{ f:[n]→[k]  ∣  f is surjective }.\mathrm{Surj}(n,k) \;=\; \#\{\, f:[n]\to[k] \;\mid\; f \text{ is surjective} \,\}.

By convention Surj(0,0)=1\mathrm{Surj}(0,0)=1 (the empty function is a surjection between empty sets) and Surj(n,0)=0\mathrm{Surj}(n,0)=0 for n≥1n\ge 1, and Surj(0,k)=0\mathrm{Surj}(0,k)=0 for k≥1k\ge 1.

Intuition

Think of [n][n] as nn labeled balls and [k][k] as kk labeled boxes. A function [n]→[k][n]\to[k] is any assignment of each ball to a box, with no restriction — there are knk^n such assignments since each of the nn balls independently picks one of kk boxes. A surjection is an assignment in which no box is left empty. The difficulty is that "box 11 is nonempty" and "box 22 is nonempty" are not independent events, and there is no simple product rule for "all boxes nonempty" the way there is for "all balls placed somewhere." Instead, define for each i∈[k]i\in[k] the "bad" property AiA_i: the property that a function ff misses target ii, meaning i∉f([n])i \notin f([n]). A function is a surjection exactly when it has none of the bad properties A1,…,AkA_1,\dots,A_k. Inclusion-exclusion computes the size of the complement of A1∪⋯∪AkA_1\cup\cdots\cup A_k inside the set of all functions. The key computational fact is that the "bad" events are easy to handle in combination: the number of functions avoiding a fixed set S⊆[k]S\subseteq[k] of targets entirely (i.e. landing inside [k]∖S[k]\setminus S) is simply (k−∣S∣)n(k-|S|)^n, because each ball now has only k−∣S∣k-|S| legal boxes. Inclusion-exclusion assembles the surjection count from these easy quantities.

Figure
Small case n=3n=3 balls into k=2k=2 boxes: all 23=82^3=8 functions, with the 2 non-surjective ones (both balls in the same box) marked
Functions [3] → {A,B}: 2³ = 8 total Assignment (f(1),f(2),f(3)) AAA AAB ABA BAA ABB BAB BBA BBB Circled = misses a box (not onto): AAA misses B, BBB misses A. Onto functions: the other 6 (each box gets ≥1 ball). Formula check: Surj(3,2) = Σ(-1)^j C(2,j)(2-j)^3 = 2^3 − 2·1^3 = 8 − 2 = 6 ✓

Central theorem

TheoremSurjection Counting Formula

Let nn and kk be positive integers. The number of surjections from an nn-element set onto a kk-element set is

Surj(n,k)  =  ∑j=0k(−1)j(kj)(k−j)n.\mathrm{Surj}(n,k) \;=\; \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n .
Proof

We use the Principle of Inclusion-Exclusion applied to the set F\mathcal F of all functions f:[n]→[k]f:[n]\to[k], ∣F∣=kn|\mathcal F| = k^n.

Setup. For each i∈[k]i \in [k], define

Ai  =  { f∈F  :  i∉f([n]) },A_i \;=\; \{\, f \in \mathcal F \;:\; i \notin f([n]) \,\},

the set of functions that fail to hit target ii. A function ff is a surjection if and only if it lies in none of A1,…,AkA_1,\dots,A_k; equivalently,

{surjections}  =  F∖(A1∪A2∪⋯∪Ak).\{\text{surjections}\} \;=\; \mathcal F \setminus (A_1 \cup A_2 \cup \cdots \cup A_k).

Hence

Surj(n,k)=∣F∣−∣A1∪⋯∪Ak∣.\mathrm{Surj}(n,k) = |\mathcal F| - |A_1\cup\cdots\cup A_k|.

Computing intersections. Fix a nonempty subset S⊆[k]S \subseteq [k] with ∣S∣=j|S| = j. We claim

∣⋂i∈SAi∣=(k−j)n.\Big|\bigcap_{i \in S} A_i\Big| = (k-j)^n.

Indeed, f∈⋂i∈SAif \in \bigcap_{i\in S} A_i means ff misses every target in SS simultaneously, i.e. f([n])⊆[k]∖Sf([n]) \subseteq [k]\setminus S. Since ∣[k]∖S∣=k−j|[k]\setminus S| = k - j, such an ff is precisely an arbitrary function [n]→[k]∖S[n] \to [k]\setminus S, and there are exactly (k−j)n(k-j)^n of these (each of the nn domain elements independently chooses one of the k−jk-j remaining targets). This proves the claim. Note the value depends only on j=∣S∣j = |S|, not on which particular targets are in SS — a symmetry that will let us collapse the inclusion-exclusion sum into a sum over jj rather than over all subsets.

Applying inclusion-exclusion. The Principle of Inclusion-Exclusion states that for any finite sets A1,…,AkA_1,\dots,A_k,

∣⋃i=1kAi∣  =  ∑∅≠S⊆[k](−1)∣S∣+1∣⋂i∈SAi∣.\Big|\bigcup_{i=1}^k A_i\Big| \;=\; \sum_{\emptyset \ne S \subseteq [k]} (-1)^{|S|+1} \Big|\bigcap_{i\in S} A_i\Big|.

Substituting ∣⋂i∈SAi∣=(k−∣S∣)n\left|\bigcap_{i \in S} A_i\right| = (k-|S|)^n and grouping subsets by their size j=∣S∣j = |S| — there are (kj)\binom{k}{j} subsets of size jj — gives

∣⋃i=1kAi∣  =  ∑j=1k(−1)j+1(kj)(k−j)n.\Big|\bigcup_{i=1}^k A_i\Big| \;=\; \sum_{j=1}^{k} (-1)^{j+1} \binom{k}{j} (k-j)^n.

Conclusion. Substituting into Surj(n,k)=kn−∣A1∪⋯∪Ak∣\mathrm{Surj}(n,k) = k^n - |A_1 \cup \cdots \cup A_k|:

Surj(n,k)=kn−∑j=1k(−1)j+1(kj)(k−j)n=kn+∑j=1k(−1)j(kj)(k−j)n.\mathrm{Surj}(n,k) = k^n - \sum_{j=1}^k (-1)^{j+1}\binom{k}{j}(k-j)^n = k^n + \sum_{j=1}^{k}(-1)^j \binom{k}{j}(k-j)^n.

The term j=0j=0 in the sum ∑j=0k(−1)j(kj)(k−j)n\sum_{j=0}^k(-1)^j\binom{k}{j}(k-j)^n equals (−1)0(k0)kn=kn(-1)^0\binom{k}{0}k^n = k^n, which matches the standalone knk^n term above exactly. Hence

Surj(n,k)=∑j=0k(−1)j(kj)(k−j)n,\mathrm{Surj}(n,k) = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n,

as claimed. ■\blacksquare

∎
LemmaRelation to Stirling numbers of the second kind

For all n≥k≥1n \ge k \ge 1,

S(n,k)  =  1k! Surj(n,k),S(n,k) \;=\; \frac{1}{k!}\,\mathrm{Surj}(n,k),

where S(n,k)S(n,k) denotes the number of ways to partition an nn-element set into exactly kk nonempty, unlabeled blocks (the Stirling Numbers of the Second Kind).

Proof

Fix a partition π\pi of [n][n] into kk nonempty unlabeled blocks B1,…,BkB_1,\dots,B_k. Assigning distinct labels from [k][k] to the blocks of π\pi turns it into a surjection f:[n]→[k]f:[n]\to[k] by setting f(x)=if(x) = i whenever x∈Bix \in B_i: every block is nonempty so every label is used, giving a surjection. There are exactly k!k! ways to label the kk blocks of π\pi (a bijection from blocks to [k][k]), and distinct labelings of the same partition give distinct surjections since the underlying fiber structure (and hence the induced partition) differs only when a different bijection is used, while conversely any two labelings of different partitions give different surjections since the fibers f−1(1),…,f−1(k)f^{-1}(1),\dots,f^{-1}(k) of a surjection always form an (ordered) partition of [n][n] into kk nonempty blocks. This exhibits a k!k!-to-11 correspondence: the map "surjection f↦f \mapsto partition of [n][n] into blocks f−1(1),…,f−1(k)f^{-1}(1),\dots,f^{-1}(k), unlabeled" sends exactly k!k! surjections (one for each relabeling) to each partition into kk nonempty blocks, and every such partition arises this way. Hence the surjections are partitioned into fibers of size k!k! indexed by the partitions counted by S(n,k)S(n,k), giving

Surj(n,k)=k!⋅S(n,k)⟺S(n,k)=Surj(n,k)k!.■\mathrm{Surj}(n,k) = k! \cdot S(n,k) \quad\Longleftrightarrow\quad S(n,k) = \frac{\mathrm{Surj}(n,k)}{k!}. \qquad \blacksquare
∎

Worked examples

Example 1: n=5n = 5 balls onto k=3k = 3 labeled boxes (asymmetric, nontrivial size). We compute Surj(5,3)=∑j=03(−1)j(3j)(3−j)5\mathrm{Surj}(5,3) = \sum_{j=0}^{3}(-1)^j \binom{3}{j}(3-j)^5.

j=0:(−1)0(30)(3)5=1⋅1⋅243=243j=1:(−1)1(31)(2)5=−1⋅3⋅32=−96j=2:(−1)2(32)(1)5=1⋅3⋅1=3j=3:(−1)3(33)(0)5=−1⋅1⋅0=0\begin{aligned} j=0:&\quad (-1)^0\binom{3}{0}(3)^5 = 1\cdot 1\cdot 243 = 243\\ j=1:&\quad (-1)^1\binom{3}{1}(2)^5 = -1\cdot 3\cdot 32 = -96\\ j=2:&\quad (-1)^2\binom{3}{2}(1)^5 = 1\cdot 3\cdot 1 = 3\\ j=3:&\quad (-1)^3\binom{3}{3}(0)^5 = -1\cdot 1\cdot 0 = 0 \end{aligned}

Summing: 243−96+3+0=150243 - 96 + 3 + 0 = 150. So Surj(5,3)=150\mathrm{Surj}(5,3) = 150. As a sanity check via the lemma, S(5,3)=150/3!=25S(5,3) = 150/3! = 25, which matches the standard tabulated value of the Stirling number S(5,3)=25S(5,3)=25. As a second sanity check, the total number of functions [5]→[3][5]\to[3] is 35=2433^5=243; the non-surjective ones (missing box 1, or box 2, or box 3) number 243−150=93243-150=93, and indeed 93=(31)25−(32)15=96−393 = \binom{3}{1}2^5 - \binom{3}{2}1^5 = 96-3 by inclusion-exclusion on the complement, consistent with the computation above.

Example 2: n=4n=4, k=4k=4 — surjections onto a same-size codomain are exactly bijections. Compute Surj(4,4)=∑j=04(−1)j(4j)(4−j)4\mathrm{Surj}(4,4) = \sum_{j=0}^4 (-1)^j\binom{4}{j}(4-j)^4:

j=0: (40)44=256j=1: −(41)34=−4⋅81=−324j=2: (42)24=6⋅16=96j=3: −(43)14=−4⋅1=−4j=4: (44)04=0\begin{aligned} j=0:&\ \binom{4}{0}4^4 = 256\\ j=1:&\ -\binom{4}{1}3^4 = -4\cdot 81 = -324\\ j=2:&\ \binom{4}{2}2^4 = 6\cdot 16 = 96\\ j=3:&\ -\binom{4}{3}1^4 = -4\cdot 1 = -4\\ j=4:&\ \binom{4}{4}0^4 = 0 \end{aligned}

Sum: 256−324+96−4+0=24256 - 324 + 96 - 4 + 0 = 24. This matches the independent fact that a surjection from an nn-set to an nn-set must also be injective (a surjective self-map of a finite set is automatically a bijection, since equal finite cardinalities of domain and image force injectivity by the pigeonhole principle), so Surj(n,n)=n!\mathrm{Surj}(n,n) = n!. Here 4!=244! = 24, confirming the alternating sum computation exactly.

CounterexampleDropping finiteness of the domain breaks the formula

The theorem's proof relies essentially on nn and kk being finite — in particular, on the fact that ∣F∣=kn|\mathcal F| = k^n is a finite number, and on the finite Principle of Inclusion-Exclusion, which is proved by induction on the (finite) number of sets A1,…,AkA_1,\dots,A_k. Consider dropping finiteness of the domain: let n=∣N∣n = |\mathbb{N}| (a countably infinite domain) and k=2k=2. The formula would formally suggest computing ∑j=02(−1)j(2j)(2−j)n\sum_{j=0}^2 (-1)^j \binom{2}{j}(2-j)^n with nn interpreted as a cardinal exponent, but (k−j)n(k-j)^n for infinite nn is now a cardinal-arithmetic expression, and 2ℵ0−2⋅1ℵ02^{\aleph_0} - 2\cdot 1^{\aleph_0} is not a meaningful subtraction in cardinal arithmetic — cardinal subtraction is not well-defined in general, since cardinal arithmetic has no additive inverses once we leave the finite realm. Concretely, there certainly do exist surjections N→{1,2}\mathbb N \to \{1,2\} (e.g. send evens to 11 and odds to 22), and in fact there are 2ℵ02^{\aleph_0} of them — but there is no way to recover this count by naively plugging n=ℵ0n=\aleph_0 into the alternating sum, because the derivation used ∣F∖(A1∪A2)∣=∣F∣−∣A1∪A2∣|\mathcal F\setminus (A_1\cup A_2)| = |\mathcal F| - |A_1 \cup A_2|, a subtraction that is only licensed when all quantities involved are finite (so that "−-" is ordinary integer subtraction, not ill-defined cardinal subtraction). This shows the finiteness hypothesis on nn (and kk) is not a technicality: without it, the subtraction step in the proof of inclusion-exclusion has no meaning, and the closed form simply fails to apply.

Scope, edge cases & common traps

SituationWhat happensWhy
n<kn < kSurj(n,k)=0\mathrm{Surj}(n,k) = 0Cannot hit kk distinct targets using fewer than kk domain elements (pigeonhole)
n=kn = kSurj(n,k)=n!=k!\mathrm{Surj}(n,k) = n! = k!Surjective self-map of a finite set is automatically bijective
n=0,k≥1n = 0, k \ge 1Surj(0,k)=0\mathrm{Surj}(0,k) = 0The empty function has empty image, cannot hit any nonempty codomain
n≥1,k=0n \ge 1, k = 0Surj(n,0)=0\mathrm{Surj}(n,0) = 0No functions at all exist into the empty set from a nonempty domain
kk very large relative to formula's summation boundSum still runs j=0,…,kj=0,\dots,kThe j=kj=k term is always (−1)k(kk)0n=0(-1)^k \binom{k}{k}0^n = 0 for n≥1n\ge1, contributing nothing but included for symmetry with inclusion-exclusion's derivation
Confusing Surj(n,k)\mathrm{Surj}(n,k) with S(n,k)S(n,k)Off by factor k!k!Surjections are labeled-codomain counts; Stirling numbers count unlabeled partitions

The mathematician behind it

Origins · 1 minJames Joseph Sylvester and how this was discovered
JJ
James Joseph Sylvester
1814–1897 · Victorian Britain, invariant theory and combinatorics

Sylvester was a prolific English mathematician who, alongside Arthur Cayley, developed much of nineteenth-century invariant theory, and who coined a striking number of mathematical terms still in daily use — "matrix," "discriminant," and "graph" (in the modern sense) among them. Sylvester's combinatorial work, including deep studies of partitions and of what we would now recognize as inclusion-exclusion-style counting arguments, fed directly into the systematic treatment of set partitions and surjective counting that later crystallized as the theory of Stirling numbers and inclusion-exclusion enumeration.

History
- 1834: James Stirling's numbers (from decades earlier, formalized and named later) begin to be systematically connected to partition counting problems.
- 1854: Sylvester publishes influential work on partitions and combinatorial identities during his most productive period in invariant theory.
- 1897: Sylvester dies; his combinatorial terminology and results remain foundational to the field.
- 1904: Whitworth's Choice and Chance collects and popularizes systematic treatments of surjection- and partition-counting problems for a broader mathematical audience.
- 1958: Gian-Carlo Rota and successors formalize inclusion-exclusion within the broader lattice-theoretic framework of Möbius functions, situating the surjection formula as a special case of a much larger theory.
Why can't we just count surjections directly without inclusion-exclusion?

There is no simple product rule for "every box gets at least one ball" the way there is for "every ball goes in some box." If we try to place balls one at a time while tracking which boxes are still empty, the number of legal choices for each ball depends on the entire history of previous placements, so a naive product formula does not exist. Inclusion-exclusion sidesteps this by first overcounting (via all knk^n functions), then systematically correcting for the functions that miss one or more specific boxes, using only quantities — (k−j)n(k-j)^n — that are simple products. This is precisely why the technique from Inclusion-Exclusion is the natural tool here rather than a direct combinatorial product argument.

Is Surj(n,k)\mathrm{Surj}(n,k) ever negative, and should I worry the alternating sum could give a negative number?

No — despite the alternating signs, Surj(n,k)\mathrm{Surj}(n,k) is always a nonnegative integer, since it counts an actual finite set of functions. The alternating sum is guaranteed by the proof (via inclusion-exclusion) to evaluate to this nonnegative count; the individual signed terms can be large, but they always combine to the correct nonnegative total. If a computation yields a negative or non-integer number, that is a sure sign of an arithmetic error, not a valid alternative answer.

How does this connect to the Twelvefold Way?

The Twelvefold Way organizes the twelve basic counting problems for functions [n]→[k][n]\to[k] by two binary choices: whether elements of [n][n] are distinguishable or not, whether elements of [k][k] are distinguishable or not, and whether the function is arbitrary, injective, or surjective. Counting surjections with both sets labeled (distinguishable) is exactly the entry computed by Surj(n,k)\mathrm{Surj}(n,k) in this article. Dividing by k!k! moves to the entry where the codomain is treated as unlabeled — giving the Stirling number S(n,k)S(n,k) — and further collapsing the domain labels too changes the problem into counting partitions of the integer nn into kk parts, a different entry entirely.

What is the exponential generating function for surjections, and where does it come from?

The EGF is ∑n≥0Surj(n,k)xnn!=(ex−1)k\sum_{n\ge 0} \mathrm{Surj}(n,k) \frac{x^n}{n!} = (e^x-1)^k. This follows from the "exponential formula" in combinatorial species theory: a surjection onto [k][k] corresponds to partitioning [n][n] into kk labeled nonempty blocks, each block being an arbitrary nonempty subset (EGF ex−1e^x - 1 per block, since ex=∑xm/m!e^x = \sum x^m/m! counts all subsets including the empty one). Raising to the kkth power accounts for the kk distinguishable blocks. Extracting the coefficient of xn/n!x^n/n! and multiplying by n!n! reproduces the same alternating sum as the inclusion-exclusion derivation, giving an independent check on the formula.

Does the formula work when k=1k=1?

Yes. When k=1k=1, every function [n]→{1}[n] \to \{1\} automatically sends every element to the unique target, so it is automatically surjective (for n≥1n \ge 1), giving Surj(n,1)=1\mathrm{Surj}(n,1) = 1. Checking the formula: ∑j=01(−1)j(1j)(1−j)n=1n−0n=1−0=1\sum_{j=0}^1 (-1)^j\binom1j(1-j)^n = 1^n - 0^n = 1 - 0 = 1 for n≥1n \ge 1, matching perfectly. This also confirms the formula correctly handles the boundary convention 0n=00^n = 0 for n≥1n \ge 1.

Can this formula be extended to count surjections with prescribed minimum fiber sizes, e.g. onto k boxes each with at least 2 balls?

Yes, this is a natural generalization solved by the same inclusion-exclusion technique combined with generating functions: instead of requiring each fiber nonempty, require each fiber to have size in some prescribed set, and use the EGF of that constraint raised to the kkth power, then extract coefficients. The basic surjection formula is the special case where the constraint is simply "nonempty," i.e., fiber size ≥1\ge 1. This generalization is a standard bridge topic connecting surjection-counting to the broader theory of set partitions with block-size restrictions.

Why is Surj(n,n)=n!\mathrm{Surj}(n,n) = n! intuitively, beyond the algebraic verification?

A function between two finite sets of the same size nn is surjective if and only if it is injective if and only if it is bijective — these three conditions coincide exactly when domain and codomain have equal finite cardinality. This is a direct consequence of the pigeonhole principle: if f:[n]→[n]f:[n]\to[n] is surjective but not injective, two domain elements would share an image, forcing some other target to be missed by counting, a contradiction with nn total images needed to cover nn targets using only nn domain elements with a repeat. Hence surjections from [n][n] to [n][n] are exactly the permutations of [n][n], of which there are n!n!.

Before this

Where this leads