# interesting probability puzzle involving out-of-sequence series

• Nov 20th 2010, 08:31 AM
metanarrator
interesting probability puzzle involving out-of-sequence series
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.
• Nov 20th 2010, 10:58 AM
metanarrator
After posting, I did some more work on this myself, and I think there may be some value in thinking of how series of n numbers are built by adding n at various places in series of n-1 numbers. For example, with n=3:

312, 132, and 123 are created by adding 3 to the 1st, 2nd, or 3rd place in the series 12.
321, 231, and 213 are created by adding 3 to the 1st, 2nd, or 3rd place in the series 21.

Here's a table describing the number of series of n numbers with x numbers out of sequence. Rows are n, starting with 1. Columns are x, starting with 0

1
1 1
1 4 1
1 9 13 1
1 16 61 41 1

To get a series of 3 numbers with 0 out of sequence, you have to add 3 to the end of a series of 2 numbers (the only one is 12) that has 0 out of sequence.
To get a series of 3 numbers with 1 out of sequence, you could either add 3 to a series of 2 numbers that has 0 out of sequence so that it is out of sequence (adding it to the 1st or 2nd place of 12), or you could add 3 to a series of 2 numbers that has 1 out of sequence (the only on is 21), so that it does NOT add to the number of out-of-sequence numbers (adding it to the 2nd or 3rd place of 21).
To get a series of 3 numbers with 2 out of sequence, you have to add 3 to a series of 2 numbers that has 1 out of sequence so that it does add to the number of out-of-sequence numbers (adding it to the 1st place of 21).

Applying the same logic in adding a 4 to series with n=3:

The only series with n=3 that has 0 numbers out of sequence is 123.
Four series have 1 number out of sequence: 312, 213, 132, 231.
The only series with n=3 that has 2 numbers out of sequence is 321.

There is only one way to add 4 to 123 so that it is NOT out of sequence.
There are three ways to add 4 to 123 so it is out of sequence. These contribute 3 of the 9 series with n=4 that have one number out of sequence.
The only way to add 4 to either 312 or 213 so that it does NOT increase the numbers out of sequence is to add it on the end. These contribute 2 more of the 9 series with n=4 that have one number out of sequence.
There are two ways to add 4 to either 132 or 231 so that it does NOT increase the numbers out of sequence (adding it to the last or second-to-last spots). These contribute 4 more of the 9 series with n=4 that have one number out of sequence.

Since there are 16 possible ways 4 could be added to the 4 series that have one number out of sequence, and 6 of them do NOT increase the numbers out of sequence, then 10 of them do increase the numbers out of sequence. These contribute 10 of the 13 series with n=4 that have two numbers out of sequence. The other 3 come from adding 4 to the series 321 at any poiint but the beginning.

Thus, any cell in the above table is arrived at by combining the number of out-of-sequence ways n can be added to any of the n-1 series that have x-1 numbers out of sequence, and the number of in-sequence ways that n can be added to any of the n-1 series that have x numbers out of sequence. 16 is 4+12, 61 is 33+28, 41 is 37+4.

Since we know that the number of series with one number out of sequence is (n-1)^2, it's easy to calculate how many n=6 series with two numbers out of sequence would be contributed by adding 6 out of sequence to n=5 series with one number out of sequence. Since 5 of the 25 n=6 series with one number out of sequence are produced by adding 6 to any of first 5 places of 12345 (612345, 162345, etc.), the other 20 must be ways that 6 can be added to the 16 n=5 series with one number out of sequence so that it does NOT increase the numbers out of sequence. And since there are six ways that 6 can be added to each of those 16 series (for a total of 96), the other 76 must produce n=6 series with two numbers out of sequence.

But of course that doesn't tell us how many n=6 series with x=2 are contributed by adding 6 in sequence to n=5 series with x=2.

Please understand that I'm not a mathematician, so don't judge me too harshly is this is all a fruitless waste of mental energy, and there's a much simpler solution.