William Stein wrote:
> On Nov 26, 2007 11:05 PM, Dan Drake <[EMAIL PROTECTED]> wrote:
>> Hello,
>>
>> I don't know if this is the appropriate place to submit code, but...
>>
>> The combinat.py file lists Rencontres numbers in the TODO section.
>> Here's a function that implements Rencontres numbers. I tried to copy
>> the documentation style, but feel free to edit as necessary.
>
> Hi,
>
> I've cleaned up your code and posted it as a patch here:
> http://trac.sagemath.org/sage_trac/ticket/1290
>
> I also noticed a subtle issue (=bug with sage) with the way you wrote
> the code below
> to use the symbolic sage code, which would lead to a bug when the
> input is very large! I've posted a trac ticket about that here:
> http://trac.sagemath.org/sage_trac/ticket/1289
> This #1289 will be good cannon fodder for bug day.
>
> William
>
>>
>> def rencontres(n, k):
>> r"""
>> Returns the Rencontres number D(n,k), the number of permutations of
>> {1, 2,..., n} with k fixed points.
>>
>> EXAMPLES:
>> Because 312 and 231 are the two permutations of {1, 2, 3} with 0 fixed
>> points, we have:
>>
>> sage: rencontres(3,0)
>> 2
>>
>> Also:
>>
>> sage: rencontres(6,1)
>> 264
>>
>> REFERENCES:
>>
>> http://en.wikipedia.org/wiki/Rencontres_number
>>
>> Sequence A008290 in the OEIS.
>> """
>> if (n - k) % 2 == 0:
>> return binomial(n, k) * ceil(factorial(n - k)/e)
>> else:
>> return binomial(n, k) * floor(factorial(n - k)/e)
>>
>>
Maybe it is interesting to know that you can do this with integer arithmetic
(and permanents!):
Let J_n be the n x n matrix with all 1's and I_n the identity matrix,
then the number of recontres or derangements with no fixed points is
D_{n,0} = per(J_n - I_n) (per being the permanent of the matrix)
Applying Ryser's algorithm one gets the formula:
D_{n,0} = sum_r=0^n-1 (-1)^r * binomial(n,r) * (n-r)^r * (n-r-1)^{n-r}
and than
D_{n,k} = binomial(n,k) * D_{n-k, 0}
Jaap
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://sage.scipy.org/sage/ and http://modular.math.washington.edu/sage/
-~----------~----~----~----~------~----~------~--~---
