Re Permanents of (+1,-1) matrices

[Gordon Royle]

Unfortunately, I don't think that the values given here are correct.....

> n = 16:             3185540657152
> n = 17:            53800242216940
> n = 18:           962741176500224
> n = 19:         18195808235851328
> n = 20:        362183230599829504
> n = 21:       7572922094356201472
> n = 22:     165945771114706763776
> n = 23:    3802923921409419771904
> n = 24:   90965940198950249168896
> n = 25: 2267151124762193502928896


My calculations agree with these values for n <= 18, but not for any of
n=19...25.

I get 

18           962741176500224
19         18195808235880448
20        362183230599856128
21       7572922094360723456
22     165945771111208714240
23    3802923921298533384192
24   90965940197460917878784
25 2267151124921333646884864

Of course, the fact that I get different numbers merely shows that (at
least) one of us is incorrect... however I claim that we can at least be
*certain* that the numbers given above for n=19 and n=20 are incorrect.

According to Maple, the claimed numbers factorize as 

> ifactor(18195808235851328);
                        6
                     (2)   (139)  (223)  (691)  (13273751)

and 

> ifactor(362183230599829504);
                          11
                       (2)    (941)  (1093901)  (171803)

while Krauter and Seifter prove that the permanent of an nxn {-1,1}
matrix is divisible by 2^{n - [log_2(n)] - 1}. 

So the claimed values for n=19,20 do not have enough 2's in them.
Strangely the remaining values *do* have enough 2s, but I still don't
agree with them...



I calculated the values as follows:

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

Then by expanding along the first row (like determinant, but with no
sign) we get

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

and by starting with a(2) = 2, b(2) = 0, we get

2 2 0
3 -2 2
4 8 4
5 8 24
6 112 128
7 656 880
8 5504 6816
9 49024 60032
10 491264 589312
(etc.)


I presume that this is the recurrence mentioned in the review of the
Krauter/Seifter paper, but as our library doesn't have the Israel
Journal of Math, it was quicker just to figure it out.