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

[Jaap Spies]

Edwin Clark wrote:
> 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
>>

Let a(n) be the permanent of the (0,1)-matrix of order nxn with n-1
diagonal 0s only.
Let b(n) be the permanent of the (0,1)-matrix of order nxn with n
diagonal 0s only.

Then by expanding along the first row

b(n) =  0.b(n-1) + (n-1) a(n-1) = (n-1) a(n-1)
a(n) =  1.b(n-1) + (n-1) a(n-1)

So a(n) = (n-2) a(n-2) + (n-1) a(n-1) and we get
with a(1)=1 and a(2)=1
the sequence 1, 1, 3, 11, 53, etc.

Which is in fact A000255.

Jaap Spies