A398323 - OEIS

A398323

Number of self-avoiding walks between two antipodal vertices on a hexagon of size n in the triangular grid.

21, 59089, 55056028411, 9121714721833768523, 315055996293473805066942838711, 2285976866724746492568710262010414731842865, 3488397016395208899750541434350011700838130040938298074129

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,1

COMMENTS

On the Cartesian grid this can be defined as the lattice T = {(x,y): 0 <= x,y <= 2*n and |x - y| <= n}. We consider the number of self avoiding walks between opposite corners.

The number of vertices and edges in the graph are A003215(n) and A045945(n) respectively.

LINKS

Table of n, a(n) for n=1..7.

EXAMPLE

The graphs for n = 1 and 2 are illustrated below:

o---o---o

/ \ / \ / \

o---o o---o---o---o

/ \ / \ / \ / \ / \ / \

o---o---o o---o---o---o---o

\ / \ / \ / \ / \ / \ /

o---o o---o---o---o

\ / \ / \ /

o---o---o

For n = 1, the graph is the wheel graph W_7, whose vertices may be considered as a hexagon and an internal point. The number of self-avoiding walks between two opposite vertices of the hexagon is 21. If the outer vertices are labeled 1,2,3,4,5,6 and the internal vertex 7, then walks between say 1 and 4 are: 174, 1734, 1754, 17234, 17654, 1274, 12754, 127654, 12734, 1234, 12374, 1237654, 123754, 1674, 16734, 167234, 16754, 1654, 16574, 1657234, 165734.

PROG

(Python)

from graphillion import GraphSet

import networkx as nx

verts = {(x, y) for x in range(2*N+1) for y in range(2*N+1) if abs(x-y)<=N}

G = nx.Graph()

G.add_nodes_from(verts)

for (x, y) in verts:

adj = {(x+1, y), (x-1, y), (x, y+1), (x, y-1), (x+1, y+1), (x-1, y-1)}.intersection(verts)

G.add_edges_from([((x, y), a) for a in adj])

GraphSet.set_universe(G.edges)

paths = GraphSet.paths((0, 0), (2*N, 2*N))