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.
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.
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.
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]
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]
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