Generating function of a combinatorial problem?

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.

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.

• Thanks that what i did , then when i find the statistic of 00's ... I have to find the cofficient of d/dq A(x,0,1) / A(x,0,1)?? @awkward Commented Dec 26, 2019 at 18:53
• @Almaa Yes, that's correct. You might as well start by setting $p=1$ to simplify $A$. Then you will need to find the partial of $A$ with respect to $q$, then set $q=1$. This will give you a GF, and you will need to find the coefficient of $x^n$ in that GF. Commented Dec 27, 2019 at 0:39

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$$