[Tutor] A small math puzzle [deranged recreational Python]

[Danny Yoo]

On Sat, 5 Jan 2002, Kirby Urner wrote:


> Re pure derangements with all elements distinct, a simpler
> algorithm, which ignores the whole "fraction object" thread,
> is just:
> 
>   >>> def drs(n):
>   	 if n==1: return 0
> 	 return n * drs(n-1) + (-1)**n
> 
>   >>> drs(1)
>   0
>   >>> drs(2)
>   1
>   >>> drs(3)
>   2
>   >>> drs(4)
>   9
>   >>> drs(5)
>   44
>   >>> drs(6)
>   265
>   >>> drs(7)
>   1854
> 
> But that's not the answer to the puzzle, as it doesn't
> allow repeats of the same letters.


I knew that I heard the word "derangements" before!  In the book "Concrete
Mathematics", there's another derivation for derangements.  Here's another
implementation of drs:

###
from math import floor, e

def drs2(n):
    return int(floor(factorial(n)/e + 0.5) + (n==0))

def factorial(n):
    if n == 0: return 1
    return factorial(n-1) * n
###


And to test it out:

###
>>> [drs2(n) for n in range(8)]
[1, 0, 1, 2, 9, 44, 265, 1854]
###