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.)
- Daniel Berend and Tamir Tassa, Improved Bounds on Bell Numbers and on Moments of Sums of Random Variables, Probability and Mathematical Statistics 30(Fasc. 2), 185–205, 2010.
- Donald Knuth, The Art of Computer Programming, Vol. 4A, Section 7.2.1.5. Addison-Wesley, 2011. (ISBN 0-201-03804-8; this section also appears in Fascicle 3, 2005, ISBN 0-201-85394-9)