Number of possible permutations with fixed element inside interval.

Question

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:

1. 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.

2. 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?

Answer 1

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.

Answer 2

The first one is wrong:

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.

When you do this, you are fixing the elements that are outside and the elements that are inside the interval. There are k-1 elements that could be placed outside the interval but you're not counting them and so with the N-k elements outside that could be placed inside.

I solved your question a little bit different way.

Without loss of generality, we can assume that the positions that $i$ is restricted to are the last $k$ positions of the sequence. Divide this entries, forming two sequences. The first are of the entries from $1$ to $L$ and the second is from $L+1$ to $N$ where $L$ satisfies $N-L=k$.

For the first sequence, of $N-1$ elements, you can choose $N-k$ that can be disposed in $(N-k)!$ ways, giving us $$ \dfrac{(N-1)!}{(N-k)!(k-1)!} \cdot (N-k)! = \dfrac{(N-1)!}{(k-1)!} \text{ possibilities.}$$ For the second, we simple have $k$ elements, so $k!=k(k-1)!$ possibilities. Multiplying those two we have $k(N-1)!$ possibilities.