Permanents of m x n (0,1)-matrices with m and m-1 zeros

[Jaap Spies]

Jaap Spies wrote:
> Dear Seqfans,
[...]

Corrections:
> 
> We define (0,1) matrices A and B of size m x n, (m<=n):
>   a_{ij}=1 except a_{ii}=0 for i=2,...,m (m-1 zeros) and
>   b_{ij}=1 and b_{ii}=0 for i=1,...,m (m zeros).
> 
> Let a(m,n)=per(A) and b(m,n)=per(B). The Laplace expansion gives:

b(m,n)=0*b(m-1,n-1) + (m-1)*a(m-1,n-1) + (n-m)*b(m-1,n-1)
a(m,n)=1*b(m-1,n-1) + (m-1)*a(m-1,n-1) + (n-m)*b(m-1,n-1)

The following relation still holds:
> 
>   a(m,n)=b(m-1,n-1) + b(m,n)
> 

Further

b(m,n)=(n-1)*b(m-1,n-1) + (m-1)*b(m-2,n-2),
with appropriate initial values b(0,k)=1, b(1,k)=k-1.

With this relations we can reconstruct Table I and Table II.

For example the 3d column of Tabel I: d=2, n=m+2
b(m,m+2)=(m+1)*b(m-1,m+1)*(m-1)*b(m-2,m)
b(1,3)=2
b(2,4)=7
b(3,5)=4*b(2,4)+3*b(1,3)=4*7+2*2=32
b(4,6)=5*32+3*7=181

y(m)=b(m,m+2)=(m+1)*y(m-1) + (m-1)*y(m-2), which is after a transformation:

ID Number: A000153 (Formerly M1791 and N0706)
URL:       http://www.research.att.com/projects/OEIS?Anum=A000153
Sequence:  0,1,2,7,32,181,1214,9403,82508,808393,8743994,103459471,
            1328953592,18414450877,273749755382,4345634192131,
            73362643649444,1312349454922513
Name:      a(n) = n*a(n-1) + (n-2)*a(n-2).


Jaap