On Nov 27, 2007 10:47 AM, Jaap Spies <[EMAIL PROTECTED]> wrote:
>
> Jaap Spies wrote:
>
> >
> > 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}
> >
> >
>
> This is my favorite application of permanents: counting the number of
> permutations with restricted positions!
That is indeed very beautiful. It's not so good from an efficiency
point of view though:
sage: time a=derangements(10000,0)
CPU time: 45.73 s, Wall time: 47.70 s
sage: time b=rencontres_number(10000,0)
CPU time: 1.11 s, Wall time: 1.21 s
at least not practically. This might be because factorial and
multiprecision arithmetic are both so fast in sage.
>
> See:
>
> encontres
> system:sage
>
> {{{id=0|
> 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)
> }}}
>
> {{{id=1|
> derangements(3,0)
> ///
> 2
> }}}
>
> {{{id=2|
> derangements(6,1)
> ///
> 264
> }}}
>
> {{{id=3|
> for i in range(12):
> for j in range(i+1):
> print derangements(i,j),
> print
> ///
> 1
> 0 1
> 1 0 1
> 2 3 0 1
> 9 8 6 0 1
> 44 45 20 10 0 1
> 265 264 135 40 15 0 1
> 1854 1855 924 315 70 21 0 1
> 14833 14832 7420 2464 630 112 28 0 1
> 133496 133497 66744 22260 5544 1134 168 36 0 1
> 1334961 1334960 667485 222480 55650 11088 1890 240 45 0 1
> 14684570 14684571 7342280 2447445 611820 122430 20328 2970 330 55 0 1
> }}}
>
> {{{id=4|
> derangements(0,0)
> ///
> 1
> }}}
>
> {{{id=5|
> derangements(1,0)
> ///
>
> 0
> }}}
>
>
> Jaap
>
>
>
> >
>
--
William Stein
Associate Professor of Mathematics
University of Washington
http://wstein.org
--~--~---------~--~----~------------~-------~--~----~
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/
-~----------~----~----~----~------~----~------~--~---
