Generating function of number of assignments with constraints

Question

Suppose I have $N$ boxes on a ring. Each box can be assigned number $0$ or $1$. Neighboring boxes can not have both $1$. so the assignment $0000$ is allowed, but the assignment $0110$, $1001$ etc are not allowed (remember the sequence is defined on a ring, so the first element and the last one are adjacent). How to find a generating function $G(q)$ that gives the number of allowed assignments $t_N$ such that $$G(q)=\sum_{N=0}^{\infty} t_N q^N$$

Thanks in advance.

Answer 1

These numbers have a close relationship to Fibonacci numbers. Indeed, if $f_n$ denotes the number of $\{0,1\}$ sequences of length $n$ which have no two consecutive $1$'s, then $f_n$ is the $n$th Fibonacci number (starting with $f_0=1,f_1=2$.

To see the relationship between $t_n$ and $f_n$, consider a $\{0,1\}$ ring of length $n$ and consider the two possibilities for the first entry:

• If the first entry is a $1$, then both the second and last entries must be $0$'s. Thus, upon deleting these three entries, we're left with a $\{0,1\}$ sequence of length $n-3$ which has no two consecutive $1$'s. Furthermore, this process is easily reversed, so there are precisely $f_{n-3}$ rings of this type.
• If the first entry is a $0$, then we have no restriction on the second and last entries. Hence, removing the first entry, we're left with a $\{0,1\}$ sequence of length $n-1$ which has no two consecutive $1$'s. Since this process is also reversible, we have precisely $f_{n-1}$ rings of this type.

Putting this together, we have $t_n=f_{n-1}+f_{n-3}$ for $n\geq 3$. We can also explicitly determine $t_0=1,t_1=2,t_2=3$. Now, let $F(q)=\sum_n f_nq^n$ be the generating function for our Fibonacci sequence. We can compute, $$ G(q)=\sum_n t_nq^n=t_0+t_1q+t_2q^2+\sum_{n\geq 3}(f_{n-1}+f_{n-3})q^n=1+2q+3q^2+q(F(q)-f_0-f_1q)+q^3F(q)=1+q+q^2+(q+q^3)F(q). $$