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