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