Let ($a_{1}, a_{2},..., a_{n}$) and ($b_{1}, b_{2}, ..., b_{n}$) be two different permutations of $n$ first natural numbers. Prove that we can transform one permutation to another using at most $\dfrac{n(n-1)}{2}$ transposition operations of two adjacent elements (i.e switching the place of two adjacent elements).
Can somebody give me a hint? I have no idea yet.
You can use the logic applied in the bubble sort algorithm. First define the relation $$a_i < a_j \iff a_j \text{ appears before } a_i \text{ in the } b \text{ sequence}$$
Then take the first two elements of the $a$ sequence and swap them if $a_2 < a_1$. Eventually after checking $n-1$ pairs (which produce at most $n-1$ transpositions) the last two entries of the two sequences will be the same. Now repeat the same procedure by for the first $n-2$ pairs in the $a$ sequence (as the last element is already in place) and so on. Eventually you will make at most:
$$1 + 2 + \cdots + (n-1) = \frac{n(n-1)}{2} \text{traspositions}$$
Here's a simple example how it works for $n=4$. Let $\{a\} = (1,3,2,4); \{b\} = (2,4,3,1)$.
Take the first two elements of the first sequence and switch them, as $3<1$ accoriding to the relation defined above. Similarly switch $1$ and $2$ and later $1$ and $4$. So after traversing once the first sequence will be $(3,2,4,1)$.
Now repeat the same procedure for the first three terms. Switch $3$ and $2$ and later $3$ and $4$. After the second traverse the sequence is $(2,4,3,1)$.
Now check the first two elements, but it's clearly that we don't need any switching and eventually we went from $\{a\}$ to $\{b\}$ in $5$ moves, which is less than $\frac{4(4-1)}{2} = 6$