A140518
Number of simple paths from corner to corner of an n X n grid with king-moves allowed.
Original entry on oeis.org
1, 5, 235, 96371, 447544629, 22132498074021, 10621309947362277575, 50819542770311581606906543, 2460791237088492025876789478191411, 1207644919895971862319430895789323709778193, 5996262208084349429209429097224046573095272337986011
Offset: 1
For example, when n=8 this is the number of ways to move a king from a1 to h8 without occupying any cell twice.
- Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.
A288033
Number of (undirected) paths in the n X n king graph.
Original entry on oeis.org
0, 30, 5148, 6014812, 57533191444, 4956907379126694, 3954100866385811897908, 29986588563791584765930866780, 2187482261973324160097873804506155572, 1550696105068168200375810546149511240714556526
Offset: 1
A339098
Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) cycles on the n X k king graph.
Original entry on oeis.org
7, 30, 30, 85, 348, 85, 204, 3459, 3459, 204, 451, 33145, 136597, 33145, 451, 954, 316164, 4847163, 4847163, 316164, 954, 1969, 3013590, 171903334, 545217435, 171903334, 3013590, 1969, 4008, 28722567, 6109759868, 61575093671, 61575093671, 6109759868, 28722567, 4008
Offset: 2
Square array T(n,k) begins:
7, 30, 85, 204, 451, ...
30, 348, 3459, 33145, 316164, ...
85, 3459, 136597, 4847163, 171903334, ...
204, 33145, 4847163, 545217435, 61575093671, ...
451, 316164, 171903334, 61575093671, 21964731190911, ...
-
# Using graphillion
from graphillion import GraphSet
def make_nXk_king_graph(n, k):
grids = []
for i in range(1, k + 1):
for j in range(1, n):
grids.append((i + (j - 1) * k, i + j * k))
if i < k:
grids.append((i + (j - 1) * k, i + j * k + 1))
if i > 1:
grids.append((i + (j - 1) * k, i + j * k - 1))
for i in range(1, k * n, k):
for j in range(1, k):
grids.append((i + j - 1, i + j))
return grids
def A339098(n, k):
universe = make_nXk_king_graph(n, k)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles()
return cycles.len()
print([A339098(j + 2, i - j + 2) for i in range(9 - 1) for j in range(i + 1)])
A220638
Number of ways to reciprocally link elements of an n X n array either to themselves or to exactly one king-move neighbor.
Original entry on oeis.org
1, 1, 10, 369, 92801, 128171936, 1040315976961, 48590896359378961, 13140746227808545282304, 20540255065209806005525289313, 185661218973084382181156348510614065, 9703072851259276652446200332793680010752000, 2932144456272256572796083896528773941130429279461761
Offset: 0
Some solutions for n=3 0=self 1=nw 2=n 3=ne 4=w 6=e 7=sw 8=s 9=se (reciprocal directions total 10)
..8..6..4....0..9..7....6..4..0....0..6..4....9..0..8....6..4..0....8..0..0
..2..7..0....9..3..1....8..6..4....6..4..7....0..1..2....0..0..8....2..6..4
..3..6..4....0..1..0....2..0..0....0..3..0....0..0..0....0..0..2....6..4..0
-
b:= proc(n, l) option remember; local d, f, k;
d:= nops(l)/2; f:=false;
if n=0 then 1
elif l[1..d]=[f$d] then b(n-1, [l[d+1..2*d][], true$d])
else for k to d while not l[k] do od; b(n, subsop(k=f, l))+
`if`(k1 and l[k+d+1],
b(n, subsop(k=f, k+d+1=f, l)), 0)+
`if`(k>1 and n>1 and l[k+d-1],
b(n, subsop(k=f, k+d-1=f, l)), 0)+
`if`(n>1 and l[k+d], b(n, subsop(k=f, k+d=f, l)), 0)+
`if`(k b(n, [true$(n*2)]):
seq(a(n), n=0..10); # Alois P. Heinz, Jun 03 2014
-
b[n_, l_] := b[n, l] = Module[{d, f, k}, d = Length[l]/2; f = False; Which[ n == 0, 1, l[[1 ;; d]] == Array[f&, d], b[n - 1, Join [l[[d+1 ;; 2d]], Array[True&, d]]], True, For[k = 1, !l[[k]], k++]; b[n, ReplacePart[l, k -> f]] + If[k < d && n > 1 && l[[k + d + 1]], b[n, ReplacePart[l, k | k + d + 1 -> f]], 0] + If[k > 1 && n > 1 && l[[k + d - 1]], b[n, ReplacePart[l, k | k + d - 1 -> f]], 0] + If[n > 1 && l[[k + d]], b[n, ReplacePart[l, k | k + d -> f]], 0] + If[k < d && l[[k + 1]], b[n, ReplacePart[l, k | k + 1 -> f]], 0]]]; a[n_] := b[n, Array[True&, 2n]]; Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 12}] (* Jean-François Alcover, Feb 01 2017, after Alois P. Heinz *)
A361171
Number of chordless cycles in the n X n king graph.
Original entry on oeis.org
0, 0, 1, 13, 197, 4729, 156806, 7035482, 505265569, 82612843683, 33651820752580, 23922790371389972, 25614853328191562332, 43322613720440154974138, 128405885225433787867253690, 738840753928503040569961869076, 8481241718402438554921627740308746, 179685856472407342498054958799766397100
Offset: 1
Showing 1-5 of 5 results.
Comments