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

[Edwin Clark]

On Wed, 29 Oct 2003, I  wrote:

> 
> 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).
> 

[skip the other characterizations]

> 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
> 

If one replaces the above formula for a(n) by A(n) = a(n+1) then
the recurrence A(n) = n*A(n-1)+(n-1)*A(n-1) is valid. At least 
I can say that Maple verifies it: 

> a:=n->n!-sum('(-1)^(i+1)*binomial(n-1,i)*(n-i)!','i'=1..n-1):
> A:=n->a(n+1):
> simplify(A(n)-n*A(n-1)-(n-1)*A(n-2));

PS For those not familiar with the difference between add and sum 
in Maple: add only works when the limits are specific integers,
whereas sum will deal with variable limits (to the extent possible).

Undoubtedly all this is known about permanents of (0,1)-matrices,
but I cannot find a reference for it.

--Edwin