4

This is the Stern-Brocot tree, which is bijective to the positive rationals.


2

$ \def\w{\text{weight}} \def\C{\mathcal{C}} $ Here is the solution using the cluster method. The generating function is $$ f(s)=\frac1{1-4s-\w(\C)}, $$ so we need to find $\w(\C)$. The set of bad words is $\{ab,ba\}$. Proceeding as in the paper, we get $$ \w(\C[ab])=-s^2-s\cdot \w(C[ba])\\ \w(\C[ba]) = -s^2-s\cdot \w(C[ab]) $$ Furthermore, $\w(\C)=\w(\C[ab])+...


2

I do not know about the Goulden-Cluster method, but I can explain why $a_n\neq 4a_{n-1}-2a_{n-2}$. Let us call the strings counted by $4a_{n-1}$ type I, and the strings counted by $2a_{n-2}$ type II. That is, Type I: (valid string of length $n-1$) + (any single letter) Type II: (valid string of length $n-2$) + ($ab$ or $ba$) The subtraction $4a_{n-1}-2a_{...


1

Claude Leibovici's method is good, but if you want the generating function, you basically found it already. Just solve the equation, $$ F(x) - 2 = 3x F(x) + \frac{x}{1-x} \implies F(x) = \frac{2-x}{(1-x)(1-3x)} . $$ (At this point you instead seem to have substituted $F(x) = \frac{1}{1-x}$ in your working, which was wrong). Now, if we want to extract ...


1

Hint To solve $$a_{n} = 3a_{n-1} + 1$$ since the problem is the constant, let $a_n=b_n+k$ and replace $$b_n+k=3b_{n-1}+3k+1$$ So, make $$k=3k+1\implies k=-\frac 12\implies b_n= 3b_{n-1} $$ which is simple


1

You are almost there. Now try to do $L_i \leftarrow L_i-L_{n+1}$ for all $1\leq i \leq n$. Where $L_i$ denotes the $i$-th row. By substracting the rows you will have the opportunity to make the missing factors appear as you did with the columns, and you will end up with only $0$s in the last column except at the bottom. Indeed, for all $1\leq i,j \leq n$ you ...


Only top voted, non community-wiki answers of a minimum length are eligible