# Combinatorics and snakes.

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:

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):

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:

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

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

## 1 Answer

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.

-
+1: That was quick! Thanks for the link and the name of the book. –  Aryabhata Mar 3 '12 at 0:04