# Simple lower bounds for Bell numbers (number of set partitions)?

The $n$-th Bell number $B_n$ represents the number of distinct partitions of a set with $n$ distinguished elements. It can be expressed as the infinite sum $B_n = (1/e)\sum_{k=1}^{\infty} (k^n/k!)$, which is also the $n$-th moment of a Poisson distribution with mean $1$. The first few values are known precisely; the Bell numbers form OEIS sequence A000110. There are also several asymptotic expressions, but for an application I need lower bounds.

Write $\log x$ for $\log_2 x$.

For $n \ge 5$, is it true that $B_n \ge (n/\log n)^n$?

Denote the set with elements $1,2,\dots,n$ by $[n]$. Since a partition of $[n]$ has at most $n$ blocks (equivalence classes), each partition of $[n]$ can be obtained via some function $f$ mapping $[n]$ to $[n]$, by regarding $f(i)$ as a name for the partition containing the number $i$. Many different names are possible for the same partition, so $B_n < n^n$, as an easy but crude upper bound.

It is possible to show tighter bounds. For convenience, when $n \ge 2$ we can express $B_n$ in terms of another sequence $c_n$ as $B_n = \left(\frac{c_n n}{\log n}\right)^n$. It seems that $\log c_n \ge -1.5$ for all integers $n \ge 2$, again by just counting functions (although a slightly more involved argument is required than for the trivial upper bound). Moreover, for any $\epsilon > 0$, this argument then also shows that $\log c_n \ge -(1+\epsilon)$ for all large enough $n$ (where the threshold for $n$ grows as $\epsilon$ becomes smaller). By a result of Berend and Tassa, it already follows that $\log c_n < 0.1924$ for all positive $n$, and they state that from an asymptotic argument of de Bruijn it follows that $\log c_n > -0.914$ for all large enough $n$. My question is then whether the stronger bound $\log c_n \ge 0$ holds for $n \ge 5$. Note that the desired inequality fails for $n \le 4$, but can be verified numerically for small values $5\le n \le 26$ via the table of Bell numbers, and for slightly larger values (up to about 100) via computer algebra by computing finite partial sums.

Consider a function $f \colon [n] \to [n]$. This induces a partition via the equivalence relation $\equiv_f$ defined as $i \equiv_f j$ iff $f(i) = f(j)$. As above, the function does not uniquely determine the induced partition. Another way to think about the question is then: can every function $[n] \to [\lceil n/\log n \rceil - 1]$ be mapped to a unique partition, for $n \ge 5$? (But note that this is a slightly different requirement, due to rounding.)

• I can get you part of the way there. Take K=n/logn bags, and put the last K balls one in each bag. Now by distributing the rest of the balls, it is clear that there are at least K^(n-K) such partitions. Gerhard "Hope This Helps You Some" Paseman, 2012.12.13 – Gerhard Paseman Dec 13 '12 at 17:47
• In fact you might be able to leverage the above idea. Take 2K balls and K bags, and distribute so that there is at least 1 ball in each bag. If you get more than K^K arrangements this way, you are gaining ground. You may get a sup of such configurations which may reach your goal. Gerhard "One Step At A Time" Paseman, 2012.12.13 – Gerhard Paseman Dec 13 '12 at 18:09
• @Gerhard Paseman: Those two naming strategies give the lower and upper bounds I sketched (Kousha Etessami originally suggested the idea to me). To go from $\log c_n \ge -(1+\epsilon)$ to $\log c_n \ge 0$ seems to require a new idea. – András Salamon Dec 14 '12 at 0:29
• B_n >= (n/log_2(n))^n is false already for n = 47... – Fredrik Johansson Dec 14 '12 at 22:19

By considering the most significant terms in the asymptotic analysis of de Bruijn, and arguing that they dominate the other terms for large enough $n$, it seems possible to show that for every $\epsilon > 0$, there is some threshold $n_0 = n_0(\epsilon)$ such that $$-0.9139\dots < \log c_n < -0.9139\dots + \epsilon$$ for all $n \ge n_0$. Hence my proposed inequality cannot be true.
(Here the mysterious constant $-0.9139\dots$ is just $\log_2\;\log_2 e - \log_2 e = -1/\ln 2 - \ln\;\ln 2/\ln 2$.)
It would be interesting to establish precisely for which range of $n$ the simple expression $\log c_n \ge 0$ does hold.