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!
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
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to [email protected]
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/
-~----------~----~----~----~------~----~------~--~---
