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: