9.62 Permanent

The package Permanent provides the function permanentpermanentPermanent for square matrices. The permanentpermanentPermanent 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 determinantdeterminantMatrix. An example of the use of permanentpermanentPermanent 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

Void

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

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

Compiling function kn with type PositiveInteger -> Matrix Integer

\[\]

44

_{Type: PositiveInteger}

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

Cannot compile conversion for types involving local variables.
   In particular, could not compile the expression involving
   :: SQMATRIX(n,INT)
AXIOM will attempt to step through and interpret the code.

\[\]

[0,1,2,9,44,265,1854,14833,133496,1334961,14684570,176214841,2290792932]

_{Type: List NonNegativeInteger}