Permanents and determinants of (0,1) matrices
Edwin Clark
eclark at math.usf.edu
Wed Nov 12 02:08:11 CET 2003
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
More information about the SeqFan
mailing list