Understanding Smirnov words in analytic combinatorics

Question

I am trying to understand a generating function in the explanation of Smirnov words in this book, in page $204-205$.

It is said that

" Smirnov words. Following the treatment of Goulden and Jackson [303], we define a Smirnov word to be any word that has no consecutive equal letters. Let $W = SEQ(A)$ be the set of words over the alphabet $A = {a_1,. . . , a_r}$ of cardinality $r$, and $S$ be the set of Smirnov words

Let also $v_j$ mark the number of occurrences of the $j$th letter in a word.One has $$W(v_1,v_2,...,v_r)=\frac{1}{1-z(v_1+v_2+..+v_r)}$$ "

Here , I understood that for example $v_1$ marks the number of occurences of $a_1$ in a word. Am I right here ?

Now, lets come to my main question.By thinking my foregoing deduction as true ,i.e , $v_1$ denotes the number of occurences of $a_1$, assume that our alphabet is $A={a,b}$ and by giving any occurrence to these letters, i can obtain the number of any words of desired size. Am I also right here ?

So , i think that lets say that $a$ can occur two times and $b$ can occur maximum three times. Then $$W(x^2,(x+x^2+x^3))=\frac{1}{1-z\bigg((x^2)+(x+x^2+x^3)\bigg)}$$

Then , I want to learn the number of all words of length $3$ using $a,b$, it must be $2^3=8$ , but when i look at the coefficient of $[z^3x^3]$ in wolfram, it is $1$

Is there any deficit part in the book ? I think that it should have been indicated that "Let also $v_j$ mark the number of occurrences of the $j$th letter in a word from one to desired repetition".

Am I right here ? Should we always start from $x^1$ up to $x^k$ where $k$ is the number of maximum consecutive identical letter.

Answer 1

Here we consider a binary alphabet $\mathcal{A}=\{a,b\}$ and derive a generating function of Smirnov words following closely the example III.24 given in Analytic Combinatorics by R. Sedgewick and P. Flajolet.

Binary words over $\mathcal{A}$:

The set $\mathcal{W}$ of all binary words over the alphabet $\mathcal{A}$ is \begin{align*} \mathcal{W}=\{&\varepsilon,a,b,aa,ab,ba,bb,\\ &aaa,aab,aba,baa,abb,bab,bba,bbb,aaaa,\ldots\} \end{align*} where $\varepsilon$ denotes the empty word of length $0$. A generating function $W(z;a,b)$ for the set of all binary words is the geometric series \begin{align*} \color{blue}{W(z;a,b)}&=1+(a+b)z+(a^2+2ab+b^2)z^2\\ &\qquad\qquad+(a^3+3a^2b+3ab^2+b^3)z^3+a^4z^4+\cdots\\ &=\sum_{n=0}^{\infty}(a+b)^nz^n\\ &\,\,\color{blue}{=\frac{1}{1-(a+b)z}} \end{align*}

Smirnov words over $\mathcal{A}$:

The set $\mathcal{S}$ of all binary Smirnov words, i.e. all binary words with no consecutive equal characters over $\mathcal{A}$ is \begin{align*} \mathcal{S}=\{&\varepsilon,a,b,ab,ba,aba,bab,\\ &abab,baba,ababa,babab,ababab,bababa,\ldots\}\tag{1} \end{align*} Of course we see in (1) at a glance there are precisely two non-empty Smirnov Words of length $n, n\geq 0$. One of them starting with $a$, the other with $b$. A generating function $S(z)$ which counts the number of Smirnov words in the binary case is simply \begin{align*} S(z)&=1+2z+2z^2+2z^3+2z^4+\cdots\\ &=1+\sum_{n=1}^{\infty}2z^n\\ &=1+\frac{2z}{1-z} \end{align*} Looking at (1) we can also derive a generating function $S(z;a,b)$. Here the exponent of $a$ resp. $b$ indicates the number of occurrences of $a$ resp. $b$. We prefer to derive $S(z;a,b)$ from $W(z;a,b)$ which also provides information how this can be reached in the general case with alphabets of size $r\geq 2$.

The key observation is that a binary words can be transformed to a Smirnov word by replacing all consecutive characters by just one of them and on the other hand we can obtain all binary words by starting with the set $\mathcal{S}$ of Smirnov words and by replacing each occurrence of a character by one or more occurrences of this character. This transformation is done by \begin{align*} a\quad\to\quad a+a^2+a^3+a^4+\cdots&=\frac{a}{1-a}\\ b\quad\to\quad\ b+b^2+b^3+b^4+\cdots\ &=\frac{b}{1-b}\\ \end{align*} We therefore have the following relationship between $S(z;a,b)$ and $W(z;a,b)$ \begin{align*} \color{blue}{S\left(z;\frac{a}{1-a},\frac{b}{1-b}\right)=W(z;a,b)}\tag{2} \end{align*} For instance the Smirnov word $abab$ corresponds via (2) with the binary words \begin{align*} abab\quad\longleftrightarrow\qquad &abab,\\ &aabab,abbab,abaab,ababb,\\ &aaabab,abbbab,abaaab,ababbb,\\ &aaaabab,abbbbab,abaaaab,ababbbb,\\ &aabbab,aabaab,aababb,abbaab,abbabb,abaabb,\\ &\ldots \end{align*} We have the following relationship \begin{align*} a\quad\to\quad \frac{a}{1-a}\qquad\qquad \frac{\frac{a}{1+a}}{1-\frac{a}{1+a}}=a\tag{3} \end{align*} Thanks to (2) and (3) we can also derive the generating function $S(z;a,b)$ from $W(z;a,b)$ via \begin{align*} \color{blue}{S(z;a,b)=W\left(z;\frac{a}{1+a},\frac{b}{1+b}\right)}\tag{4} \end{align*} and we derive from (4)

\begin{align*} \color{blue}{S(z;a,b)}&=W\left(z;\frac{a}{1+a},\frac{b}{1+b}\right)\\ &=\frac{1}{1-\frac{az}{1+az}-\frac{bz}{1+bz}}\\ &=\frac{(1+az)(1+bz)}{(1+az)(1+bz)-az(1+bz)-bz(1+az)}\\ &\,\,\color{blue}{=\frac{1+(a+b)z+abz^2}{1-abz^2}}\tag{5}\\ &\,\,\color{blue}{=1+(a+b)z+2abz^2+ab(a+b)z^3+2a^2b^2z^4+\cdots}\tag{6} \end{align*}

We see the generating function $S(z;a,b)$ in (6) corresponds nicely with the set $\mathcal{S}$ in (1) giving for each even length $2m$ two Smirnov words with $m$ $a$'s and $m$ $b$'s and for each odd length $2m+1$ two Smirnov words with either one more $a$ than $b$'s or vice versa.

Note: As requested by a comment we can also show the validity of (2) algebraically. We consider (5) in the form \begin{align*} \frac{1+az+bz+abz^2}{1-abz^2} \end{align*} and have according to (3) to substitute each occurrence of $az$ with $\frac{az}{1+az}$ and each occurrence of $bz$ with $\frac{bz}{1+bz}$. This type of substitution is indicated in the parameter representation in (4).

We obtain from (5) \begin{align*} &\color{blue}{S\left(z;\frac{a}{1-a},\frac{b}{1-b}\right)}\\ &\qquad=\frac{1+\frac{az}{1-az}+\frac{bz}{1-bz}+\frac{az}{1-az}\,\frac{bz}{1-bz}} {1-\frac{az}{1-az}\,\frac{bz}{1-bz}}\\ &\qquad=\frac{(1-az)(1-bz)+az(1-bz)+bz(1-az)+abz^2}{(1-az)(1-bz)-abz^2}\\ &\qquad=\frac{1}{1-(a+b)z}\\ &\qquad\,\,\color{blue}{=W(z;a,b)} \end{align*} and (2) follows.

Answer 2

Let us focus on the two letter alphabet case. I will use $A$ and $B$ to refer to the letters themselves, while $a$ and $b$ are the variables for the generating function. We have two generating functions of interest:

Generating function	Meaning
$W(a,b)=\frac1{1-(a+b)}$	$[a^mb^n]W(a,b)=\text{# words with $m$ $A$'s and $n$ $B$'s}$
$S(a,b)= W\left(\frac{a}{1+a},\frac{b}{1+b}\right)$	$[a^mb^n]S(a,b)=\text{# Smirmov words with $m$ $A$'s and $n$ $B$'s}$

Let us check that $S(a,b)$ works properly. $$ S(a,b)=\frac{1}{1-\frac{a}{1+a}-\frac b{1+b}}=\frac1{1-ab}+\frac{a}{1-ba}+\frac b{1-ab}+\frac{ba}{1-ba} $$ Note that $\frac1{1-ab}=1+ab+abab+ababab+\dots$, which represents all Smirmov words like the empty word, $AB$, $ABAB$, $ABABAB$, and so on. Next, $\frac{a}{1-ba}=a+bab+babab+\dots$, representing $A$, $ABA$, $ABABA$, and so on. Similarly, $\frac b{1-ab}$ represents $B, BAB,BABAB,\dots$, while $\frac{ba}{1-ba}$ represents $BA, BABA, BABABA,\dots$. You can check that these four groups represent all possible sequecne of $A$ and $B$ with no instances of $AA$ and $BB$, so $S(a,b)$ works as intended.

Next, suppose that you want to count words where there are at most $p$ instances of $A$ in a row, and at most $q$ instances of $B$ in a row, for some integers $p$ and $q$. The authors say that if you substitute $a+a^2+\dots+a^p$ and $b+b^2+\dots+b^q$ into $S(a,b)$, then this does exactly what you want. For example, let $p=2$ and $q=3$. Then you can find the number of words with $3$ $A$'s and $4$ $B$'s, such that no instances of $AAA$ or $BBBB$ occur, by extracting $$ [a^3b^4]S(a+a^2,b+b^2+b^3)=28. $$ See Wolfram|Alpha computation. Indeed, the 28 valid words are listed below:

AABABBB AABBABB AABBBAB ABAABBB ABABABB ABABBAB ABABBBA 
ABBAABB ABBABAB ABBABBA ABBBAAB ABBBABA BAABABB BAABBAB 
BAABBBA BABAABB BABABAB BABABBA BABBAAB BABBABA BABBBAA 
BBAABAB BBAABBA BBABAAB BBABABA BBABBAA BBBAABA BBBABAA 

If you just wanted to count the number of valid words of a given length, instead of with a given frequency of each letter, you need to replace both $a$ and $b$ with a generic variable, say $x$. In that case, you find $$ [x^7]S(x+x^2,x+x^2+x^3)=63, $$ so there are $63$ words of length $7$ with no instances of $AAA$ or $BBBB$.

However, there is no utility in considering $W(a+a^2,b+b^2+b^3)$. The authors never claimed there was any utility to this, only for substituting in $S$. The problem is, since $W(a,b)$ enumerates all sequences of $a$ and $b$, there would be ambiguity when you expand $W(a+a^2,b+b^2+b^3)$, so some words would be double-counted, and the coefficients lose any useful meaning.

The problem is best illustrated with a single-letter alphabet. $$ \begin{align} W(a+a^2)&=\frac1{1-(a+a^2)} \\&=1 + (a+a^2)+(a+a^2)^2+\dots \\&=1+a+aa+\color{red}aa + \color{red}2aaa + aaaa+\dots \\&=1+a+2a^2+\dots \end{align} $$ As you can see, the coefficient of $a^2$ is $2$, which is incorrect, because there is only one word of length $2$, namely $AA$. However, this word was counted twice. This problem does not occur when substituting in $S(a,b)$, because $S$ was carefully constructed to not allow repeated instances, so no ambiguity.