Number of unique figures in a grid with $n$ lines drawn without lifting the pen

41 Views Asked by At

The problem is to find the number of distinct figures drawn from $n$ straight lines of fixed length in a grid, which I call snakes. Reflections and rotations of the snakes are identified, so the problem is to find the number of unique snakes. The snakes for $n = 1,2,3$ are illustrated below enter image description here

Set $s(n)$ to be the number of unique figures with $n$ lines. I have found the first couple of values, but I couldn't find any pattern. I also couldn't see that it was mentioned in the online encyclopedia of integer sequences. My question is if there is any way to find a formula for $s(n)$? Maybe there are some other connections one could make, for example to graph theory (I think the problem is equivalent to finding the number of Eulerian planar graphs with $n$ edges, only cycles of even length and the number of neighbors of a node is less than 4). Below is table of values of the first few values

$$ \begin{array}{c|c} n & f(n) \\ \hline 1 & 1 \\ \hline 2 & 2 \\ \hline 3 & 4 \\ \hline 4 & 10 \\ \hline 5 & 23 \end{array}$$