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.

I've recently watched a fun video about some snakes made up of modules and how we can think about the way they are arranged as follows.

  1. We have a "snake" composed of $n$ modules, including head and tail. That is:

enter image description here

  1. Each joint (?) is flexible so that we can turn it either $0º$ or $90º$ degress, both right or left. For example, with a $3-\text{snake}$ we can make the following (among others):

enter image description here

  1. Suppose we start at the black dot and we place the snake, coding each $n$ placements in a string of letters. We first code the direction of the first module, as $N$, $E$, $W$ or $S$, and from there on, we note wether we're placing the module at $0º$ (straight), $90º$ (leftwards) or $-90º$, (rightwards). As an example, let's code the four configurations above (left to right, left to right)

$$E:SS$$ $$E:RR$$ $$E:SR$$ $$E:RL$$

  1. Suppose also, that the snake can't run into itself, that is: from $n\geq4$, we can't have a string composed of $n-1$ $R$s or $n-1$ $L$s, since that will mean our snake will run into itself.

Given this rules, can we combinatorially find a way of computing the possible configurations of an $n-\text{snake}$? I guess we can just leave the orientation aside and then multiply by $4$. As an example, I leave the configurations for $n=3$ and starting $E:$, which are:

enter image description here

This means there are a total of $4 \times 9 = 36$ configurations for $n=3$ if I'm not wrong.


It seems easier to compute $\mathcal{S}(4)$ if we use the coding. This gives

$$\eqalign{ & SSS - SSR - SSL \cr & SLR - SLS - SLL \cr & SRR - SRL - SRS \cr} $$

$$\eqalign{ & RRS - RRL - \color{red}{RRR} \cr & RSS - RSL - RSR \cr & RLR - RLS - RLL \cr} $$

$$\eqalign{ & LLR - LLS - \color{red}{LLL} \cr & LRL - LRR - LRS \cr & LSR - LSL - LSS \cr} $$

I'll write some values, without multiplying by $4$:

$$\mathcal{S}(1)=3^0=1$$ $$\mathcal{S}(2)=3^1=3$$ $$\mathcal{S}(3)=3^2=9$$ $$\mathcal{S}(4)=3^3-2=25$$ $$\mathcal{S}(5)=3^4-10=71$$

We can say that

$$\mathcal{S}(n)=3^n-\mathcal{R}(n)$$

The reminder is actually the important thing here. We have that for the first 5 cases

$$\mathcal{R} = 0,0,0,2,10$$

The reminder of $n=5$ is built up from the case $n=4$ since we just consider the next step. In the first one we set apart

$$RRR$$ $$LLL$$

So now we consider the following "products":

$$\{R,S,L\} \times RRR= RRRR , SRRR, LRRR$$

$$\{R,S,L\} \times LLL= RLLL , SLLL, LLLL$$

$$ LLL \times \{R,S\} = LLLR , LLLS$$

$$ RRR \times \{L,S\} = RRRL, RRRS$$

Thus we have that

$$\mathcal{R}(4)\times 5 = \mathcal{R}(5)$$

The next remainder will be

$$\mathcal{R}(6)=54$$

Why? We take $\mathcal{R}(5)$ as a base, and worry about the palindromes, which are

$$L???L$$ Where we fill in with a triad. So we have

$$\eqalign{ & RRRR \cr & RRRL \cr & RRRS \cr} $$

$$\eqalign{ & RLLL \cr & SLLL \cr & LLLL \cr} $$

$$\eqalign{ & SRRR \cr & LRRR \cr} $$

$$\eqalign{ & LLLR \cr & LLLS \cr} $$

We apply $\{R,L,S\}\times$ to the left side and get $30$ more cases. And for the right, we apply $\{R,L,S\}\times$ on the right to those that can't be turned into a plaindrome, to get $4$ more cases, plus $2\times$ the $6$ posible palindromes. We get a total of

$$10\times 3+3 \times 4 +2\times6 = 54$$

Thus

$$\mathcal{S}(6)=3^5-54=189$$

share|improve this question
3  
+1: Nice question! –  Aryabhata Mar 3 '12 at 0:04
    
To peter: The picture is not shown on my computer! –  Victor Mar 10 '12 at 21:41
add comment

1 Answer

up vote 9 down vote accepted

Although this might feel very simple and playful, this is an unsolved problem that has been considered. In particular, this is equivalent to the following problem:

Start at the origin in the plane. How many self-avoiding 'walks' are there on the integer lattice of prescribed length? Some results include this paper, which relates the number of walks in a strip with fibonacci numbers. Equivalently, the number of snakes that are 'very tall' (so that they're in a strip) is related to the fibonacci numbers.

Madras and Slade have a book, The Self-Avoiding Walk dedicated largely to this problem.

share|improve this answer
2  
+1: That was quick! Thanks for the link and the name of the book. –  Aryabhata Mar 3 '12 at 0:04
add comment

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.