Permanents and determinants of (0,1) matrices

[Edwin Clark]

On Tue, 11 Nov 2003, Jaap Spies wrote:

> N. J. A. Sloane wrote:
> > Hugo asked which of those sequences should be submitted. Well, let's see:
> > 
> [...]
> > 
> > Maximal permanent of a real non-singular (0,1)-matrix of order n:
> > 1 1 3 11 53
> next value 309

This one is already in OEIS as:

ID Number: A000255 (Formerly M2905 and N1166)
URL:       http://www.research.att.com/projects/OEIS?Anum=A000255
Sequence:  1,1,3,11,53,309,2119,16687,148329,1468457,16019531,
           190899411,2467007773,34361893981,513137616783,8178130767479,
           138547156531409,2486151753313617,47106033220679059,
           939765362752547227
Name:      a(n) = n*a(n-1) + (n-1)*a(n-2)

and among the many comments one finds:

Also maximal permanent of a nonsingular n X n (0,1)-matrix, which is
achieved by the matrix with just n-1 0's, all on main diagonal
[Proof by Jaap Spies!]


------------------------------------------------------------------------
> 
> > Number of real non-singular (0,1)-matrices having maximal permanent=
> > a(from previous sequence)
> > 1 6 18 96 600
> 
> next value 4320

This appears to make the following two sequences coincide. A theorem is
suggested.

ID Number: A052655
URL:       http://www.research.att.com/projects/OEIS?Anum=A052655
Sequence:  0,1,6,18,96,600,4320,35280,322560,3265920,36288000,
           439084800,5748019200,80951270400,1220496076800,
           19615115520000,334764638208000,6046686277632000,
           115242726703104000,2311256907767808000
Name:      A simple regular expression in a labeled universe.
Formula:   E.g.f.: x*(-2*x^2+x^3+x+1)/(-1+x)^2
           Recurrence:
{a(1)=1,a(0)=0,a(2)=6,a(3)=18,(-n^2-2*n-1)*a(n)+a(n+1)*n,a(4)=96}
           n*n!



ID Number: A089474
URL:       http://www.research.att.com/projects/OEIS?Anum=A089474
Sequence:  1,6,18,96,600
Name:      Number of real non-singular {0,1}-matrices of order n having
maximal permanent = A089473(n).
------------------------------------------------------------------



--Edwin