Generating function of a combinatorial problem?

Question

Let $A_n$ be the set of all binary words of length $n$. Let $A(x,p,q)$ be the generating function of the number of words in $A_n$ when $x$ counts length , $p$ counts the number of $1$ (the number of appearance of $1$), $q$ counts the number of strings $00$. Write a recursive structure for $\cup_{n} A_n$ for calculating the generating function and find it. What is the average of the number of the string $00$ in $A_n$ . Can you help me with this questions please, I'm puzzled with that topic. Thanks in advance.

Answer 1

In this problem, the structure of binary words makes it possible to derive the generating function without first finding the coefficients (and it's easier, too). Note these facts about binary words:

• A word is either the empty word, a word ending in zero, or a word ending in one.
• A word ending in zero is either the word $0$, a word ending in zero followed by a zero, or a word ending in one followed by a zero.
• A word ending in one is an arbitrary word followed by a one.

Let's define $B(x,p,q)$ to be the generating function for words ending in a zero and $C(x,p,q)$ to be the generating function for words ending in a one. Then the above observations translate into the following equations: $$\begin{align} A(x,p,q) &= 1 + B(x,p,q) + C(x,p,q) \\ B(x,p,q) &= x + qxB(x,p,q) + xC(x,p,q) \\ C(x,p,q) &= xpA(x,p,q) \end{align}$$ Solve this system of three equations for $A(x,p,q)$ and you have the sought-after generating function. You can then use that generating function to find the average number of $00$s in a word of length $n$ without needing to find the coefficients of the generating function.

Answer 2

This will get you started ...

Let $X_{n,p,q}$ denote the number of binary words with $p$ $1$'s and $q$ $00$'s that end with $00$.

Let $Y_{n,p,q}$ denote the number of binary words with $p$ $1$'s and $q$ $00$'s that end with $10$.

Let $Z_{n,p,q}$ denote the number of binary words with $p$ $1$'s and $q$ $00$'s that end with $1$.

Your $A_{n,p,q}$if given by \begin{eqnarray*} A_{n,p,q}= X_{n,p,q} + Y_{n,p,q} +Z_{n,p,q}. \end{eqnarray*}

$X,Y,Z$ satisfy the following recurrence relations \begin{eqnarray*} &X_{n+1,p,q+1} &=& X_{n,p,q} + Y_{n,p,q} \\ &Y_{n+1,p,q}&=& &Z_{n,p,q} \\ &Z_{n+1,p+1,q}&=& X_{n,p,q} + Y_{n,p,q}+ & Z_{n,p,q}. \\ \end{eqnarray*}

You now need to do some algebra to get a recurrence relation that only involves $A$. ... Good luck ... $ \ddot \smile$