Solving Combination Question: Word Length & Alphabetical Order

[Batmaniac]

I have a fully solved combination question that I can't seem to follow.

"How many words of length 4 can be formed if the letters in the word must be in increasing alphabetical order? Note: {A,A,D,E} is but {A,D,A,E} is not"

The solution is as follows (C denotes choose)

(26 C 1) + (26 C 1)(25 C 1) + (26 C 2) + (26 C 1)(25 C 2) + (26 C 4) = 23751

I am having trouble seeing just what this calculation is doing and why it solves the problem (I've only just recently been introduced to permutations and combinations).

To my understanding, each term in the solution is its own case, but I'm not sure what these cases are.

Any help in explaining this solution would be appreciated.

Thanks.

 

[EnumaElish]

Can you post the thought process that led to this solution?

 

[matt grime]

There are probably several ways to do this. You really need to find some way of making the counting easy.

You could set up all kinds of difference equations to solve this, but that is hard. You could sum over all possible starting letters, but that is hard.

How about splitting things up into smaller groups. It is easy to calculate the number of acceptable strings with no repetitions: given any 4 distinct letters, there is precisely one acceptable ordering. Or if you like, there are 26 choose 4 acceptable strings. Now, what about the ones we've yet to count?

 

[matt grime]

Can you post the thought process that led to this solution?

It isn't a solution they devised, so probably not. But it is breaking it down into cases - the first term counts the strings with one letter in them, and so on.

 

[EnumaElish]

Oh, I hadn't seen the "a" in "I have a fully solved". Sorry.

I am guessing that the answer is:

letter1 * (26 - rank(letter1) + 1) * (26 - rank(letter2) + 1) * (26 - rank(letter3) + 1) summed over letter3, then over letter2, then over letter1.

 

[matt grime]

Erm, that is not the way to do it. It would contain approximately a thousand or so terms in the sum, wouldn't it? I mean, it is certainly large, and certainly not obvious how to relate it to the given answer which is easy to explain (follow my hint above).

 

[EnumaElish]

I thought my formula would resolve into combinations.

 

[matt grime]

If it's correct it will. But can you see an easy way to do that?

 

[EnumaElish]

Point taken. Starting over, with one letter (e.g. AAAA), there are 26 = C(26, 1) combinations.