! 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.

Any ideas?

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. For now, I have marked my attempt above as a spoiler, and I encourage you to do the same if you decide to answer.

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.

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]$.

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.

Any ideas?

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]$.

! 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.

Any ideas?

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. For now, I have marked my attempt above as a spoiler, and I encourage you to do the same if you decide to answer.