I'm not quite certain what descriptors to use to describe the solution I'm looking for, but is there an approximation or useful lower bound for the Bell numbers, for which the amount of terms used in the calculation does not grow with $n$? The ordered Bell numbers have this approximation: $$a(n)\approx\dfrac{n!}{2(log2)^{n+1}}$$ which is nice and tidy, and allows one to compute the ordered Bell number $n$ to a ballpark of order of magnitude, which is useful for my purpose. I mostly wanted to reason about the difference in the order of magnitude for search spaces for a problem where the solution is either a single partition or single ordered partition of a set of size $n$. This is, of course, the difference between the ordered Bell numbers and the Bell numbers.

I realize now that it is probably easier and more accurate to simply enumerate the sequences, and their difference, over the domain in which I expect the $n$ might be for my problem ($1\le n\le 50$). However, I am still curious about how the above approximation was derived, and if the same derivation would be impossible for the Bell numbers. I've read what I could find and partially understand about the subject, but it seems most lower bounds or approximations introduce either a number of terms that grows with $n$, or functions or ideas whose approximation themselves aren't immediately clear to me, or may involve an expansion of terms as well. e.g. this approximation with the Lambert W function: $$B_n\sim \dfrac{1}{\sqrt{n}}\bigg(\dfrac{n}{W(n)}\bigg)^{n+\frac{1}{2}}\text{exp}\bigg(\dfrac{n}{W(n)}-n-1\bigg)$$ It seems to be no less trivial for computation than any other exact form, or Dobiński's formula for that matter.

Below I've made a loose attempt at using Dobiński's reduced formula to derive an expression that meets my needs, but I haven't been able to quite get there, and I might have made some errors along the way.

$$B_n = \Bigg\lceil\dfrac{1}{e}\sum_{k=0}^{K-1}\dfrac{k^n}{k!}\Bigg\rceil, \quad \dfrac{K^n}{K!} \le 1$$ $$0\lt B_n-\dfrac{1}{e}\sum_{k=0}^{K-1}\dfrac{k^n}{k!}\lt1$$ $$\dfrac{1}{e}\sum_{k=0}^{K-1}\dfrac{k^n}{k!} \lt B_n$$

At this point it seems we could choose some expression for $K$ such that the inequality holds, and only take the largest term of the sum as an approximation to have some bound. But I'm not sure where to go from here, or if the bound would be useful for my purposes. $K=2n$ satisfies $\dfrac{K^n}{K!} \le 1$, but in that case the summation doesn't make sense for $k=0$, so we'll assume the inequality doesn't hold for $n=0$ and push forward. Subbing $2n$ for $K$ we get the inequality: $$\dfrac{1}{e}\sum_{k=0}^{2n-1}\dfrac{k^n}{k!} \lt B_n, \quad \text{for } n \ge 1$$ But now on further examination, the value of $k$ for which $\dfrac{k^n}{k!}$ is the largest for a given $n$ is not obvious to me. Observing the graph of $y=\dfrac{x^n}{x!}$ and varying $n$ leads me to believe that finding the root of $k$ for a given $n$, for the following partial derivative will allow us to find the largest term(s). $$\dfrac{\partial}{\partial k}\dfrac{ k^n}{k!}=0, \quad k,n \gt 0$$ But I think this is as far as I can get with my current knowledge. Once an expression for that root is found in terms of $n$, you could round it to get (what I would imagine) is the largest term in the summation, or get two terms by applying the floor and the ceiling function to the expression, getting you the largest two terms, and a hopefully simple expression for the lower bound. But all of the solutions to the above equation seem to involve the inverse digamma function, or something I'm equally unsure of how to approximate simply. Although it seems like the root is able to be approximated by some software.



You must log in to answer this question.

Browse other questions tagged .