Neighbours Apart
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.
Related problems & prerequisites
Worth solving first
- Photo Finish 6.0/10
- Dominoes and L-Trominoes 6.0/10
- L-Trominoes in a Strip 6.0/10
Source: Classic exercise in wide circulation; no traceable original source. Statement written for AxiomIQ.