What are the no of permutations for any no of adjacent elements swapping places at the same time in an array of length n?
Asked
Active
Viewed 102 times
1 Answers
0
I think that we only need to count the number of ways to choose disjoint pairs of adjacent elements. This is the same as the number of ways to choose the index of the first element of the pair. Or better, to choose the distance between the pairs. Let's call $x_1$ the position of the first element of the first pair to be swapped, $x_2$ the distance from the second element of the first pair to the first element of the second pair, and so on. Then we have the conditions: $x_1,x_2,...,x_k\geq1$, $x_1+x_2+...+x_k+k\leq n$. We can introduce a new variable $y\geq1$ to contain the difference between the sum and $n$. In this way we get an equality, which is easier to treat. $$x_1+...x_k+y=n-k+1$$ Now we just need to count the number of integer solutions of this equation for each $k=1,2,...$ and add these numbers together. We know the number of solutions of such an integer solution. But this we know know how to count as in here.
Let just continue along that line and see what we get at the end of the computation.
We have to count the number of integer solutions of the equation $$\begin{align}x_1+x_2+...+x_k+y&=n-k+1\\x_i&\geq1\\y&\geq1\end{align}$$
Following the idea in the question you linked this number is the number of ways to put $k$ bars in between $n-k+1$ stars. We can see that this number is $\binom{n-k}{k}$.
And now we add these numbers for all values of $k$ $$F_{n+1}:=\sum_{k=0}^{[n/2]}\binom{n-k}{k}$$
Notice you have a mistake there (which somehow I think it is not your fault) and we should also consider the case $k=0$ to count the case in which no permutations occur.
Now we need to compute what is $F_{n+1}$.
We have $F_{1}=\binom{0}{0}=1$, $F_2=\binom{2}{0}+\binom{1}{1}=1+1=2$. Now
$$\begin{align}F_{n+2}&=\sum_{k=0}^{[(n+1)/2]}\binom{n+1-k}{k}\\&=\sum_{k=0}^{[(n+1)/2]}\left(\binom{n-k}{k}+\binom{n-k}{k+1}\right)\\&=F_{n+1}+F_{n}\end{align}$$
This is the (one) definition of the Fibonacci numbers. I wasn't expecting that.
We can write an explicit formula for them.
