4
$\begingroup$

I am trying to prove that an upper bound for the nth Bell number is n factorial. I am trying to do this by induction. Firstly, the nth Bell number is given by:

$B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-1\choose k}$, for $n \geq 2$ and $B_{0}=B_{1}=1$.

My proof is as follows:

Let the statement $S(n)$ be $B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-1\choose k} \leq n!$. (*)

Clearly $S(2)$ is true.

Assume $S(n)$ true for some $n>2$.

RTP: $S(n+1)$ true, i.e. $B_{n+1}=\sum\limits^{n}_{k=0} B_{k}{n\choose k} \leq (n+1)!$

I tried multiplying both sides of (*) by $n+1$, so we get $(n+1)!$ on the RHS as needed, but then it is not clear that we get $\sum\limits^{n}_{k=0} B_{k}{n\choose k}$ on the LHS.

Can anyone help me to complete this proof? I tried using different forms of the Bell number as well - like using Dobinski's formula. I also got nowhere.

Thanks!

$\endgroup$
2
  • $\begingroup$ Maybe start from the definition of the Bell numbers as the number of partitions of an $n$-element set? $\endgroup$ Apr 9 '20 at 9:19
  • 1
    $\begingroup$ There is a tremendous amount of information about the Bell numbers at oeis.org/A000110 including "$a(n)$ is the number of permutations on $[n]$ in which a 3-2-1 (scattered) pattern occurs only as part of a 3-2-4-1 pattern. Example: $a(3) = 5$ counts all permutations on $[3]$ except $321$." $\endgroup$ Apr 9 '20 at 9:33
9
$\begingroup$

Since $B_n$ is the number of partitions of the set $[n]=\{1,2,3,\dots,n\}$ while $n!$ is the number of linear orderings of $[n]$, we can prove the inequality $B_n\le n!$ by exhibiting an injection from the set of partitions to the set of orderings.

Let $P=\{X_1,X_2,\dots,X_k\}$ be a partition of $[n]$, indexed so that $\min X_i\lt\min X_j$ when $i\lt j$. Map $P$ to the ordering of $[n]$ in which all elements of $X_i$ precede all elements of $X_j$ when $i\lt j$, and the elements within each set $X_i$ are arranged in the opposite of their natural order. For instance, $$\{\{1,7,8,9\},\{2,4,6\},\{3\},\{5\}\}\mapsto(9,8,7,1,6,4,2,3,5).$$ It is easy to see that this is an injection.

As a variation of this argument, the cycle decomposition of a permutation suggests an obvious surjection from the symmetric group $S_n$ to the set of all partitions of $[n]$.

Alternatively, there is an easy proof by induction based on the inequality $B_n\le nB_{n-1}$.
The inequality follows from the observation that any partition of $[n]$ can be obtained from some partition of $[n-1]$ by either adding the new element to one of the existing equivalence classes (of which there are at most $n-1$) or starting a new class.

$\endgroup$
0
2
$\begingroup$

Assume $$B_{n}=\sum\limits^{n-1}_{k=0} B_{k}{n-1\choose k} \leq n!\,.$$ Then $$ \begin{align*} B_{n+1}&=\sum^{n}_{k=0} B_{k}{n\choose k}\\ &=\sum_{k=0}^{n-1}B_k\frac{n}{n-k}\binom{n-1}k+B_n\\ &\leq n\cdot\sum_{k=0}^{n-1}B_k\binom{n-1}k+B_n\\ &=(n+1)\cdot B_n\\ &\leq(n+1)!\,. \end{align*} $$


Hope this helps.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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