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](https://oeis.org/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*](http://www.math.uni.wroc.pl/~pms/files/30.2/Article/30.2.1.pdf), 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)



Simple lower bounds for Bell numbers (number of set partitions)?
On further reflection, it seems the answer is no.


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.


