max permanent of nonsingular nxn (0,1)-matrices

[Edwin Clark]

If a(n) = max permanent of an nxn nonsingular (0,1) matrix
then a(n) = permanent of the matrix with the least number of
0's which is nonsingular. And this is clearly n-1 0's. By 
permuting rows and columns we can assume the n-1 0's are on
the main diagonal. Unlike the (1,-1) case if one adds anymore
0's then clearly the permanent cannot increase.

I calculated a(n) for n from 1 to 12 using Maple and find
that at least up to 12 it agrees with the sequence
 A000255 which has the following characterizations:

Name:      a(n) = n*a(n-1) + (n-1)*a(n-2).
Comments:  a(n) counts permutations of [1,...,n+1] having no substring
[k,k+1].
              - Len Smiley (smiley(AT)math.uaa.alaska.edu), Oct 13 2001
           Also a(n-2) = !n/(n - 1) where !n is the subfactorial of n,
A000166(n) -
              Lekraj Beedassy (beedassylekraj(AT)hotmail.com), Jun 18 2002
           Also determinant of the tridiagonal n X n matrix M such that
M(i,i)=i,
              and for i=1,..,n-1, M(i,i+1)=-1, M(i+1,i)=i. - Mario
Catalani
              (mario.catalani(AT)unito.it), Feb 04 2003
 

-----------------------------------------------

Maybe someone can see the equivalence. It's the number of permutations f
of {1,2,...,n} such that f(i) <> i for i from 1 to n-1 (almost
derangements of {1, 2, . . ., n}.) Using inclusion-exclusion we get
a(n) = n!-add((-1)^(i+1)*binomial(n-1,i)*(n-i)!,i=1..n-1):

--Edwin