Expanding series to obtain desired words using generating functions

91 Views Asked by At

I am working on analytic combinatorics by myself. According to theorem, $$W\bigg(z,\frac{az}{1+az},\frac{bz}{1+bz},\frac{cz}{1+cz}\bigg)=\bigg(1-\frac{az}{1+az}-\frac{bz}{1+bz}-\frac{cz}{1+cz}\bigg)^{-1}$$

would give the words such that no two consecutive same element appears in its expansion.

It doesnt works in $$W\bigg(z,\frac{az}{1+az},\frac{bz}{1+bz}\bigg)=\bigg(1-\frac{az}{1+az}-\frac{bz}{1+bz}\bigg)^{-1}= \frac{1+az+bz+abz}{1-abz^2}$$

It produces some unwanted words such as $aab$ when we expand it

MOreover, when we apply the same for $\bigg(1-\frac{az}{1+az}-\frac{bz}{1+bz}-\frac{cz}{1+cz}\bigg)^{-1}$, I obtain $$\frac{1+a+b+c+ab+ac+bc+abc}{1-(ba+ca+cb+bac+cab)}$$

When I expand it, I got some unwanted words such as $bba,ccb,..,abbac,..$ etc,as well.

Why doesnt it work properly when we expand them ? They should have listed all possible Smirnow words. Can you please help me to understand how thier expansion gives desired words even if they contain some unwanted words.

(You can see theorem here,page $205$)

ADDENTUM: @ is it possible to show that $$W(z,a,b)=\frac{1}{(1-(a+b)z)}$$ derives smirnow words algebraically when we put $a/(1+a),b/(1+b)$ in place of a and b above without using my way. I want to see that it derives smirnow words algebraically. I know that $a/(1+a) = a-a^2+a^3-a^4+...$, and it is valid also for $b$. Moreover, we write them in form of $$\sum_{n \geq0}(\frac{a}{1+a}+\frac{b}{1+b})^n$$ , but how those terms cancel each other and gives a,b,ab,ba+...

1

There are 1 best solutions below

7
On

The coefficient of $z^n$ of the generating function \begin{align*} W(z;a,b)=\left(1-\frac{az}{1+az}-\frac{bz}{1+bz}\right)^{-1}\tag{1} \end{align*} is not intended to produce the set of binary Smirnov words of length $n$, but a way to derive the number of these words. The generating function starts with \begin{align*} 1+(a+b)z+2abz^2+\left(a^2b+ab^2\right)z^3+2a^2b^2z^4+(a^3b^2+a^2b^3)z^5+\cdots \end{align*} Evaluating (1) at $a=b=1$ gives \begin{align*} \color{blue}{W(z;1,1)}&=\left(1-\frac{2z}{1+z}\right)^{-1}\\ &\color{blue}{=1+2z+2z^2+2z^3+\cdots=\frac{1+z}{1-z}} \end{align*}

Note: Here we typically consider generating functions as (formal) power series which form a $\mathbb{C}$-vector space denoted by $\mathbb{C}[[z]]$. Since $\mathbb{C}$ is a commutative field, we have for instance $(abab+baba)z^4=2a^2b^2z^4$.

The authors P. Flajolet and R. Sedgewick refer to section 2.4.16. The Smirnov Problem in Combinatorial Enumeration by I. P. Goulden and D. M. Jackson, who provide this approach to derive the number of Smirnov words.