<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type>
<META name=GENERATOR content="MSHTML 8.00.6001.18812">
<STYLE></STYLE>
</HEAD>
<BODY>
<DIV>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT size=2>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):<?xml:namespace prefix = o ns =
"urn:schemas-microsoft-com:office:office" /><o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT
size=2> <o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2>n=<SPAN style="mso-spacerun: yes"> </SPAN>3<SPAN
style="mso-spacerun: yes"> </SPAN>4<SPAN
style="mso-spacerun: yes"> </SPAN>5<SPAN
style="mso-spacerun: yes"> </SPAN>6<SPAN
style="mso-spacerun: yes">
</SPAN>7<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2> <o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN style="mso-spacerun: yes"> </SPAN>4<SPAN
style="mso-spacerun: yes"> </SPAN>18<SPAN
style="mso-spacerun: yes"> </SPAN>96<SPAN
style="mso-spacerun: yes"> </SPAN>600<SPAN
style="mso-spacerun: yes"> </SPAN>4320<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN style="mso-spacerun: yes"> </SPAN>3<SPAN
style="mso-spacerun: yes"> </SPAN>14<SPAN
style="mso-spacerun: yes"> </SPAN>78<SPAN
style="mso-spacerun: yes"> </SPAN>504<SPAN
style="mso-spacerun: yes"> </SPAN>3720<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN style="mso-spacerun: yes"> </SPAN>2<SPAN
style="mso-spacerun: yes"> </SPAN>11<SPAN
style="mso-spacerun: yes"> </SPAN>64<SPAN
style="mso-spacerun: yes"> </SPAN>426<SPAN
style="mso-spacerun: yes"> </SPAN>3216<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN
style="mso-spacerun: yes">
</SPAN>9<SPAN style="mso-spacerun: yes"> </SPAN>53<SPAN
style="mso-spacerun: yes"> </SPAN>362<SPAN
style="mso-spacerun: yes"> </SPAN>2790<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN
style="mso-spacerun: yes">
</SPAN>44<SPAN style="mso-spacerun: yes"> </SPAN>309<SPAN
style="mso-spacerun: yes"> </SPAN>2428<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN
style="mso-spacerun: yes">
</SPAN>265<SPAN style="mso-spacerun: yes">
</SPAN>2119<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
size=2><SPAN
style="mso-spacerun: yes">
</SPAN>1854<o:p></o:p></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Courier New'; mso-bidi-font-family: 'Times New Roman'"><FONT
face=Arial><FONT size=2> <o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT size=2>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))<o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT
size=2> <o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT size=2>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).<o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT
size=2> <o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT size=2>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.<o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT
size=2> <o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT size=2>My
questions are these. (1) Why does this heuristic work? (2) Is there a simpler
way?<o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT
size=2> <o:p></o:p></FONT></FONT></SPAN></P>
<P style="MARGIN: 0in 0in 0pt" class=MsoNormal><SPAN
style="FONT-FAMILY: 'Times New Roman'"><FONT face=Arial><FONT size=2>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.<o:p></o:p></FONT></FONT></SPAN></P></DIV></BODY></HTML>