1
2% Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
3% All rights reserved.
4%
5% Redistribution and use in source and binary forms, with or without
6% modification, are permitted provided that the following conditions are
7% met:
8%
9%     - Redistributions of source code must retain the above copyright
10%       notice, this list of conditions and the following disclaimer.
11%
12%     - Redistributions in binary form must reproduce the above copyright
13%       notice, this list of conditions and the following disclaimer in
14%       the documentation and/or other materials provided with the
15%       distribution.
16%
17%     - Neither the name of The Numerical ALgorithms Group Ltd. nor the
18%       names of its contributors may be used to endorse or promote products
19%       derived from this software without specific prior written permission.
20%
21% THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
22% IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
23% TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
24% PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
25% OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
26% EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
27% PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES-- LOSS OF USE, DATA, OR
28% PROFITS-- OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29% LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30% NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31% SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32
33
34The package \spadtype{Permanent} provides the function
35\spadfunFrom{permanent}{Permanent} for square matrices.
36\index{matrix!permanent of}
37The \spadfunFrom{permanent}{Permanent} of a square matrix can be computed
38in the same way as the determinant by expansion of minors except that for
39the permanent the sign for each element is \spad{1}, rather than being
40\spad{1} if the row plus column indices is positive and \spad{-1}
41otherwise.
42This function is much more difficult to compute efficiently than the
43\spadfunFrom{determinant}{Matrix}.
44An example of the use of \spadfunFrom{permanent}{Permanent} is the
45calculation of the \eth{n} derangement number, defined to be the number
46of different possibilities for \spad{n} couples to dance but never with
47their own spouse.
48\xtc{
49Consider an \spad{n} by \spad{n} matrix with entries \spad{0} on the diagonal and
50\spad{1} elsewhere.
51Think of the rows as one-half of each couple (for example, the males) and the
52columns the other half.
53The permanent of such a matrix gives the desired derangement number.
54}{
55\begin{spadsrc}[\bound{kn}]
56kn n ==
57  r : MATRIX INT := new(n,n,1)
58  for i in 1..n repeat
59      r(i, i) := 0
60  r
61\end{spadsrc}
62}
63\xtc{
64Here are some derangement numbers, which you see grow quite fast.
65}{
66\spadcommand{permanent(kn(5) :: SQMATRIX(5,INT)) \free{kn}}
67}
68\xtc{
69}{
70\spadcommand{[permanent(kn(n) :: SQMATRIX(n,INT)) for n in 1..13] \free{kn}}
71}
72