6
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$ Dec 13, 2012 at 17:47
  • 1
    $\begingroup$ 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 $\endgroup$ Dec 13, 2012 at 18:09
  • $\begingroup$ @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. $\endgroup$ Dec 14, 2012 at 0:29
  • 3
    $\begingroup$ B_n >= (n/log_2(n))^n is false already for n = 47... $\endgroup$ Dec 14, 2012 at 22:19

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ See Fredrik Johannsson's comment above for an answer to the last sentence. $\endgroup$ Jun 1, 2015 at 7:54

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.