[with patch] add computationg of Rencontres numbers to Sage

[was]

Dan Drake posted this on sage-devel, and I reformatted it into a proper patch.

I rewrote the patch to avoid using any symbolic computation (e.g., maxima) for speed and to be correct when the input/output is very large.

[jsp]

See my alternative on the mailing list sage-devel: derangements = rencontres

def derangements(n, k):
     if n == 0 and k == 0:
         return 1
     if n == 1 and k == 0:
         return 0

     if k == 0:
         lst = [(-1)^r * binomial(n, r) * (n-r)^r * (n-r-1)^(n-r) for r in range(n)]
         return sum(lst)
     else:
         return binomial(n, k) * derangements(n-k, 0)

Someone should check the implications!? Eventually translate it into Cython, etcetera.

[mhansen]

Looks good to me.

[mabshoff]

Merged in 2.8.15.alpha2.