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

[Jaap Spies]

Dear Seqfans,

Table I and table II are output of an implementation of Ryser's algorithm for m x n matrices.
Before I explain what is calculated, let us look to the numbers. We recognize several sequences
from the OEIS.

Table I:
  m=1          0               1               2               3               4               5
               1               3               7              13              21              31
               2              11              32              71             134             227
               9              53             181             465            1001            1909
              44             309            1214            3539            8544           18089
             265            2119            9403           30637           81901          190435
            1854           16687           82508          296967          870274         2203319
           14833          148329          808393         3184129        10146321        27772873
          133496         1468457         8743994        37401155       128718044       378673901
         1334961        16019531       103459471       477471021      1764651461      5551390471
        14684570       190899411      1328953592      6581134823     25992300894     87057596075
       176214841      2467007773     18414450877     97388068753    409295679480   1453986826852
m=13 2290792932     34361893981    273749755386   1539794658307   6860637960916  25762463877481
          ^                 ^              ^               ^               ^               ^
          |                 |              |               |               |               |
        A000166           A000255       A000153          A000261        A001909         A001910


Table II:

m=1           1               2               3               4               5               6
               1               4               9              16              25              36
A027444 ->    3              14              39              84             155             258
              11              64             213             536            1135            2136
              53             362            1395            4004            9545           19998
             309            2428           10617           34176           90445          208524
            2119           18806           91911          327604          952175         2393754
           16687          165016          890901         3481096        11016595        29976192
          148329         1616786         9552387        40585284       138864365       406446774
         1468457        17487988       112203465       514872176      1893369505      5930064372
        16019531       206918942      1432413063      7058605844     27756952355     92608986546
       190899411      2657907184     19743404469    103969203576    435287980375   1541044427972
      2467007773     36828901754    292164206263   1637182718036   7269933749277  27216451364582
     34361893983    547499500380   4619383966443  27442555381104 128812324446047 508388558664014
          ^               ^
          |               |
      A000255           A055790

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:
   a(m,n)=1*b(m-1,n-1) + (n-1)*a(m-1,n-1), a(1,n)=n
   b(m,n)=0*b(m-1,n-1) + (n-1)*a(m-1,n-1), b(1,n)=n-1
So we have recurrencies:

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

and an interresting relation:

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

In table I we see b(m,m+d) for d=0,1,2,3,4,5 and in Table II a(m,m+d) for d=0,...,5.
For d=0 we have square matrices with m, resp. m-1 zeros, see (A000166, A000255).

Writing this, the question arises how this fits in the OEIS.
Maybe it is just interresting.

Jaap Spies