robin at robinw.org.uk
Tue Sep 1 10:14:51 UTC 2009
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? I cannot remember any follow up to this problem so I did a bit of doodling and came up with the following. This must be defined as serendipitous. Consider the table (in Courier New):
n= 3 4 5 6 7
4 18 96 600 4320
3 14 78 504 3720
2 11 64 426 3216
9 53 362 2790
44 309 2428
The first row of the table is the number of changes left when those with the treble at lead have been removed, and is simply (n-1)(n-1)! The remaining entries in each column, the number left when the 2nd, 3rd,... are removed, were found by inspection. The last entry in each column is the number of derangements on that number of bells. (Call this S(n))
The interesting part is this. Successive entries in the jth row of the ith column are simply the (j-1)th entry minus the (j-1)th entry in the (i-1)th column. If you like, T(j,i) = T(j-1,i) - T(j-1,i-1).
If my heuristic is correct, then there are 14833 derangements for n=8. The figure of 176214841 is obtained for n=12 which I have a vague idea agrees with the original question.
My questions are these. (1) Why does this heuristic work? (2) Is there a simpler way?
As a partial answer to (2), I note that S(n) = n.S(n-1)±1 when ± alternates between successive sequence members ('+' for n even) also seems to give a 'good' solution.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the ringing-theory