Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

2 Answers

up vote 2 down vote accepted

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}$.

share|improve this answer
add comment

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}$.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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