6
$\begingroup$

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

for a three-link snake

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

I don't know a closed 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 

1 Answers 1

5

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.

  • 0
    Thanks, Hendrik and Brian. The article by Brian Hayes is quite interesting.2012-12-05