20
$\begingroup$

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.

$\endgroup$
5
  • 7
    $\begingroup$ This is American Mathematical Monthly Problem 11957 with deadline June 30, 2017. I don't know if there is any agreement in the community on this issue, but the AMM does ask that published problems are not posted on the internet before the deadline. $\endgroup$ Apr 29, 2017 at 13:13
  • 4
    $\begingroup$ Since we are now past June 30, discussion of this problem is now reopened. $\endgroup$
    – Todd Trimble
    Jul 2, 2017 at 11:19
  • 7
    $\begingroup$ One of the comments (by Gro-Tsen) - upvoted 7 or or 8 times- said that he disagrees with closing a question on the grounds of being a problem in some given journal of some given mathematical society. I agreed with this comment and also disagree with this comment being erased by one single moderator. $\endgroup$
    – YCor
    Jul 3, 2017 at 9:21
  • $\begingroup$ Is it known when equality holds? $\endgroup$
    – LSpice
    May 12, 2022 at 19:50
  • $\begingroup$ If you look at my proof below, it's going to be exactly when the equality holds for the AM-GM inequality used there. So, it holds when $k=0$, $k=1$, and $k=n$. If $1<k<n$, we can partition the set into unequally sized blocks, so the AM-GM inequality becomes strict. $\endgroup$ Dec 4, 2022 at 19:45

4 Answers 4

9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is very clever. $\endgroup$ Jul 3, 2017 at 7:02
  • $\begingroup$ Your name is the same as my father's, except for one letter. $\endgroup$ May 14, 2022 at 16:26
8
$\begingroup$

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.

$\endgroup$
2
  • 5
    $\begingroup$ It doesn't quite work. Note that when $f$'s are injections, your $g$'s are not just any functions from $[n]$ to $k$-element subsets of $[n]$, they are surjections. So this actually shows a weaker inequality $k! {n \brace k} {n \choose k} \leq n^k {n \brace k}$, which is just ${n \choose k} \leq n^k / k!$. $\endgroup$ Apr 29, 2017 at 7:12
  • $\begingroup$ On the other hand, if we forget about $f$'s being injective, this shows $\sum_{j\leq k} j! {n \brace j} {n \choose j} \leq n^k {n \brace k}$. I'm not sure at the moment what the thing on the left is. $\endgroup$ Apr 29, 2017 at 7:21
8
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I think this is a beautiful argument. $\endgroup$ Jul 4, 2017 at 9:23
2
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ the probability of being surjective should exceed the probability of being injective $\endgroup$ Jul 3, 2017 at 7:59
  • $\begingroup$ "it is also clear that distinct injections go to distinct surjections". This seems false to me (in fact, clearly so). Take $k=1$ to see the problem. $\endgroup$
    – Olivier
    Jan 11, 2019 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.