[r-t] Cattermole

[Paul Bibilo]

Robin Woolley wrote:
> 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?
A colleague at work sent me the following in response to your questions:
--<snip>--<snip>--
T(i,j) is the number of permutations of j items
where none of the first i items are in their original place.

T(i,j) = T(i-1,j) - T(i-1,j-1)

a) why does this work.
b) is there a simpler way.


a)
Suppose we have T(i-1,j) and want to find T(i,j)
T(i-1,j) has permutations we don't want: ones with the jth item in the correct
place.
How many permutations of the T(i-1,j) have the jth item in the correct place?
It is the same as the number of permuations of T(i-1,j) that have the jth
item and the jth  place deleted.

I.e. the number of permutations of j-1 items where none of the first i-1
items are in the correct place. I.e. T(i-1,j-1)

So T(i,j) = T(i-1,j) - T(i-1,j-1)

b)
Goto google. Type OEIS and click "I'm feeling lucky"
Put 2,9,44,265 in the box.
Formula is noted there:  a(n) = floor((factorial(n)+1)/e)
which is a fairly astonishing formula!

The ± thing is noted there too.
--<snip>--<snip>--

HTH,
-- 
Paul