# A combinatorial problem of counting path weights with a special symbolic binary tree

Consider two symbols, $$X$$ and $$Y$$.

Symbol $$X$$ spawns $$X$$ and $$Y$$ -- think of the spawning as a binary tree rooted in $$X$$ with two leaves. The path weight for leaf $$X$$ is $$a$$ and that for leaf $$Y$$ is $$b$$.

Symbol $$Y$$ also spawns $$X$$ and $$Y$$ -- however, the path weight for leaf $$X$$, in this case, is $$c$$ and that for leaf $$Y$$ is $$d$$.

Let us start with symbol $$X$$ and consider another binary tree.

Each level of the tree is made of children spawned by the previous level.

That is, the root, or the first level, will be $$X$$.

The next level will be $$X$$ and $$Y$$, with the weight of the path connecting $$X$$ (of the second level) to $$X$$ (the root) being $$a$$ and that connecting $$Y$$ to the root $$X$$ being $$b$$.

Similarly, the next level will have $$X$$ (path weight upto the root being $$a^{2}$$), $$Y$$ (path weight upto the root being $$ab$$), $$X$$ (path weight upto the root being $$bc$$), and $$Y$$ (path weight upto the root being $$bd$$.)

As is evident, the weights of different paths get multiplied when counting the weight of a path till the root. Then, the final weights are added together to get the total weight of a symbol.

Additionally, as is also evident, the first ($$X$$, $$Y$$) pair of this level was spawned from $$X$$ (of the previous level) and the second pair was spawned from $$Y$$ (of the previous level.)

So, the total weight for symbol $$X$$ in this level will be $$a^{2} + ab$$ and the total weight for symbol $$Y$$ will be $$bc + bd$$.

Let us say the binary tree has $$k$$ levels.

What is the total weight of symbol $$X$$ and symbol $$Y$$ after the $$k^{\text{th}}$$ level?

By using induction from the leafs to the root : Lets $$x_k$$ be the weight of a tree of depth $$k$$ rooted on $$X$$, and $$y_k$$ same but rooted on $$Y$$.
We have the following recurrence : $$x_{k+1} = ax_k + by_k$$ $$y_{k+1} = cx_k + dy_k$$ $$x_0 = y_0 = 1$$ which is a system of linear homogeneous recurrences, and can be solved the classic way.
• @RandomMatrices You can write $u_k = (x_k, y_k)$, $u_{k+1} = Au_k$, with $A = \left(\begin{matrix} a &c\\b &d\end{matrix}\right)$, which gives $u_n = Au_0$, so you need to compute $A^n$. $A^n = P^{-1}D^nP$ if $A$ is diagonalizable. Cayley-Hamilton works in a more general way. For the 2x2 case: math.stackexchange.com/questions/3478394/… Mar 30, 2022 at 15:49