Given integers from 1 to n, I believe there are (n-1)^2 series (out of a total of n! series) in which one number is out of order (one number has to be moved to get the sequence 1, 2, 3, …n). For example, 2 in the series 13452 needs to be moved to produce the sequence 12345.
Can anyone tell me how many series there are in which two numbers are out of order? For example: 13254, 14523, 34512 are all series in which two numbers need to be moved to get 12345.
The answer is 1 of 6 for n=3, 13 of 24 for n=4, and 61 of 120 for n=5 (NOTE: when I first posted, I wrote 58 for n=5, which was an error--sorry!). But I can’t see a way to a general equation for any n. The only potentially useful pattern I've noted is that series of n numbers in which x are out of order all have one or more embedded (though often interrupted) sequences of (n-x) numbers. For example, 13254 includes the sequences 1_2_4 and 13_5, 14523 includes 145 and 1__23. But I haven't found a way to make use of that fact.
I've asked a few mathematicians I know, and one economist who likes this sort of problem, and none could readily find a solution. A couple of them are still working on it, but I figured I'd also ask here.
Thanks for any help you can give, and I hope this may also be an entertaining puzzle.