[seqfan] nXk graphs with x->(x+1) mod z adjacent successors

[Ron Hardin]

Take an nXk array of values in 0..z-1, with each value x adjacent to a value (x+1) mod z.
(It needs a successor but not a predecessor.)
Adjacent here means horizontally or vertically next to.

Short tables of T(n,k) for z=3..8 with recurrences for columns 2,3 and examples for 4x4

Slightly notable is that the recurrences apply to the whole series, including trivially impossible leading zeros.

Tables:

/tmp/dkt
T(n,k)=Number of nXk 0..2 arrays x(i,j) with each element horizontally or vertically next to at least one element with value (x(i,j)+1) mod 3, and upper left element zero
Table starts
.0....0.......0........0.........0.........0...........0.........0........0
.0....0.......2........8........30.......108.........386......1376.....4902
.0....2......28......258......2318.....19996......173042...1495602.12923884
.0....8.....258.....5734....115630...2348840....47524048.960953664.........
.0...30....2318...115630...5524854.261026756.12303458948...................
.0..108...19996..2348840.261026756.........................................
.0..386..173042.47524048...................................................
.0.1376.1495602............................................................
.0.4902....................................................................
.0.........................................................................
Empirical for column k:
k=2: a(n)=4*a(n-1)-a(n-2)-2*a(n-3)
k=3: [order 10]
k=4: [order 34]
Some.solutions.for.4X4..
..0..1..2..1....0..1..0..2....0..0..1..2....0..1..0..2....0..1..0..2..
..2..1..0..0....0..2..1..1....1..2..1..0....2..2..0..1....0..2..1..0..
..1..2..2..1....1..2..2..0....0..1..0..2....0..1..1..0....1..1..1..2..
..0..0..1..0....2..0..1..0....2..2..0..1....2..0..2..2....2..0..2..1..


/tmp/dkv
T(n,k)=Number of nXk 0..3 arrays x(i,j) with each element horizontally or vertically next to at least one element with value (x(i,j)+1) mod 4, and upper left element zero
Table starts
.0.....0.......0.........0..........0..........0............0...........0
.0.....2.......6........26........118........522.........2310.......10234
.0.....6......34.......514.......5838......64838.......722386.....8040426
.0....26.....514.....18218.....517794...15075834....442507578.12967930114
.0...118....5838....517794...38111288.2905031942.220881339818............
.0...522...64838..15075834.2905031942....................................
.0..2310..722386.442507578...............................................
.0.10234.8040426.........................................................
.0.45334.................................................................
.0.......................................................................
Empirical for column k:
k=2: a(n)=4*a(n-1)+a(n-2)+4*a(n-3)
k=3: [order 13]
Some.solutions.for.4X4..
..0..1..0..1....0..1..0..3....0..3..2..1....0..3..0..3....0..1..3..0..
..1..2..3..2....3..2..2..1....1..0..1..3....1..0..1..2....3..2..1..1..
..0..3..0..1....1..1..3..2....2..3..3..0....2..3..2..1....1..2..1..2..
..1..2..1..0....2..3..0..1....1..0..2..1....1..0..3..2....2..3..0..3..


/tmp/dla
 T(n,k)=Number of nXk 0..4 arrays x(i,j) with each element horizontally or vertically next to at least one element with value (x(i,j)+1) mod 5, and upper left element zero
Table starts
.0...0......0........0.........0.........0........0..........0.......0....0.0
.0...0......0........0.........2.........8.......32........120.....430.1508..
.0...0......0.......82.......842......9068....92538.....934880.9391704.......
.0...0.....82.....3200.....88580...2467778.68210356.1854786186...............
.0...2....842....88580...6605632.501998702...................................
.0...8...9068..2467778.501998702.............................................
.0..32..92538.68210356.......................................................
.0.120.934880................................................................
.0.430.......................................................................
.0...........................................................................
Empirical for column k:
k=2: a(n)=4*a(n-1)-4*a(n-3)-9*a(n-4)-6*a(n-5)
k=3: [order 31]
Some.solutions.for.4X4..
..0..4..3..2....0..4..3..3....0..3..4..3....0..1..2..3....0..4..3..2..
..1..2..3..1....1..2..3..4....1..2..0..2....4..3..2..4....1..2..3..1..
..0..2..4..0....0..1..1..0....3..1..1..2....3..3..1..0....0..2..4..0..
..4..3..3..4....4..3..2..4....4..0..4..3....3..4..0..4....4..3..2..1..


/tmp/dlb
 T(n,k)=Number of nXk 0..5 arrays x(i,j) with each element horizontally or vertically next to at least one element with value (x(i,j)+1) mod 6, and upper left element zero
Table starts
.0....0......0.......0........0.......0.........0.......0....0.0
.0....0......2.......8.......30.....120.......506....2144.9030..
.0....2.....28.....270.....2966...34684....405122.4682406.......
.0....8....270....7078...225010.7476932.239885668...............
.0...30...2966..225010.20908278.................................
.0..120..34684.7476932..........................................
.0..506.405122..................................................
.0.2144.........................................................
.0..............................................................
Empirical for column k:
k=2: a(n)=5*a(n-1)-5*a(n-2)+5*a(n-3)+8*a(n-4)
k=3: [order 20]
Some.solutions.for.4X4..
..0..5..4..1....0..5..4..3....0..5..0..5....0..1..2..1....0..1..2..1..
..1..2..3..2....1..4..1..4....1..2..1..0....3..0..3..4....5..4..3..2..
..1..0..5..4....2..3..2..5....0..3..2..5....4..5..0..5....4..1..2..1..
..2..3..4..3....1..2..1..0....5..4..3..4....3..2..1..0....3..0..5..0..


/tmp/dlc
 T(n,k)=Number of nXk 0..6 arrays x(i,j) with each element horizontally or vertically next to at least one element with value (x(i,j)+1) mod 7, and upper left element zero
Table starts
.0.0.....0.......0.......0.......0........0......0..0.0
.0.0.....0.......0.......0.......0........2......8.32..
.0.0.....0.......0......52....1738....18106.197916.....
.0.0.....0.....272...35170.1003084.29871142............
.0.0....52...35170.3535192.............................
.0.0..1738.1003084.....................................
.0.2.18106.............................................
.0.8...................................................
.0.....................................................
Empirical for column k:
k=2: a(n)=4*a(n-1)-4*a(n-3)-8*a(n-4)-12*a(n-5)-17*a(n-6)-10*a(n-7)
k=3: [order 64]
Some.solutions.for.4X4..
..0..6..5..4....0..1..2..3....0..1..2..1....0..6..3..2....0..6..5..4..
..1..5..2..3....6..3..2..4....6..5..3..2....1..5..4..1....1..5..4..3..
..2..1..1..0....5..4..1..5....3..4..4..5....2..3..2..0....2..5..6..2..
..3..4..5..6....5..6..0..6....2..1..0..6....1..4..5..6....3..4..0..1..


/tmp/dld
 T(n,k)=Number of nXk 0..7 arrays x(i,j) with each element horizontally or vertically next to at least one element with value (x(i,j)+1) mod 8, and upper left element zero
Table starts
.0...0.....0......0......0.......0......0...0.0
.0...0.....0......2......8......32....118.440..
.0...0....16....170...1716...18588.215314......
.0...2...170...4648.129874.4038314.............
.0...8..1716.129874............................
.0..32.18588...................................
.0.118.........................................
.0.............................................
Empirical for column k:
k=2: a(n)=5*a(n-1)-4*a(n-2)-5*a(n-3)+9*a(n-4)+12*a(n-5)
k=3: [order 32]
Some.solutions.for.4X4..
..0..1..0..7....0..1..2..1....0..7..6..7....0..3..4..5....0..1..2..1..
..1..2..3..4....3..4..3..2....1..2..1..0....1..2..1..6....7..2..3..0..
..0..7..6..5....4..5..0..1....0..3..0..7....6..7..0..7....2..3..4..7..
..3..4..5..4....3..6..7..0....3..4..5..6....5..6..5..6....1..0..5..6..


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