# How many unique shapes can be created from a wiggly snake of $k$ links?

In one of her videos (at 0:46) Vihart muses about this problem. Given a wiggly plastic snake with $k$ links, how many valid and unique shapes can be created out of the snake.

A shape is valid if it does not contain a loop. For similarity, both rotational and reflections symmetry is allowed.(consider head and tail like any other link)

For example,

  _          _
_| |   and  | |_ are same

_         |_
_| |   and   _| are also same


and so on.

So, for a snake with two links there are only two possible shapes

_ _   and  _|


                    _    _
_ _ _  , _ _ | , _ |  ,  _|


I don't know a close form mathematical expression for $f(k)$, the number of uniques shapes that can be created with a snake of $k$ links. But I did write a program to find $f(k)$. The numbers I got for different values of $k$ are given below. I was wondering if anyone can comment on the correctness of the numbers or know of a closed form expression for $f(k)$.

links  shapes
0       0
1       1
2       2
3       4
4       9
5       22
6       56
7       147
8       388
9       1047
10      2806
11      7600
12      20437
13      55313
14      148752
15      401629
16      1078746

-

Check the The On-Line Encyclopedia of Integer Sequences! Great fun ...

A037245 Number of unrooted self-avoiding walks of n steps on square lattice.

Exactly matches your numbers, but no closed formula is given.

-
And this article from 1998 by Brian Hayes gives what looks like a pretty good survey. (The link to it in the OEIS entry is broken.) –  Brian M. Scott Dec 4 '12 at 1:14
Thanks, Hendrik and Brian. The article by Brian Hayes is quite interesting. –  Sumit Dec 5 '12 at 4:25