blob: 607de71eb47d9ee3ad757714f0390d989bd5f2af (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
% Copyright The Numerical Algorithms Group Limited 1992-94. All rights reserved.
% !! DO NOT MODIFY THIS FILE BY HAND !! Created by ht.awk.
\newcommand{\PermanentXmpTitle}{Permanent}
\newcommand{\PermanentXmpNumber}{9.62}
%
% =====================================================================
\begin{page}{PermanentXmpPage}{9.62 Permanent}
% =====================================================================
\beginscroll
The package \spadtype{Permanent} provides the function
\spadfunFrom{permanent}{Permanent} for square matrices.
%-% \HDindex{matrix!permanent of}{PermanentXmpPage}{9.62}{Permanent}
The \spadfunFrom{permanent}{Permanent} of a square matrix can be computed
in the same way as the determinant by expansion of minors except that for
the permanent the sign for each element is \spad{1}, rather than being
\spad{1} if the row plus column indices is positive and \spad{-1}
otherwise.
This function is much more difficult to compute efficiently than the
\spadfunFrom{determinant}{Matrix}.
An example of the use of \spadfunFrom{permanent}{Permanent} is the
calculation of the \eth{\spad{n}} derangement number, defined to be the number
of different possibilities for \spad{n} couples to dance but never with
their own spouse.
\xtc{
Consider an \spad{n} by \spad{n} matrix with entries \spad{0} on the diagonal and
\spad{1} elsewhere.
Think of the rows as one-half of each couple (for example, the males) and the
columns the other half.
The permanent of such a matrix gives the desired derangement number.
}{
\begin{spadsrc}[\bound{kn}]
kn n ==
r : MATRIX INT := new(n,n,1)
for i in 1..n repeat
r.i.i := 0
r
\end{spadsrc}
}
\xtc{
Here are some derangement numbers, which you see grow quite fast.
}{
\spadpaste{permanent(kn(5) :: SQMATRIX(5,INT)) \free{kn}}
}
\xtc{
}{
\spadpaste{[permanent(kn(n) :: SQMATRIX(n,INT)) for n in 1..13] \free{kn}}
}
\endscroll
\autobuttons
\end{page}
%
|
