2
$\begingroup$

For instance, aaaaabbbbb and abcdefghiz are in alphabetical order, while bababababa is not.

I tried finding some value to divide by $26^{10}$, but I'm not sure how to find that value. Each letter in the sequence depends on the previous letter.

2 Answers 2

2

Notice that the number you want is the same as the number of non-increasing functions from $\{1,\ldots , 10\}$ to $\{1,\ldots , 26\}$. This number is $\binom{35}{10} = 183579396$. If you want to know why this is true, write back. The probability comes out to nearly $1.3 \times 10^{-6}$.

0

For the numerator you are looking for, here is a not completely attractive but not hard to compute expression.

If we are going to use $k$ distinct letters, they can be chosen in $\binom{26}{k}$ ways. For each of these ways, we ask how many $10$-letter "words" there are in non-decreasing alphabetical order.

This is a straight Stars and Bars problem. We have $10$ slots to put letters into, and will put $k-1$ separators between the slots. The slots up to the first separator will be filled with the first (in the alphabet) of our $k$ chosen letters. The slots between the first separator and the second will be filled with the second (in the alphabet) of our chosen letters, and so on. There are $9$ gaps between the $10$ slots, so there are $\binom{9}{k-1}$ ways to insert the separators. So our numerator is $\sum_{k=1}^{10} \binom{26}{k}\binom{9}{k-1}.$ For the probability, divide by $26^{10}$.