login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of self-avoiding walks in the n X 2 grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.
3

%I #29 Mar 26 2020 07:12:05

%S 1,8,29,80,195,444,969,2056,4279,8788,17885,36176,72875,146412,293649,

%T 588312,1177855,2357188,4716133,9434336,18871091,37744988,75493209,

%U 150990120,301984455,603973684,1207952749,2415911536,4831829819,9663667148,19327342625,38654694456,77309399055,154618809252

%N Number of self-avoiding walks in the n X 2 grid graph which start at any of the n vertices on left side of the graph and terminate at any of the n vertices on the right side.

%F Conjecture: a(n) = (27*2^n - n^3 - 26*n - 24)/3.

%F Conjecture: G.f.: x*(1+2*x-5*x^2+2*x^3+2*x^4)/((1-x)^4*(1-2*x)).

%e a(1) = 1;

%e +--+

%e a(2) = 8;

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

%e | | | |

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

%e -------------------------

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

%e | | | |

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

%e a(3) = 29;

%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 | | | | |

%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 A(start, goal, n, k):

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

%o GraphSet.set_universe(universe)

%o paths = GraphSet.paths(start, goal)

%o return paths.len()

%o def A333509(n, k):

%o if n == 1: return 1

%o s = 0

%o for i in range(1, n + 1):

%o for j in range(k * n - n + 1, k * n + 1):

%o s += A(i, j, k, n)

%o return s

%o def A333510(n):

%o return A333509(n, 2)

%o print([A333510(n) for n in range(1, 20)])

%Y Column k=2 of A333509.

%K nonn

%O 1,2

%A _Seiichi Manyama_, Mar 25 2020