Lagmental Vicfred

Inclusion--Exclusion Counts Onto Functions by Vicfred

A surjection is a function that misses none of the target values, so missing-value events can be excluded. A small computation will anchor the general statement before the abstraction takes over.

Set-up

Enumerative combinatorics turns a finite set \(\Omega\) into several reversible descriptions. Binomial coefficients \(\binom nk\) appear whenever a choice forgets order but remembers size.

$$ \operatorname{Surj}(n,k)=\#\{f:[n]\twoheadrightarrow[k]\} $$

The definition determines which expressions are legal; only then does the identity become meaningful. An equality in \(\mathcal A\) may change ambient meaning, so I keep \(\mathsf D\) separate from \(\mathsf C\).

$$ \operatorname{Surj}(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n $$

The calculation

The middle display is intentionally dense: it is where signs, bounds, multiplicities, or normalising factors are most likely to be lost.

$$ \operatorname{Surj}(5,3)=3^5-\binom31\,2^5+\binom32\,1^5=243-96+3=150 $$

What survives abstraction

The invariant statement is the one that does not depend on a convenient choice of coordinates, representatives, basis, or enumeration.

$$ \begin{aligned} \mathsf{D}\;&:\quad \operatorname{Surj}(n,k)=\#\{f:[n]\twoheadrightarrow[k]\},\\[5pt] \mathsf{C}\;&:\quad \operatorname{Surj}(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n. \end{aligned} $$

The boundary

A formula with the correct magnitude can still count the wrong objects. The proof must explain whether order, repetition, labels, and empty parts are allowed.

$$ \boxed{\begin{gathered} \text{compact conclusion}\\[-2pt] \operatorname{Surj}(n,k)=\sum_{j=0}^{k}(-1)^j\binom kj(k-j)^n \end{gathered}} $$

I would use the boxed line as a reference later, while returning to the full display whenever a hypothesis becomes uncertain. That division keeps compression from becoming ambiguity.

This article was posted on Thu 29 May 2014. Facts and circumstances may have changed since publication.
Please contact me before jumping to conclusions if something seems wrong or unclear.