2
$\begingroup$

Please correct me, if any of my assumptions are wrong.

Suppose I want to find the number of words (real or not) with a length of 10 letters created by our 26-letter alphabet. This would yield $$26^{10}$$ possible combinations.

If I only wanted to use every letter just once the calculation would be $$\frac{26!}{16!}$$ possible combinations. The same result is found with $$26*25*24*23*22*21*20*19*18*17.$$

If repetitions of letters were allowed but no more than two equal letters should be present in a row, I would calculate $$26*25^{9}.$$

How can I calculate the possible number of words constructed from a 26-letter alphabet with length 10, where no triple letters should be present? So, $ABCDEFGHIJ$ would naturally be allowed, as would be $AABBAABBAA$, while $ABCDEEEFGH$ would exceed the maximum number of repeats of a single letter ($E$ in this case).

Based on the previous approaches I would assume $$26*25*24^{8}$$ to be the correct calculation. However, I'm not sure whether it is indeed correct or how to go about finding out, if it is. If I scale it down to shorter words or less letters, it appears to yield lower numbers than expected.

This question is, as I see it, independent of vowels or consonants.

$\endgroup$
  • 1
    $\begingroup$ $26\times25^9$ counts the words where all letters differ from e.g. the first letter (with exception of first itself). Then more than 2 equal letters can be present. $\endgroup$ – drhab Jan 19 '18 at 14:07
  • $\begingroup$ OP is counting the words where all letters differ from the previous letter. He explains when he talks of three-in-a-row. $\endgroup$ – Empy2 Jan 19 '18 at 14:31
  • $\begingroup$ @Michael: It also counts the words with no pairs of successive letters matching. Pick the first letter freely, then each following letter has to be different from the one before. It misses AABBCCDDEE, which the text indicates should be counted. $\endgroup$ – Ross Millikan Jan 19 '18 at 15:01
0
$\begingroup$

Suppose there are $A(n)$ with the last two letters the same, and $B(n)$ with the last two letters different. In both cases, three-in-a-row is not allowed.

Then $A(n+1)=B(n)$ and $B(n+1)=25(A(n)+B(n))$. So $$B(n+2)=25B(n+1)+25B(n)$$

Look up finite difference equations. The trick is to solve the quadratic equation $$x^2=25x+25$$

then the general solution for $B(n)$ is $$B(n)=Cx_1^n+Dx_2^n$$

You can check that this formula obeys the recursion above. Lastly, calculate $B(1)$ and $B(2)$, then you can work out what $C$ and $D$ must be.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry for the late reply. Thanks for the answer. Though, to be completely honest, I don't really understand it. I guess it's too sophisticated for me, my knowledge of math is quite basic. $\endgroup$ – problemfinder Jan 24 '18 at 10:03
  • $\begingroup$ It increases by a factor of about 25.9629 for every extra letter. $\endgroup$ – Empy2 Jan 24 '18 at 10:14

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.