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$