Choosing random keys

Say you had code that generated random keys. These random keys were 6 letters long, all caps, with no duplicates. Here’s a few, as an example:

What are the chances that the key that you generate will be in alphabetical order? For instance, above, there’s only one in alphabetical order (CERSUY, in bold) And then, if you think you have that, generalize: For any string of length k distinct characters chosen from a set of n, what are the chances that they will be in order? My answer after the break.

I spent several minutes trying to solve this the straightforward way. You only have 21 choices for the first letter, because if it’s anything after U, there’s no way to have five more letters that come after it. Then for the second letter, you have 22-a₁ (where a₁ is the index of the first letter) choices. For instance, if the first letter was E, you have only 22-5, or 17 choices – namely anything between F and V. After going through all six letters, you end up with this ungainly thing:

It’s probably possible to simplify that somewhat by looking at reductive cases – you can model a two-letter key as a grid of allowed possibilities, but even that would get pretty challenging pretty quickly. If you look at it from another direction, however, things get much easier. Consider a single key, let’s say “NTCYAR” (the first in the table above). How many possible permutations of that key are there? Simple: 65432*1, or 6!. Of those, how many of them are in alphabetical order? Even simpler: 1 (ACNRTY). In fact, this is true for any set of six letters you choose – you could have picked those same letters in any of 6! possible orderings, and only one is in alphabetical order. So there you go. Your answer is:

The interesting thing? The probability doesn’t depend on the length of your alphabet, only on the length of the key. The generalized probability is simply: