# Thoughts on Snakes

Document history:
*hwc 2003-09-13 - created.
*hwc 2003-09-14 - added section on Fibonacci sequences.

Apology: this document is seriously lacking in digrams. Sorry.

## Labeling Snakes

```We need to define a way to label snakes.

Also define function N(x) = the number of perfect matchings of snake
x.
N : {snakes} -> Z+

o---o
| e |		The most basic snake is called e.
o---o		N(e) = 2			[1]

o---o---o
| e | r |	The next snake is er
o---o---o	N(er) = 3			[2]

o---o
| u |		Here is snake eu, made by adding a box on top of
o---o		the e snake.
| e |
o---o		N(eu) = 3.			[3]

o---o
| u |	Here is snake eru.
o---o---o	N(eru) = 1 + N(er).        [4]
| e | r |	       = 1 + 3
o---o---o	       = 4

Let us generalize equation [4].

N(e(ru)^k) = 1 + N(e(ru)^{k-1}r)	[5]

You can rotate any snake along the y=x line and switch all u's for
r's.  Applying this transform to equation [5] gives

N(e(ur)^k) = 1 + N(e(ur)^{k-1}u)	[6]

Another case:  erurururur or eururururu.  It's simple to see that:

N(er(ur)^k) = 1 + N(e(ru)^k)	  	[6.1]
N(eu(ru)^k) = 1 + N(e(ur)^k)		[6.2]

But what if we have a snake of the form xurururur, where x is any
snake?   (We're trying to recursively calculate the matchings of any
snake.) We can not directly calculate N(xurururur).

Instead we can calculate N(xr(ru)^k) and N(xr(ru)^{k}r).  (k>0)

N(xr(ru)^k) = N(x) + N(xrr(ur)^{k-1})		 [7]
N(xr(ru)^kr) = N(x) + N(xr(ru)^{k})		 [8]

Apply transform to [7] and [8] to give:

N(xu(ur)^k) = N(x) + N(xuu(ru)^{k-1})		 [9]
N(xu(ur)^ku) = N(x) + N(xr(ur)^{k})		 [10]

Simple Calculations:

N(xrr) = N(xr) + N(x)			[11]
N(xuu) = N(xu) + N(x)			[12]

[11] and [12] are generalized forms of the Fibonacci recurrance.
Since, in general, x can be anything, then the snake sequence

F = {x,xr,xrr,xrrr,xrrrr,xrrrrr,...}

is like a fibonacci sequence with odd starting conditions.

f_1 = N(x)
f_2 = N(xr)
f_k = f_{k-1} + f_{k-2}

where f_k = N(F_k), the Number of perfect matchings of the kth snake
in the sequence F.  Of course, if x=e, then f_1=2 and f_2=3, giving
the usual fibonacci sequence.

Special case of [7] and [9]:

N(xrru) = N(x) + N(xrr)		[13]
N(xuur) = N(x) + N(xuu)		[14]

These equations should give us the tools to recursively calculate N(x)
for any snake.

To do:  prove that there aren't any cases that we are forgetting.

```

## Proof: (?)

```Any snake string ends in 'e', 'er', 'eu', 'rr', 'uu', 'ur'
or 'ru'.  Do my rules apply to *all* cases?

Snake strings always get shorter when you apply a rule.  So if
a string is n chars long, you only need to apply rules at most
n times.

```

## Simplification:

```From [7] and [8], we get:
N(xr(ru)^{k})  = N(x) + N(xrr(ur)^{k-1})	 [7]
N(xr(ru)^{k}r) = N(x) + N(xr(ru)^{k})		 [8]

N(xr(ru)^{k})  = N(x) + N(xrr(ur)^{k-1})
N(xrr(ur)^{k-1}) = N(x) + N(xr(ru)^{k-1})

N(xr(ru)^{k}) = (2 * N(x)) + N(xr(ru)^{k-1})

So, we have shown that:

N(xr(ru)^k) = (2 * k * N(x)) + N(xr)		[15]
N(xu(ur)^k) = (2 * k * N(x)) + N(xu)		[16]

Doing it the other way:
N(xr(ru)^{k}r) = N(x) + N(xr(ru)^{k})		 [8]
N(xr(ru)^{k})  = N(x) + N(xrr(ur)^{k-1})	 [7]

N(xr(ru)^{k}r) = N(x) + N(xr(ru)^{k})
N(xr(ru)^{k})  = N(x) + N(xr(ru)^{k-1}r)

N(xr(ru)^{k}r) = (2 * N(x)) + N(xr(ru)^{k-1}r)
And:
N(xr(ru)^{k}r) = (2 * k * N(x)) + N(xrr)

Apply [11]:

N(xr(ru)^{k}r) = (2 * k * N(x)) + N(xr) + N(x)
N(xr(ru)^{k}r) = ((2k+1) * N(x)) + N(xr)	[17]
N(xu(ur)^{k}u) = ((2k+1) * N(x)) + N(xu)	[18]

From [5] and [6.1]
N(e(ru)^k) = 1 + N(e(ru)^{k-1}r)	[5]
N(er(ur)^k) = 1 + N(e(ru)^k)	  	[6.1]

N(e(ru)^k) = 1 + N(er(ur)^{k-1})
N(er(ur)^{k-1}) = 1 + N(e(ru)^{k-1})

N(e(ru)^k) = 2 + N(e(ru)^{k-1})

Simplify, giving:

N(e(ru)^k) = 2k + N(e)
N(e(ru)^k) = 2k + 2			[19]

x=y transform:

N(e(ur)^k) = 2k + 2			[20]

From [5] and [6.1]:
N(er(ur)^k) = 1 + N(e(ru)^k)	  	[6.1]
N(e(ru)^k) = 1 + N(e(ru)^{k-1}r)	[5]

N(er(ur)^k) = 2 + N(er(ur)^{k-1})
N(er(ur)^k) = 2k + N(er)
N(er(ur)^k) = 2k + 3			[21]
N(eu(ru)^k) = 2k + 3			[22]

```

## Summarize:

```	N(e) = 2					[1]
N(er) = 3					[2]
N(eu) = 3					[3]
N(e(ru)^k) = 2k + 2				[19]
N(e(ur)^k) = 2k + 2				[20]
N(er(ur)^k) = 2k + 3				[21]
N(eu(ru)^k) = 2k + 3				[22]
N(xrr) = N(xr) + N(x)				[11]
N(xuu) = N(xu) + N(x)				[12]
N(xrru) = N(x) + N(xrr)				[13]
N(xuur) = N(x) + N(xuu)				[14]
N(xr(ru)^k) = (2 * k * N(x)) + N(xr)		[15]
N(xu(ur)^k) = (2 * k * N(x)) + N(xu)		[16]
N(xr(ru)^{k}r) = ((2k+1) * N(x)) + N(xr)	[17]
N(xu(ur)^{k}u) = ((2k+1) * N(x)) + N(xu)	[18]
```

## Code

I've written out this algorithm in perl. Here is all of the output for snales of length 2 to 11: counted-snakes.txt. Here is example output:

```[hal@ups 2003]\$ perl snake-counting 'e'
N(e) = 2
[hal@ups 2003]\$ perl snake-counting 'er'
N(er) = 3
[hal@ups 2003]\$ perl snake-counting 'eu'
N(eu) = 3
[hal@ups 2003]\$ perl snake-counting 'eru'
N(eru) = 4
[hal@ups 2003]\$ perl snake-counting 'errr'
N(errr) = 8
[hal@ups 2003]\$ perl snake-counting 'erururr'
N(erururr) = 13
[hal@ups 2003]\$ perl snake-counting 'erurururrurur'
N(erurururrurur) = 49
[hal@ups 2003]\$ perl snake-counting 'er'
N(er) = 3
[hal@ups 2003]\$ perl snake-counting 'err'
N(err) = 5
[hal@ups 2003]\$ perl snake-counting 'errr'
N(errr) = 8
[hal@ups 2003]\$ perl snake-counting 'errrr'
N(errrr) = 13
[hal@ups 2003]\$ perl snake-counting 'errrrr'
N(errrrr) = 21
[hal@ups 2003]\$ perl snake-counting 'errrrrr'        A
N(errrrrr) = 34
[hal@ups 2003]\$ perl snake-counting 'errrrrrr'
N(errrrrrr) = 55
[hal@ups 2003]\$ perl snake-counting 'errrrrrrr'
N(errrrrrrr) = 89
[hal@ups 2003]\$ perl snake-counting 'errrrrrrrr'
N(errrrrrrrr) = 144
[hal@ups 2003]\$ perl snake-counting 'errrrrrrrrr'
N(errrrrrrrrr) = 233
[hal@ups 2003]\$ perl snake-counting 'errrrrrrrrrr'
N(errrrrrrrrrr) = 377
[hal@ups 2003]\$ perl snake-counting 'errrrrrrrrrrr'
N(errrrrrrrrrrr) = 610
```

BACK