TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

The number of surjections from an $n$ -element set onto a $k$ -element set is $\sum_{i < k + 1} (- 1)^{i} (\binom{k}{i}) (k - i)^{n}$ , read in $R$ through $ι$

Statement

Let $A$ and $B$ be finite sets, $n : = ∣ A ∣$ and $k : = ∣ B ∣$ , and write

$Surj (A, B) : = {f : f is a surjection A \to B}$

(Injection, surjection, bijection). Then $Surj (A, B)$ is finite and, in $R$ ,

$ι ∣ Surj (A, B) ∣ = \sum_{i < k + 1} (- 1)^{i} ι (\binom{k}{i}) ι ((k - i)^{n}),$

where $ι$ is the canonical natural (The canonical natural $ι (n) = n \cdot 1_{F}$ of a field), $(k - i)^{n}$ is the $N$ -valued power of Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , and $k - i$ is the truncated difference of Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ , which is the ordinary one throughout the range $i \leq k$ of the sum.

All three degenerate readings are part of the statement, and each is computed rather than stipulated.

$n = 0$ and $k = 0$ . There is exactly one function $\emptyset \to \emptyset$ , the empty function, and it is a surjection, so the count is $1$ . The sum has the single term $(- 1)^{0} ι (\binom{0}{0}) ι (0^{0})$ , and $0^{0} = 1$ is the base clause of Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , so the sum is $1$ too.
$n = 0$ and $k \geq 1$ . No function $\emptyset \to B$ is a surjection, so the count is $0$ ; and every factor $ι ((k - i)^{0})$ is $1$ , so the sum is the full alternating row sum $\sum_{i < k + 1} (- 1)^{i} ι (\binom{k}{i})$ , which is $0$ because $k \geq 1$ ( $\sum_{k < n + 1} (\binom{n}{k}) = 2^{n}$ , and $\sum_{k < n + 1} (- 1)^{k} ι ⁣ (\binom{n}{k}) = 0$ for $n \geq 1$ , clause 2).
$n \geq 1$ and $k = 0$ . There is no function from a nonempty set to $\emptyset$ , so the count is $0$ ; and the sum has the single term $ι (0^{n})$ , which is $0$ because $n \geq 1$ (Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ , clause (a)).

Facts & Assumptions

Given: Finite sets $A$ and $B$ with $n : = ∣ A ∣$ and $k : = ∣ B ∣$ ; the set $Map (A, B)$ of all functions $A \to B$ ; and, for $b \in B$ , the set $F_{b} : = {f \in Map (A, B) : b \notin f [A]}$ of functions missing the value $b$ .

[L1]

$Map (A, B)$ is finite with $∣ Map (A, B) ∣ = k^{n}$ . This is The set $A^{B}$ of functions $B \to A$ between finite sets is finite, with $∣ A^{B} ∣ = ∣ A ∣^{∣ B ∣}$ with its $A$ taken to be $B$ and its $B$ taken to be $A$ , so that its $A^{B}$ is the set of functions $A \to B$ and its formula reads $∣ B ∣^{∣ A ∣} = k^{n}$ (Exponentiation of natural numbers, $m^{n}$ , and its agreement with the integer power in $R$ ).

[L2]

$(F_{b})_{b \in B}$ is a family of subsets of the finite set $X : = Map (A, B)$ indexed by the finite set $B$ , hence a sieve family with ambient set $X$ , and its intersections $F_{J}$ for $J \subseteq B$ satisfy $F_{\emptyset} = X$ (A finite family $(A_{i})_{i \in I}$ of subsets of a finite set $X$ , the intersections $A_{J}$ for $J \subseteq I$ , and the convention $A_{\emptyset} = X$ , A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , The cardinality $∣ A ∣$ of a finite set).

[L3]

$f \in Map (A, B)$ is a surjection exactly when $f [A] = B$ , that is exactly when there is no $b \in B$ with $b \notin f [A]$ (Injection, surjection, bijection). Hence $Surj (A, B) = X ∖ ⋃_{b \in B} F_{b}$ , and it is finite as a subset of $X$ (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ ).

[L4]

For a finite sieve family $(F_{b})_{b \in B}$ in $X$ with $F_{\emptyset} = X$ , the complementary identity is $ι ∣ X ∖ ⋃_{b \in B} F_{b} ∣ = \sum_{J \in P (B)} (- 1)^{∣ J ∣} ι ∣ F_{J} ∣$ (Inclusion and exclusion: $ι ∣ ⋃_{i \in I} A_{i} ∣ = \sum_{\emptyset \neq J \subseteq I} (- 1)^{∣ J ∣ + 1} ι ∣ A_{J} ∣$ , together with the complementary form counting the elements in none of the $A_{i}$ , clause 2).

[L5]

For $J \subseteq B$ : $∣ J ∣ + ∣ B ∖ J ∣ = ∣ B ∣$ , so $∣ B ∖ J ∣ = k - ∣ J ∣$ (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition, clause 1, and the truncated difference of Finite sums and finite products of natural numbers, $\sum_{k < n} a_{k}$ and $\prod_{k < n} a_{k}$ in $N$ ).

[L6]

Partition of a power set by cardinality: the sets $[B]^{i}$ for $i \in σ (k)$ are pairwise disjoint with union $P (B)$ , since a subset of $B$ has exactly one cardinality and it is at most $k$ ; and $∣ [B]^{i} ∣ = (\binom{k}{i})$ (A subset of a finite set is finite, with $∣ B ∣ \leq ∣ A ∣$ , and equality holds if and only if $B = A$ , clause 2, The set $[A]^{k}$ of $k$ -element subsets and the binomial coefficient $(\binom{n}{k}) : = ∣ [n]^{k} ∣$ , $∣ P (A) ∣ = 2^{∣ A ∣}$ for finite $A$ ).

[L7]

Splitting a sum along a partition of its index set (The sum rule: a finite disjoint union is finite with $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣$ and $∣ ⋃_{i \in I} A_{i} ∣ = \sum_{i \in I} ∣ A_{i} ∣$ , and a sum over a finite index set splits along a partition, clause 3); a constant real summand $\sum_{p \in S} λ = ι (∣ S ∣) λ$ and the bridge $\sum_{i \in n} u_{i} = \sum_{i < n} u_{i}$ (The sum $\sum_{i \in S} a_{i}$ over a finite index set, and its product form, clauses (a) and (c)); and the real finite sum itself (Finite sums and finite products, by recursion).

[L8]

$ι$ is injective and $(- 1)^{0} = 1$ (Laws of finite sums and products in $N$ , and $ι (\sum_{k < n} a_{k}) = \sum_{k < n} ι (a_{k})$ , clause 7, Integer powers $a^{m}$ ).

Proof

technique · direct

1.1

The ambient set. Put $X : = Map (A, B)$ ; it is finite with $∣ X ∣ = k^{n}$ by [L1].

1.2

The sieve family. For $b \in B$ the set $F_{b}$ of functions missing $b$ is a subset of $X$ , and by [L3] a function $f \in X$ is a surjection exactly when $f \notin ⋃_{b \in B} F_{b}$ ; so $Surj (A, B) = X ∖ ⋃_{b \in B} F_{b}$ is the complement of the union of the sieve family $(F_{b})_{b \in B}$ inside $X$ .

L2L3construct

1.3

The intersections are function sets. For every $J \subseteq B$ , $F_{J} = Map (A, B ∖ J)$ : for $J \neq \emptyset$ , $f \in F_{J}$ says that $f$ misses every $b \in J$ , that is that $f$ takes all its values in $B ∖ J$ ; and for $J = \emptyset$ both sides are $Map (A, B)$ , the left by the stipulation $F_{\emptyset} = X$ of [L2]. Hence $∣ F_{J} ∣ = ∣ B ∖ J ∣^{n} = (k - ∣ J ∣)^{n}$ by [L1] applied to $B ∖ J$ and by [L5].

L1L2L5

2.1

The sieve. Applying [L4] to the family of step 1.2 and substituting step 1.3, $ι ∣ Surj (A, B) ∣ = \sum_{J \in P (B)} (- 1)^{∣ J ∣} ι ∣ F_{J} ∣ = \sum_{J \in P (B)} (- 1)^{∣ J ∣} ι ((k - ∣ J ∣)^{n})$ .

step 1.2step 1.3L4

3.1

Grouping the subsets of $B$ by size. Splitting the last sum along the partition of [L6] and using the constant clause of [L7] on each block, where the summand depends on $J$ only through $∣ J ∣ = i$ , gives $\sum_{J \in P (B)} (- 1)^{∣ J ∣} ι ((k - ∣ J ∣)^{n}) = \sum_{i < k + 1} ι (\binom{k}{i}) (- 1)^{i} ι ((k - i)^{n})$ .

step 2.1L6L7

4.1

Combining steps 2.1 and 3.1 gives $ι ∣ Surj (A, B) ∣ = \sum_{i < k + 1} (- 1)^{i} ι (\binom{k}{i}) ι ((k - i)^{n})$ , and $Surj (A, B)$ is finite by [L3]; since $ι$ is injective, the identity determines the count in $N$ .

step 2.1step 3.1L3L8∎

Remarks

The convention $0^{0} = 1$ is load bearing exactly once, at $n = 0$ and $k = 0$ , where the formula returns $ι (0^{0})$ and the truth is that the empty function is a surjection onto the empty set. It is not a convenience: it is the base clause of the recursion defining natural exponentiation, and changing it would make the formula false at that single point.
Why the family is indexed by $B$ and not by $A$ . The sieve removes the functions that miss a value, and there is one condition per element of the codomain. This is also why the alternating sum runs to $k$ and not to $n$ .
The count is a natural number. The identity is stated in $R$ because it carries signs, and $ι$ is injective, so it pins down the natural number $∣ Surj (A, B) ∣$ exactly.

Depends on

Used by

Dependency tree · two levels

61 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Surjective function (Wikipedia) (standard reference, not scraped)
Inclusion-exclusion principle (Wikipedia) (standard reference, not scraped)
Twelvefold way (Wikipedia) (standard reference, not scraped)
Algebraic Combinatorics Blueprint: Surjections (standard reference, not scraped)

The number of surjections from an nn-element set onto a kk-element set is ∑i<k+1(−1)i(ki)(k−i)n∑i<k+1​(−1)i(ik​)(k−i)n, read in RR through ιι