[r-t] Cattermole

[Fred Bone]

On 01 September 2009 at 11:14, Robin Woolley said:

> Reading the late Paul Cattermole's obituary in the paper on Saturday
> reminded me of a problem he set some years ago. The problem was: How many
> derangements are there on n bells, where a derangement is a row with no
> bell in its own position? 

The number of derangements of n items is (n!/e). The Wikipedia article on 
derangements has a good derivation of this (basically, consider swapping 
the nth item with the item that belongs in the nth place: the result can 
be reduced either to a derangement of n-1 or one of n-2, in n-1 ways 
each; then massage the recurrence relation).