1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.