0
$\begingroup$

Prove that, for all even integers n ≥ 2, $(n/2)^{n/2} \le r_n \le n^n$ where $r_n$ are the Bell numbers.

I know the Bell numbers are given by the following recurrence relation:

$B_{n+1} = \sum_{k=0}^n {n \choose k} \ast B_k$

So far I've tried to use an inductive proof, but after the initial step I'm not sure where to go with it. I also tried the reasoning of how the Bell numbers are directly related to the power set on $n$ which can only be as large as $2^n$, but the Bell numbers grow faster than this. The answer seems obvious to me, but I lack the tools to prove it myself.

$\endgroup$

1 Answer 1

2
$\begingroup$

$B_n$ is the number of equivalence elations on a set with $n$ elements. We can take the set to be $[n]=\{1,\dots,n\}$. Put each odd number in a separate equivalence class. Then for each of the $N/2$ even numbers, we have $n/2$ choices fo the class it belongs to, giving $\left(\frac{n}{2}\right)^{n/2}$ different equivalence relations.

On the other hand, imagine that we have $n$ distinct buckets, and we put each element in one of the buckets. There are $n^n$ ways to do this, and every equivalence relation corresponds to one or more such distributions, so there are fewer than $n^n$ equivalence relations.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .