Solution
Neighbours Apart
Show the problem again
In how many ways can the set {1, 2, 3, 4, 5, 6, 7} be partitioned into nonempty, unlabelled blocks such that no block contains two consecutive integers (i and i + 1)? The partition into seven singletons counts. Give an integer.
Worked solution
**Answer: 203.** Let f(n, k) count partitions of {1, ..., n} into k blocks with no two consecutive integers in a block. Insert the element n into a valid partition of {1, ..., n − 1}: it can start a new block, or join any existing block except the one containing n − 1. So f(n, k) = f(n − 1, k − 1) + (k − 1) f(n − 1, k), with f(1, 1) = 1. Compare the Stirling numbers of the second kind, S(n, k) = S(n − 1, k − 1) + k S(n − 1, k). One checks that g(n, k) = S(n − 1, k − 1) satisfies exactly the recurrence and initial value of f, so f(n, k) = S(n − 1, k − 1). Summing over k, the number of valid partitions of {1, ..., n} equals the Bell number B(n − 1), the total number of partitions of a set with one fewer element. For n = 7 the answer is B(6) = 203.
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.