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

Question

Here's an interesting inequality involving binomial coefficient and Stirling numbers of the second kind that I believe holds for all $n,k$: $$ k^n {n \choose k} \leq n^k {n \brace k} $$ On the left-hand side we choose a $k$-element subset of the set $[n]=\{1,\ldots,n\}$, and then choose a function from $[n]$ into the chosen subset. On the right-hand side we choose a partition of $[n]$ into $k$ blocks, and then to each block we assign a label from $[n]$. The number of objects on the left-hand side seems to be at most the number of objects on the right-hand side. It is easy to show this for some special cases ($k=0,1,2,n-1,n$), but I don't know how to show it in general.

Another way of looking at the inequality is the following. Provided that $k$ and $n$ are either both zero or both positive, we can rearrange the inequality to get $$ \frac{n^{\underline{k}}}{n^k} \leq \frac{{n \brace k} k!}{k^n} $$ Here, $n^{\underline{k}} = n (n-1) \ldots (n-k+1)$ is the falling factorial power. Now the left-hand side is the ratio of injections to all functions $[k]\to[n]$, and the right-hand side is the ratio of surjections to all functions $[n]\to[k]$. Therefore the inequality intuitively expresses that surjections $[n]\to [k]$ are more common than injections $[k]\to[n]$.

Any ideas how to prove this?

UPDATE: As pointed out by Mark Wildon, this problem has been posted by American Mathematical Monthly with deadline June 30, 2017. It is not clear whether we should be discussing it before then. I tried to mark my attempt below as a spoiler, but the spoiler functionality doesn't seem to be working properly in combination with MathJax. So, if you don't want spoilers, I suggest you stop reading at this point.

SPOILER: Here's a combinatorial approach that proves a weaker inequality: $$ k^{n-k} {n \choose k} \leq n^k {n \brace k} $$ We'll construct an injection from the objects on the left-hand side into the objects on the right-hand side. On the left-hand side we are given a $k$-element subset $K\subseteq [n]$, together with a function $f\colon [n]\setminus K \to K$. We form a partition $P=\{\{x\} \cup f^{-1}(x) \mid x\in K\}$ and a function $g\colon P\to [n]$ given by $g(\{x\} \cup f^{-1}(x))=x$. Function $g$ essentially picks a representative from each block, and serves to uniquely reconstruct the subset $K$ and the function $f\colon [n]\setminus K \to K$.

In the original inequality, on the left-hand side we have a function $f\colon [n]\to K$, meaning that in addition to a mapping $[n]\setminus K\to K$ we have a mapping $K\to K$. In order to construct an injection, our function $g\colon P\to [n]$ must now encode what the representative of each block is, and also how these representatives are mapped among themselves. It is not clear to me how to do this.

I've also tried to prove the inequality algebraically. There are many ways to expand the terms using various identities, but so far I always get stuck.

Answer 1

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.

Answer 2

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.

Answer 3

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*}

Answer 4

Doesn't this admit the following easy argument: given an injection $f:[k] \rightarrow [n]$, let $\sigma(f): [n] \rightarrow [k]$ send $i \in [n]$ to $j \in [k]$ if $f(j)=i$ and to 1 otherwise. $\sigma(f)$ is obviously surjective, and it is also clear that distinct injections go to distinct surjections.