login
Number of self-avoiding closed paths in the n X n grid graph which pass through all vertices on four (left, right, upper, lower) sides of the graph.
2

%I #17 Apr 07 2020 10:38:14

%S 1,1,11,191,11346,2002405,1112939654,1878223479450

%N Number of self-avoiding closed paths in the n X n grid graph which pass through all vertices on four (left, right, upper, lower) sides of the graph.

%C a(11) = 152567999801505122456.

%e a(2) = 1;

%e +--+

%e | |

%e +--+

%e a(3) = 1;

%e +--+--+

%e | |

%e + +

%e | |

%e +--+--+

%e a(4) = 11;

%e +--+--+--+ +--+--+--+ +--+--+--+

%e | | | | | |

%e +--*--* + +--* *--+ +--* +

%e | | | | | |

%e +--*--* + +--* *--+ +--* +

%e | | | | | |

%e +--+--+--+ +--+--+--+ +--+--+--+

%e +--+--+--+ +--+--+--+ +--+--+--+

%e | | | | | |

%e + *--*--+ + *--* + + *--+

%e | | | | | | | |

%e + *--*--+ + * * + + *--+

%e | | | | | | | |

%e +--+--+--+ +--+ +--+ +--+--+--+

%e +--+--+--+ +--+--+--+ +--+ +--+

%e | | | | | | | |

%e + + + + + *--* +

%e | | | | | |

%e + *--* + + + + *--* +

%e | | | | | | | | | |

%e +--+ +--+ +--+--+--+ +--+ +--+

%e +--+ +--+ +--+ +--+

%e | | | | | | | |

%e + *--* + + * * +

%e | | | | | |

%e + + + *--* +

%e | | | |

%e +--+--+--+ +--+--+--+

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o import graphillion.tutorial as tl

%o def A333759(n):

%o universe = tl.grid(n - 1, n - 1)

%o GraphSet.set_universe(universe)

%o cycles = GraphSet.cycles()

%o points = [i for i in range(1, n * n + 1) if i % n < 2 or ((i - 1) // n + 1) % n < 2]

%o for i in points:

%o cycles = cycles.including(i)

%o return cycles.len()

%o print([A333759(n) for n in range(2, 10)])

%Y Main diagonal of A333758.

%Y Cf. A333466.

%K nonn,more

%O 2,3

%A _Seiichi Manyama_, Apr 04 2020