How many n strings are there of letters of english alphabet in which there are no consecutive z's?

Question

I have this combinatorics problem:

How many n strings are there of letters of english alphabet in which there are no consecutive z's?

I want to solve this problem using generating functions

Generating functions of single letters other than z is obvious but i can't find the generating function for z. I know that its function will be a polynomial with degree of $\frac{n}{2}$ or $\frac{n+1}{2}$ depending on whether n is even or odd but i can't find the coefficients of the function. Can anyone lead me to a solution?

Thanks in advance.

Answer 1

The letter $z$ is always followed by a non-$z$, except for the $z$ at the end. So group each $z$ with letter after it to form a double letter. The string is built out of letters and double letters; call each of these a "unit". The generating function of a single unit is $25x+25x^2$; there are $25$ letters of length $1$, and $25$ double letters of length $2$. Since we want a sequence of these units, the g.f. is $$ {1\over 1-25x-25x^2} $$ But wait, we forgot about the possible $z$ at the end! There either is or is not a $z$ at the end, which is accounted for by a factor of $1+x$. Therefore, the answer is actually $$ \bbox[5px,border:1.5px solid black]{{1\over 1-25x-25x^2}\cdot (1+x).} $$

Answer 2

Words with no consecutive equal characters at all are called Smirnov or Carlitz words. See example III.24 Smirnov words in Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

A generating function for the number of Smirnov words over an $n$-ary alphabet is given by \begin{align*} \left(1-\frac{nz}{1+z}\right)^{-1}\tag{1} \end{align*}

Here we consider an alphabet with $n=26$ letters. Since there is only a restriction given for $z$, all other letters may occur with runs of arbitrary length. We respect this by substituting each of these characters with

\begin{align*} z\to z+z^2+z^3+\cdots=\frac{z}{1-z}\tag{2} \end{align*}

We substitute (2) in (1) for all characters but one and obtain \begin{align*} &\left(1-\frac{z}{1+z}-25\frac{\frac{z}{1+z}}{1+\frac{z}{1+z}}\right)^{-1}\\ &\qquad=\color{blue}{\frac{1+z}{1-25z-25z^2}}\\ &\qquad=1+26z+675z^2+17\,525 z^3+455\,000z^4+11\,813\,125z^5+\cdots \end{align*} The last line was calculated with some help of Wolfram Alpha.

Answer 3

Or, we can build a good word by adding, step by step, a new component

$sA + sB + \cdots + sY + sZ + s^2.c.ZZ + s^3.c^2.ZZZ + \cdots \ $ where

$c$ is a counter for the at least number of occurrences of a pair ZZ in the word.

$s$ is a counter for the length of the added component.

overall the strings are depicted by

$$1 \over 1 - (sA + sB + \cdots + sY + sZ + s^2.c.ZZ + s^3.c^2.ZZZ + \cdots )\ $$

we are interested in words that have exactly $ \ 0 \ $ occurences of ZZ, so we have to replace $ \ c \ $ by $ \ c-1 \ $ for the PIE reason, than take $ \ c=0 \ $.

the generating expression becomes $${1 \over 1 -( sA + sB + \cdots + sY + {sZ \over 1+sZ}) }={ 1+sZ \over 1 -( sA + sB + \cdots + sY )(1 + sZ)}$$

when we are interested only in length ( the sort of letter does not matter) we get the generating function

$$ \frac {1+s} {1 - 25s.(1 + s)} $$