In this post I am going to show that , the th Bell number, is larger than .
Our main tool will be Burnside’s lemma, which states that if a finite group acts on a finite set , the average number of fixed points of the elements of is equal to the number of orbits of the action of on :
where is the set of fixed points of .
We let , the symmetric group on letters, act on component-wise. The elements of are -tuples consisting of integers between and . Now you may easily convince yourself that it is possible to send a tuple to a tuple if and only if whenever , we also have , and vice versa. In other words we view each -tuple as a function ; its fibres partition , and composition with a permutation preserves the fibres of . It is immediate that and are in the same orbit of if and only if they have the same collection of fibres. For instance, can be sent to by the cycle but there is no way to send to , because any permutation will send to a 3-tuple of the form .
Thus has orbits on . On the other hand since our permutations act component-wise, we have
i.e. the fixed points of acting on are the tuples consisting of fixed points of acting on . Therefore, by Burnside’s lemma, we have
In fact the same argument shows that for any , we have
In particular, the identity of fixes all of , so we have
In fact, by using the fact that a permutation of consists of a subset of (the subset of fixed points), and a derangement of the remaining elements, we easily obtain the formula
where is the number of derangements of a set of elements.