[seqfan] Domino Tiling ^ 2 = city block distance one permutation?

Ron Hardin rhhardin at att.net
Mon Apr 11 02:33:56 CEST 2011


Permute the elements of a nXk array by moving each element exactly one position 
horizontally or vertically

the number of array permutations appears to be
Table starts
.0....1......0.........1...........0............1.............0.............1
.1....4......9........25..........64..........169...........441..........1156
.0....9......0.......121...........0.........1681.............0.........23409
.1...25....121......1296........9025........78961........609961.......5040025
.0...64......0......9025...........0......1399489.............0.....219750976
.1..169...1681.....78961.....1399489.....45265984.....994077841...27918733921
.0..441......0....609961...........0....994077841.............0.1671065533809
.1.1156..23409...5040025...219750976..27918733921.1671065533809..............
.0.3025......0..40144896...........0.669109276081............................
.1.7921.326041.326199721.34566618241.........................................

all the numbers are squares, take the square root and get
Table starts
.0..1...0.....1......0......1.......0.......1......0......1.....0....1...0.1
.1..2...3.....5......8.....13......21......34.....55.....89...144..233.377..
.0..3...0....11......0.....41.......0.....153......0....571.....0.2131......
.1..5..11....36.....95....281.....781....2245...6336..18061.51205...........
.0..8...0....95......0...1183.......0...14824......0.185921.................
.1.13..41...281...1183...6728...31529..167089.817991........................
.0.21...0...781......0..31529.......0.1292697...............................
.1.34.153..2245..14824.167089.1292697.......................................
.0.55...0..6336......0.817991...............................................
.1.89.571.18061.185921......................................................

which is 
http://oeis.org/A099390/table  the number of domino tilings of a nXk grid

So: take two tilings A and B as defining a permutation.  But how?

Obviously where they align, it's a pure swap.  Where they cross, they define 
cycles.

But I don't see how they define a direction to each cycle.  Any ideas?  There 
are many disjoint cycles in general, and each one has to get a specific 
orientation.

Yet we also have to be able to produce each orientation for each cycle 
independently (?), and I don't see how that's possible if we've already used A 
and B (plus B then A).

The (?) maybe is my error.


 rhhardin at mindspring.com
rhhardin at att.net (either)




More information about the SeqFan mailing list