6
$\begingroup$

How many words of length $6$ are there when adjacent letters being equal is not allowed?

My try: We have $26$ choices for the first position and $25$ for the remaining $5$ positions because if we choose any alphabet for the first position we have $25$ left for second and for the third we still have $25$ ($-1$ for the letter which is in $2$nd position) and so on.

So, is $26 \cdot 25^{5}$ the correct answer?

$\endgroup$
2
  • 1
    $\begingroup$ Yes, it is correct. $\endgroup$ Commented Mar 6, 2016 at 6:40
  • 1
    $\begingroup$ Yes, it is correct :-) $\endgroup$ Commented Mar 6, 2016 at 6:40

2 Answers 2

1
$\begingroup$

Here is some additional information affirming your answer.

The words with no consecutive equal letters are so-called Smirnov words. If you are curious about them you might have a look at example III.24 in Analytic Combinatorics which explains some properties of them.

We count the number of Smirnov words of length $n$ with the help of formal power series. The coefficients of $z^n$ give the number of words of length $n$.

It turns out that the power series of Smirnov words with $26$ letters is \begin{align*} \left(1-\frac{26z}{1+z}\right)^{-1}&=\frac{1+z}{1-25z}\\ &=1+26z+650z^2+16250z^3\\ &\qquad+406250z^4+10156250z^5+253906250z^6+\cdots \end{align*}

The coefficients of $z^n$ were calculated with the help of Wolfram Alfa.

We observe, the number of Smirnov words of length $6$ is \begin{align*} 253906250=2\cdot5^{10}\cdot13=26\cdot25^5 \end{align*}

$\endgroup$
2
  • $\begingroup$ That's the reason I love Mathematics. An explanation for everything. Thank you so much. $\endgroup$
    – max
    Commented Mar 6, 2016 at 16:59
  • $\begingroup$ @max: You're welcome! I see, there are many good reasons to love mathematics. :-) $\endgroup$ Commented Mar 6, 2016 at 17:02
1
$\begingroup$

Yes the answer will be $$ 26 * 25^5 $$ and your method is absolutely correct.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .