peb at delcam.com
Tue Sep 1 11:10:29 UTC 2009
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
> 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:
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.
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
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)
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.
More information about the ringing-theory