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.
- We have a "snake" composed of $n$ modules, including head and tail. That is:
- 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):
- 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$$
- 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$$