Branching of Fibonacci Words     misc

Young-Fibonacci Lattice Explorer

The Young-Fibonacci lattice $\text{YF}$ is the union of all sets $\text{YF}_n$, $n \geq 0$, where $\text{YF}_n$ is the set of all Fibonacci words (binary words whose digits lie in $\{1,2\}$) of weight $n$.

In this lattice, a Fibonacci word $w$ in $\text{YF}_n$ is connected to $w'$ in $\text{YF}_{n+1}$ if $w'$ can be obtained from $w$ by one of the following operations:

• F1: $w' = 1w$ (prepend 1 to $w$)
• F2: $w' = 2^{k+1}v$ if $w = 2^k1v$ for some $k \geq 0$ and an arbitrary Fibonacci word $v$
• F3: $w' = 2^{\ell}12^{k-\ell}v$ if $w = 2^kv$ for some $k \geq 1$ and an arbitrary Fibonacci word $v$, where $\ell = 1,...,k$

Dimension formula: For $w \in \text{YF}$, the dimension $\dim(w)$ counts the number of saturated chains from $\emptyset$ to $w$ and obeys the recursion:

• $\dim(\emptyset) = 1$
• $\dim(1v) = \dim(v)$ for a Fibonacci word $v$
• $\dim(2v) = (\text{weight}(v) + 1) \times \dim(v)$ for a Fibonacci word $v$

where $\text{weight}(v)$ is the sum of digits in $v$.

For example, $\dim(22121) = 70$ calculated as: $7 \times 5 \times 2 = 70$, where:

• First 2: tail is "$2121$" with weight 6, so factor is $6+1 = 7$
• Second 2: tail is "$121$" with weight 4, so factor is $4+1 = 5$
• Third 2: tail is "$1$" with weight 1, so factor is $1+1 = 2$