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.



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. 


