Permanents and determinants of (0,1) matrices

[Edwin Clark]

On Sat, 1 Nov 2003, Yuval Dekel wrote:

> In the reference, sequence A000409 is given and there Neil writes :
> 
> "What exactly is the difference between this sequence and A000410? -
>    njas" .
> 
> Does someebody know ?
> 
> Yuval
> 

I think I have figured it out from reading the Metropolis/Stein paper:

Note that if one defines the function T(n) as in this paper:
(Pardon the Maple.)

> with(combinat):
> T:=proc(n) -sum(stirling1(n+1,k+1)*binomial(2^k-1,n),k=0..n-1); end
proc:
> seq(T(n),n=2..6);

                      0, 6, 350, 43260, 14591171

The sequence agrees with A000409. Note the index starts with 2. And it is
easy to calculate more terms:

0, 6, 350, 43260, 14591171, 14657461469, 46173502811223,
474928141312623525, 16489412944755088235117, 1985178211854071817861662307,
846428472480689964807653763864449,
1299141117072945982773752362381072143359,
7268140170419155675761326840423792818571154945,
149650282980396792665043455999899697765782372693740287,
11426232642182841032607237762874792528864825400979653977461473,
3254873821196966469285481340406597415823975009378171747126253327071967,
3476449209929059845527079573613456758103614767500363423859054867568167493902273,
13980717528486182361090627404602011742783914018461897795771634935595086197572962496841535,
212460614233626811031469855469914796102069609138795096280193025593660372147137351706195644596967169

According to the M/S paper T(n) gives 

"the number of $n\times n (0,1)$ matrices having distinct,
non-zero ordered rows, but having at least two equal columns or at least
one zero column."

This is a lower bound for the set of all $n\times n (0,1)$ matrices having
distinct, non-zero ordered rows and determinant 0.

Here ordered means that we take only one representative from the
n! matrices obtained by all permutations of the distinct columns of an nxn
matrix. 

If we let a(n) denote the number of all $n\times n (0,1)$ matrices having
distinct, non-zero ordered rows and determinant 0 then a Maple calculation
gives the sequence 0,0,6,425,656625 agreeing with A000410 up to n =
5. Here the index starts with 1. Presumably Guenter M. Ziegler who is
given credit for n = 7 would know the definition of the sequence.


--Edwin