The rook path problem

D.P. Chan posted the following question on sci.math: He did not state whether each walk would have to visit all the points. This made me think about my counting program. I have addapted it in such a way that it can also count walks from a certain point in the first row to a certain point in the last row.

This problem is also known as the chess/rook.path problem in the rec.puzzle FAQ.

Let M(n,m) be the number of paths from one corner to the other corner in P_n x P_m. The the following results were known: 

   M(n,m) = M(m,n)
   M(1,m) = 1
   M(2,m) = 2^(m-1)
I found the following other results: 
   M(3,3) = 12
   M(3,4) = 38
   M(3,m) = 4M(3,m-1) - 3 M(3,m-2) + 2M(3,m-3) + M(3,m-4) (for m > 4)

   M(4,4) = 184
   M(4,5) = 976
   M(4,6) = 5382
   M(4,7) = 29739
   M(4,8) = 163496
   M(4,9) = 896476
   M(4,10) = 4913258
   M(4,11) = 26932712
   M(4,12) = 147657866
   M(4,n) = 12M(4,m-1) - 54M(4,m-2) + 124M(4,m-3) - 133M(4,m-4)
          - 16M(4,m-5) + 175M(4,m-6) - 94M(4,m-7) - 69M(4,m-8)
          + 40M(4,m-9) + 12M(4,m-10) - 4M(4,m-11) - M(4,m-12) (for m > 12)

   M(5,1) = 1
   M(5,2) = 16
   M(5,3) = 125
   M(5,4) = 976
   M(5,5) = 8512
   M(5,6) = 79384
   M(5,7) = 752061
   M(5,8) = 7110272
   M(5,9) = 67005561
   M(5,10) = 630588698
   M(5,11) = 5933085772
   M(5,12) = 55827318685
   M(5,13) = 525343024814
   M(5,14) = 4943673540576
   M(5,15) = 46521924780255
   M(5,16) = 437788749723725
   M(5,17) = 4119750109152730
   M(5,18) = 38768318191017931
   M(5,19) = 364823700357765771
   M(5,20) = 3433121323699285343
   M(5,21) = 32306898830469680384
   M(5,22) = 304019468350280601960
   M(5,23) = 2860931888452842047170
   M(5,24) = 26922391858409506569346
   M(5,25) = 253349332040459400463497
   M(5,26) = 2384107785665647075602841
   M(5,27) = 22435306570786253414376286
   M(5,m) = 30M(5,m-1) - 383M(5,m-2) + 2772M(5,m-3) - 12378M(5,m-4)
          + 33254M(5,m-5) - 40395M(5,m-6) - 44448M(5,m-7) + 239776M(5,m-8)
          - 274256M(5,m-9) - 180404M(5,m-10) + 678758M(5,m-11)
          - 301650M(5,m-12) - 542266M(5,m-13) + 492472M(5,m-14)
          + 184306M(5,m-15) - 225284M(5,m-16) - 102314M(5,m-17)
          + 25534M(5,m-18) + 97396M(5,m-19) + 10392M(5,m-20)
          - 40292M(5,m-21) - 13218M(5,m-22) + 5328M(5,m-23)
          + 5376M(5,m-24) + 1822M(5,m-25) + 319M(5,m-26) + 24M(5,m-27).
For information about how I found these results, please look at my Hamilton counting page. Or in table form: 
   |   1    2    3      4       5         6           7            8
---+----------------------------------------------------------------
1  |   1    1    1      1       1         1           1            1
2  |   1    2    4      8      16        32          64          128
3  |   1    4   12     38     125       414        1369         4522
4  |   1    8   38    184     976      5382       29739       163496
5  |   1   16  125    976    8512     79384      752061      7110272
6  |   1   32  414   5382   79384   1262816    20562673    336067810
7  |   1   64 1369  29739  752061  20562673   575780564  16230458696
8  |   1  128 4522 163496 7110272 336067810 16230458696 789360053252
Simular results are found by Christoph Dürr and others. Recently, Steve Finch has started a page about the subject of rook paths.

Another problem

Later D.P. Chan mailed me to explain that he looked for the number of trails between the two points. In a trail each edge can be visited at most once, but a vertex can be visted more than once. This is a different problem then the one discussed above.

To find solutions for this problem my program needs to be modified to a greater extend.

Counting page | home