Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 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
share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
5  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.