Generating Function of a combinatorial Problem

Question

I am trying to solve the following question: Consider the alphabet $\{A,B,C,1,2,3,4\}$. Let $a_n$ denote the number of words of length $n$ which do not contain 3 successive numbers. Find the generating function $A(z)=\sum \limits _{n\geq 0}a_nz^n$.

To avoid confusion, I will say that $A,B,C$ are letters and letters of a word in the mathematical sense are elements.

Now first I looked for a recursive formula of the problem. For a word of length $n-1$, we can always append any of the 3 letter. This gets us a summand of the form $a_{n-1}\cdot 3$

If we want to append a number, we have to consider 2 cases:

1. case: the last element of a word of length n-1 is a letter. Then we can append any number. This obtains us a summand of $a_{n-2}\cdot 3\cdot 4$.

2. case: the last element of a word of length n-1 is a number and the second last is a letter. Then we can also append a number and we get a summand of $a_{n-3}\cdot 3\cdot 4\cdot 4$.

Those are all cases and our recursion is

$a_n=3a_{n-1}+12a_{n-2}+48a_{n-3}$

Now we need a few initial values and find $a_0=1, \ a_1=7, \ a_2=49 $.

We calculate

$A(z)\\=\sum \limits _{n\geq 0}a_nz^n\\=a_0+a_1z+a_2z^2+\sum \limits _{n\geq 3}a_nz^n\\=1+7z+49z^2+3z(\sum \limits _{n\geq 0}a_nz^n-7z-1)+12z^2(\sum \limits _{n\geq 0}a_nz^n-1)+48z^3\sum \limits _{n\geq 0}a_nz^n\\=1+4z+16z^2+A(z)(3z+12z^2+48z^3)$

So all in all

$A(z)=\frac{1+4z+16z^2}{1-3z-12z^2-48z^3}$

The calculations up to this point should all be correct. But how do I proceed now? I tried to integrate the function and use the generating function of the natural logarithm, but it gets a really big mess. Is there another way?

Sincerely slinshady

Answer 1

The recurrence relation and the generating function look fine.

We can use the geometric series expansion and obtain

\begin{align*} \color{blue}{[z^n]A(z)}&=[z^n]\frac{1+4z+16z^2}{1-3z(1+4z+16z^2)}\\ &=[z^n]\sum_{j=0}^\infty(3z)^j(1+4z+16z^2)^{j+1}\\ &=\sum_{j=0}^n3^j[z^{n-j}]\sum_{k=0}^{j+1}\binom{j+1}{k}(4z)^k(1+4z)^k\tag{1}\\ &=\sum_{j=0}^n3^{n-j}[z^j]\sum_{k=0}^{n-j+1}\binom{n-j+1}{k}(4z)^k(1+4z)^k\tag{2}\\ &=\sum_{j=0}^n3^{n-j}\sum_{k=0}^{\min\{j,n-j+1\}}\binom{n-j+1}{k}4^k[z^{j-k}]\sum_{l=0}^k\binom{k}{l}(4z)^l\tag{3}\\ &\color{blue}{=3^n\sum_{j=0}^n\sum_{k=0}^{\min\{j,n-j+1\}}\left(\frac{4}{3}\right)^j\binom{n-j+1}{k}\binom{k}{j-k}}\tag{4} \end{align*}

Comment:

• In (1) we use the linearity of the coefficient of operator and apply the rule $$[z^{p-q}]A(z)=[z^p]z^qA(z)$$ We also set the upper limit of the series to $n$ since the exponent of $z^{n-j}$ has to be non-negative.

• In (2) we change the order of summation $j\rightarrow n-j$.

• In (3) we work similarly as in (1).

• In (4) we select the coefficient of $z^{j-k}$ and do some rearrangements.