[r-t] Cattermole

[Robin Woolley]

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

                       265   2119

                             1854

 

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...
URL: <http://bellringers.net/pipermail/ringing-theory_bellringers.net/attachments/20090901/c370b12f/attachment.html>