Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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
2  
B_n >= (n/log_2(n))^n is false already for n = 47... –  Fredrik Johansson Dec 14 '12 at 22:19
add comment

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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