Opened 13 years ago

Closed 13 years ago

Last modified 12 years ago

#1290 closed enhancement (fixed)

[with patch] add computationg of Rencontres numbers to Sage

Reported by: was Owned by: mhansen
Priority: major Milestone: sage-2.8.15
Component: combinatorics Keywords:
Cc: sage-combinat Merged in:
Authors: Reviewers:
Report Upstream: Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description

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.

Attachments (1)

trac1290.patch (1.9 KB) - added by was 13 years ago.

Download all attachments as: .zip

Change History (5)

Changed 13 years ago by was

comment:1 Changed 13 years ago by 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.

comment:2 Changed 13 years ago by mhansen

Looks good to me.

comment:3 Changed 13 years ago by mabshoff

  • Resolution set to fixed
  • Status changed from new to closed

Merged in 2.8.15.alpha2.

comment:4 Changed 12 years ago by nthiery

  • Cc sage-combinat added
Note: See TracTickets for help on using tickets.