Consider a string of N numbers, [1, 2, 3, … , N]. I choose one of them, say i , and I am interested in the total number of permutations, in which i takes positions between L and M. I have two solutions for this problem:
-
For simplicity, say M – L = k. Now the total number of permutations we can form, with i, in the interval of length k is simply k!. We then have (N-k) elements left, so (N-k)! more permutations outside the interval of k elements. In total, one can form k!*(N-k)! permutations, in which i resides in an interval of length k.
-
We are interested in the permutations of N where i takes only one of the k possible positions. Therefore, the total number of permutations is : k*(N-1)!
Now clearly k!(N-k)! is not equal to k(N-1)!, so one of the solutions is wrong. The question is which one and why?
Best Answer
The first answer is wrong because you only permute the integers in $[L,M]$ and $[1,L-1)\cup (M+1,L-1]$ with each other.
Consider for example the permutation [k-1,2,3,...,k-2,1,k,k+1,...,N] which meets the condition if $k-1,k \in [L,M]$ but which is not counted in the second solution.