# 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			

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

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.			

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

Let us generalize equation .

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

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

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

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})		 
N(xr(ru)^kr) = N(x) + N(xr(ru)^{k})		 

Apply transform to  and  to give:

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

Simple Calculations:

N(xrr) = N(xr) + N(x)			
N(xuu) = N(xu) + N(x)			

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

N(xrru) = N(x) + N(xrr)		
N(xuur) = N(x) + N(xuu)		

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  and , we get:
N(xr(ru)^{k})  = N(x) + N(xrr(ur)^{k-1})	 
N(xr(ru)^{k}r) = N(x) + N(xr(ru)^{k})		 

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)		
N(xu(ur)^k) = (2 * k * N(x)) + N(xu)		

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

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 :

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

From  and [6.1]
N(e(ru)^k) = 1 + N(e(ru)^{k-1}r)	
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			

x=y transform:

N(e(ur)^k) = 2k + 2			

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

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

```

## Summarize:

```	N(e) = 2					
N(er) = 3					
N(eu) = 3					
N(e(ru)^k) = 2k + 2				
N(e(ur)^k) = 2k + 2				
N(er(ur)^k) = 2k + 3				
N(eu(ru)^k) = 2k + 3				
N(xrr) = N(xr) + N(x)				
N(xuu) = N(xu) + N(x)				
N(xrru) = N(x) + N(xrr)				
N(xuur) = N(x) + N(xuu)				
N(xr(ru)^k) = (2 * k * N(x)) + N(xr)		
N(xu(ur)^k) = (2 * k * N(x)) + N(xu)		
N(xr(ru)^{k}r) = ((2k+1) * N(x)) + N(xr)	
N(xu(ur)^{k}u) = ((2k+1) * N(x)) + N(xu)	
```

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