2
$\begingroup$

I want to make sequences of length exactly 3r (r is a natural number, including zero). How many sequences are there such that each sequence is 3r characters long, with at least r of the same character in a row? Any permutation of these characters are valid. There are 25 characters and I can use each character as many times as I want.

$\endgroup$
  • $\begingroup$ Wait... "in A row" or "in THE row"? These two phrases have pretty different meanings. With $r=3$ do you consider $\color{red}{a}bc\color{red}{a}de\color{red}{a}fg$ to be a valid string that you want to count? $a$ occurs exactly three times in the row (i.e. in the string)... but not consecutively (i.e. in a row). Or do you only want to count things like $\color{red}{aaa}bcdefg$ $\endgroup$ – JMoravitz Feb 18 '17 at 17:03
  • $\begingroup$ in A row, so abcadeafg does not count, But we can count aaabcdefg or asdcccasd counts, given that r = 3. $\endgroup$ – Schloafhousin Feb 18 '17 at 17:06
3
$\begingroup$

The method will be to count sequences length $3r$ which have $<r$ successive identical characters (call this $C_{<r}$) and subtract from total sequences length $3r$ given by $25^{3r}$, so: $$\text{desired count}=25^{3r}-C_{<r}$$ Now, say, for the sake of argument that the characters are the first 25 letters of the English alphabet "a" through "y". Then call the generating function for all sequences using these 25 characters such that there are no $r$ successive identical characters $f(x)$. Further, call the generating function for all such sequences that terminate in the letter "a" $f_a(x)$, similarly the generating function for all sequences ending in "b" is $f_b(x)$ and so on. Then $$f(x)=1+f_a(x)+f_b(x)+\ldots +f_y(x)$$ Now, any sequence ending in "a" is formed from any sequence not ending in "a" with either $1,2,3\ldots,r-1$ "a"s appended hence $$f_a(x)=(f(x)-f_a(x))(x+x^2+x^3+\ldots +x^{r-1})\\\Rightarrow f_a(x)=\frac{f(x)(x+x^2+x^3+\ldots +x^{r-1})}{1+(x+x^2+x^3+\ldots +x^{r-1})}\\\Rightarrow f_a(x)=\frac{f(x)(x-x^{r})}{1-x^r}$$ Where the last step is a simplification using the finite geometric series formula.

By symmetry each of the generating functions for sequences ending "a", "b", "c" etc are equal $$f_a(x)=f_b(x)=f_c(x)=\ldots =f_y(x)=\frac{f(x)(x-x^{r})}{1-x^r}$$ therefore $$f(x)=1+25\cdot\frac{f(x)(x-x^{r})}{1-x^r}\\\Rightarrow f(x)=\frac{1}{1-25\frac{(x-x^{r})}{1-x^r}}\\\Rightarrow f(x)=\frac{1-x^r}{1-(25x-24x^r)}$$ Then the number of sequences length $3r$ with less than $r$ successive identical characters is the $x^{3r}$ coefficient of $f(x)$, in other words $$C_{<r}=[x^{3r}]\frac{1-x^r}{1-(25x-24x^r)}$$ and therefore $$\text{desired count}=25^{3r}-[x^{3r}]\frac{1-x^r}{1-(25x-24x^r)}$$ Note that the coefficients $f_k$ of $x^k$ in $f(x)=\sum\limits_{k\ge 0}f_kx^k$ can be generated by the recurrence $$f(x) = 1-x^r+(25x-24x^r)f(x)\\\Rightarrow f_k=25f_{k-1}-24f_{k-r}-\delta_{kr}$$ With $f_0=1$ and $f_k=0$ for $k<0$ and $\delta_{kr}$ is the Kronecker delta: $\delta_{kr}=1$ for $k=r$ and $0$ otherwise.

$\endgroup$
  • 1
    $\begingroup$ very good approach (+1) $\endgroup$ – G Cab Feb 19 '17 at 20:16
  • $\begingroup$ what does the x represent in this function. $\endgroup$ – Schloafhousin Feb 23 '17 at 15:00
  • $\begingroup$ It doesn't represent anything. It is known as an "indeterminate". In other words we use the formal power series purely for the coefficients in front of the powers of $x$. Sometimes generating functions are referred to as a "clothesline" upon which we hang the coefficients we are interested in. In this case the generating function I have derived has coefficients of $x^k$ which count words of length $k$ with less than $r$ consecutive identical characters. $\endgroup$ – N. Shales Feb 23 '17 at 16:52
  • $\begingroup$ For the case of $k=3r$ the coefficient of $x^{3r}$ in this expansion is then subtracted from the total number of words length $3r$ i.e. from $25^{3r}$. At the end of Markus' answer he has derived the generating function for desired words by subtracting my generating function from the generating function that enumerates all possible words $(1-25x)^{-1}$. Both answers amount to the same thing but Markus' has better formatting :) $\endgroup$ – N. Shales Feb 23 '17 at 17:02
1
$\begingroup$

Here is another approach to derive sequences of length $3r$ which contain $r$ consecutive equal characters. We start with a generating function for words of a $25$ character alphabet which counts words with no consecutive equal characters at all.

These words are called Smirnov or Carlitz words. See example III.24 Smirnov words from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick for more information.

The generating function $A(z)$ counting Smirnov words over a $25$ character alphabet is according to the reference \begin{align*} A(z)=\left(1-\frac{25z}{1+z}\right)^{-1} \end{align*}

The coefficient of $z^n$ of $A(z)$ gives the number of Smirnov words of length $n$.

Based upon $A(z)$ we generate all words over the $25$ character alphabet which contain no more than $r-1$ consecutive equal characters. This means each character can be replaced with one up to $r-1$ characters.

\begin{align*} z\longrightarrow z+z^2+z^3+\cdots+z^{r-1}=\frac{z(1-z^{r-1})}{1-z} \end{align*} in the generating function $A(z)$.

We obtain this way a generating function $B(z)=A\left(\frac{z(1-z^{r-1})}{1-z}\right)$ with \begin{align*} B(z)&=\left(1-\frac{25\cdot \frac{z(1-z^{r-1})}{1-z}}{1+\frac{z(1-z^{r-1})}{1-z}}\right)^{-1}=\frac{1-z^r}{1-25z+24z^r}\\ \end{align*} in accordance with the answer of @N.Shales.

$$ $$

We conclude a generating function $C(z)$ which counts words over a $25$ character alphabet each having at least $r$ consecutive equal characters is \begin{align*} C(z)&=\sum_{n=0}^\infty (25z)^n-B(z)\\ &=\frac{1}{1-25z}-\frac{1-z^r}{1-25z+24z^r} \end{align*} The number of wanted words is therefore $$[z^{3r}]C(z)$$

$\endgroup$
  • $\begingroup$ Great work (+1)! $\endgroup$ – N. Shales Feb 23 '17 at 17:04
  • 1
    $\begingroup$ @N.Shales: This also holds for your answer of course! (+1) $\endgroup$ – Markus Scheuer Feb 23 '17 at 17:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.