Are surjections $[n]\to [k]$ more common than injections $[k]\to [n]$?

Let $Y = \{1,\ldots, n\}$. Throughout $r \in \{1,\ldots, k\}$ will be the size of the range of a function.

The left-hand side $k^n \binom{n}{k}$ is the size of the union of the sets $\mathcal{L}_r$ of all pairs $(Z, g)$ where $Z$ is an $k$-subset of $Y$ and $g : \{1,\ldots, n\} \rightarrow Z$ has range of size $r$. The right-hand side $\newcommand{\stir}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} n^k \stir{n}{k}$ is the size of the union of the sets $\mathcal{R}_r$ of pairs $(\mathcal{P}, f)$ where $\mathcal{P}$ is a set partition of $\{1,\ldots,n\}$ into $k$ sets and $f : \mathcal{P} \rightarrow Y$ is a function from the $k$-set of parts to $Y$ with range of size $r$.

Let $(Z, g) \in \mathcal{L}_r$. The set $\mathcal{Q}$ of pre-images $\{g^{-1}(y) : y \in Y\}$ is a set partition of $\{1,\ldots,n\}$ into $r$ parts. First choosing an $r$-subset $W$ of $\{1,\ldots, n\}$ (this will be the image of $g$), then a $k$-subset $Z$ of $\{1,\ldots,n\}$ containing $W$, then $\mathcal{Q}$, and finally a bijection between $\mathcal{Q}$ and $W$ to define $g$, we get

\begin{equation}\tag{1} |\mathcal{L}_r| = \binom{n}{r} \binom{n-r}{k-r} \stir{n}{r} r!. \end{equation}

If $\mathcal{P}$ is a partition refining $\mathcal{Q}$ then there is a unique function $\overline{g} : \mathcal{P} \rightarrow \{1,\ldots, n\}$ defined for $X \in \mathcal{P}$ by $\overline{g}(X) = g(x)$, where $x$ is any element of $X$. (Observe that $\overline{g}$ is well-defined, since each part of $\mathcal{P}$ is contained in a part of $\mathcal{Q}$, and $g$ is constant on these parts.) Thus for any such $\mathcal{P}$, we have $(\mathcal{P}, \overline{g}) \in \mathcal{R}_r$. Moreover, since there are $\stir{k}{r}$ ways to combine the parts of $\mathcal{P}$ to form $\mathcal{Q}$, we have

\begin{equation}\tag{2} |\mathcal{R}_r| = \stir{n}{k} \stir{k}{r} \binom{n}{r} r!. \end{equation}

Comparing (1) and (2), we see that there is an injective map $(Z,g) \mapsto (\mathcal{P}(Z,g), \overline{g}\hskip0.5pt)$ from $\mathcal{L}_r$ to $\mathcal{R}_r$ provided that there are sufficiently many choices for $\mathcal{P}(Z,g)$, i.e.

\begin{equation} \tag{3} \binom{n-r}{k-r} \stir{n}{r} \le \stir{n}{k} \stir{k}{r} \end{equation}

whenever $n \ge k \ge r \ge 1$. It therefore suffices to prove (3).

Proof of (3). Given a set partition $\mathcal{Q}$ of $\{1,\ldots, n\}$ with exactly $r$ parts, let

$$ M(\mathcal{Q}) = \{\max\hskip0.5pt X : X \in \mathcal{Q}\} $$

be the $r$-subset of $\{1,\ldots, n\}$ of maximal elements in each part. The right-hand side of (3) is the number of pairs $(\mathcal{P}, \mathcal{Q})$ where $\mathcal{P}$ is a set partition of $\{1,\ldots, n\}$ into $k$ parts refining a set partition $\mathcal{Q}$ of $\{1,\ldots, n\}$ into $r$ parts. The left-hand side is the number of pairs $(\mathcal{Q}, T)$ where $\mathcal{Q}$ is a set partition of $\{1,\ldots, n\}$ into $r$ parts and $T$ is a $(k-r)$-subset of $\{1,\ldots,n\} \backslash M(\mathcal{Q})$.

Given such a pair $(\mathcal{Q},T)$, let $\mathcal{P}$ be the set partition refining $\mathcal{Q}$ obtained by putting every element of $T$ into a new singleton part. Thus if $X$ is a part of $\mathcal{Q}$ then $X$ is split into parts $\{x\}$ for $x \in X \cap T$ and $X \backslash T$. (Since $T$ does not contain $\max X$, $X \backslash T$ is non-empty.) This introduces $k-r$ new parts, so $(\mathcal{P}, \mathcal{Q})$ is as required. Suppose that $\{x\}$ is a singleton part of $\mathcal{P}$ contained in the part $X$ of $\mathcal{Q}$. If $x\not\in T$ then either $X = \{x\}$ or $|X \cap T| = |X|-1$ and $x$ is the maximum of $X$; in both cases $x \in M(\mathcal{Q})$. Thus

$$ T = \bigl\{x : \{x\} \in \mathcal{P}, x \not\in M(\mathcal{Q}) \bigr\} $$

and we can reconstruct $T$ from $(\mathcal{P},\mathcal{Q})$. $\quad \Box$

Acknowledgements. This answer is motivated in part by Richard Stanley's answer and Filip Nikšić's proposal for a proof by an explicit injection.

Given a partition $\pi=\{B_1,\dots,B_k\}$ of $[n]$ and a function $f\colon \pi\to[n]$, define $g\colon[n]\to f(\pi)$ (the image of $f$) by the condition $g(i)=f(B_j)$, where $i\in B_j$. When $f$ is injective, the corresponding $g$'s are just the functions from $[n]$ to a $k$-element subset of $[n]$, so the inequality follows.

I have already accepted Mark Wildon's answer, but just for the reference, let me also post another proof that I found while the discussion was closed. The proof uses the following auxiliary notion that led me to the question in the first place.

Definition. Given a set $S\subseteq [n]$ with $k$ elements and a partition $P$ of $[n]$ with $k$ blocks, we say that $P$ splits $S$ if every block in $P$ contains exactly one element of $S$, that is, $B\cap S \neq \emptyset$ for every $B\in P$.

Proof. We show an equivalent inequality obtained by dividing both sides of the original inequality by $k^k$: $$ k^{n-k} {n \choose k} \leq \frac{n^k}{k^k} {n \brace k} $$

Let $M$ be a binary matrix whose rows are indexed by partitions of $[n]$ with $k$ blocks, columns are indexed by subsets of $[n]$ with $k$ elements, and such that an entry corresponding to partition $P$ and set $S$ is 1 if and only if $P$ splits $S$.

We count the number of ones in the matrix in two different ways. The number of ones in a column indexed by $S$ is the number of partitions that split $S$. Such a partition is uniquely determined by a map from $[n]\setminus S \to S$ that maps $x \in [n]\setminus S$ to $y\in S$ if $x$ and $y$ are in the same block of the partition. Hence the number of ones in the column is $k^{n-k}$, and the total number of ones in $M$ is $k^{n-k} {n \choose k}$. On the other hand, the number of ones in a row indexed by $P=\{B_1, \ldots, B_k\}$ is the number of sets split by $P$. Such a set is uniquely determined by a choice of one element from each block. Hence the number of ones in the row is $\lvert B_1 \rvert \cdots \lvert B_k \rvert$, and the total number of ones in $M$ is obtained by summing over all partitions with $k$ blocks.

From the identity obtained by double counting we get the desired claim by applying the AM-GM inequality: \begin{align*} k^{n-k} {n \choose k} & = \sum_{P=\{B_1, \ldots, B_k\}} \lvert B_1 \rvert \cdots \lvert B_k \rvert \\ & \leq \sum_{P=\{B_1, \ldots, B_k\}} \frac{(\lvert B_1 \rvert + \ldots + \lvert B_k \rvert)^k}{k^k} \\ & = \frac{n^k}{k^k} {n \brace k} \end{align*}