====================================================================
Permanent examples
====================================================================

The package Permanent provides the function permanent for square
matrices.  The 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 1, rather than being 1 if the
row plus column indices is positive and -1 otherwise.  This function
is much more difficult to compute efficiently than the determinant.
An example of the use of permanent is the calculation of the n-th
derangement number, defined to be the number of different possibilities 
for n couples to dance but never with their own spouse.

Consider an n by n matrix with entries 0 on the diagonal and 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.

  kn n ==
    r : MATRIX INT := new(n,n,1)
    for i in 1..n repeat
      r.i.i := 0
    r

Here are some derangement numbers, which you see grow quite fast.

  permanent(kn(5) :: SQMATRIX(5,INT))

  [permanent(kn(n) :: SQMATRIX(n,INT)) for n in 1..13]

See Also:
o )show Permanent

