We have n cards numbered from 1 to n. We get pre-shuffled cards and we have to sort them in ascending order according to some rules: we look at the number of the first card in the sequence (let's denote it by x) and find the card with the number x - 1 (unless x = 1, it then finds card number n), and then translates it to the beginning. The time it takes to complete this operation is proportional to the distance of the found card from the beginning of the sequence of cards. The time for sorting cards is the sum of all times operations performed. We are to calculate the sum of the operations for all n! permutation.
Example: for n = 3 we have 6 permutation
1 2 3 (0 moves)
1 3 2 ( 1 move ) 3 1 2 (2 moves) 2 3 1 (2 moves) 1 2 3 (summary 5 moves)
2 1 3 ( 1 move ) 1 2 3
2 3 1 (2 moves) 1 2 3
3 1 2 (2 moves) 2 3 1 (2 moves) 1 2 3 (summary 4 moves)
3 2 1 ( 1 move ) 2 3 1 (2 moves) 1 2 3 (summary 3 moves)
getting it all together to sort 3! permutations we needs 15 moves.
for n = 4 we needs 168 moves
for n = 5 we needs 1700 moves
for n = 6 we needs 17,220 moves
for n = 7 we needs 182,406 moves
for n = 8 we needs 2,055,200 moves
For small n we can easly calculate it using a brute force algorithm, but how to do it for large n like 100,000 or bigger. Is it any mathematical formula to count all possibilities ? I have no idea how to go about it, do you have any usefull tips ? What area of mathematics describes this issue ?????????
I've found a closed-form formula by playing around with the numbers, tough I haven't been able to come up with a complete proof yet. We have:
$$f(n) = n!\;(n-1)(\frac{5}{4}n - \sum_{k=0}^{n-1}\frac{1}{k!}) = \\ =(n-1)(1 + n!\;(\frac{5}{4}n) - [e *n!]) $$
If you don't have fractions (and can't approximate $e$ to the required precision), I recommend distributing the $n!$ over that sum so you can work with integers.
If you only need an approximate number, for large $n$ we can say $$f(n) \approx n!\;(n-1)(\frac{5}{4}n -e)$$ where $e$ is Euler's number.
Edit: Here is a sketch of a proof. First to count the number of moves required for sequences starting with $n$. Of these, the sequence $(n,n-1\dots 1)$ is the one with the smallest number of moves, namely $n(n-1)/2$. For any other $n$-starting sequence $p$ we observe the number of moves increases whenever a larger number that is to the right of $n$ has to jump leftwards over a smaller number. This gives the following:
Theorem 1: The number of moves required for $p$ starting with $n$ is $n(n-1)/2 + T_{p}$ , where $T_{p}$ is the number of tuples $(x,y)$ such that $x<y$ and $p_{x}<p_{y}$.
For a random sequence starting with $n$, there are $(n-2)(n-1)/2$ tuples (excluding those formed with the starting element $n$), and each has an equal probability of being increasing or decreasing. Thus $T_{p}$ is on average $(n-1)(n-2)/4$.
Let $m(p)$ be the number of moves needed for a sequence $p$.
Define $s(p)$ to be one plus the number of times the starting value of the sequence $p$ changes as it moves towards an ordered sequence. To take examples from the post, we have $s(1,3,2) = 4$ , $s(3,1,2) = 3$ , $s(1,2,3) = 1$
Define $r^n_{k} = (k,k+1,\dots n, 1, 2, \dots k-1)$. We have $m(r^n_{k})= (n-1)(k-1)$. Additionally, $s(n, \dots) = n$.
To compute the number of moves required for a sequence starting with $k\neq n$, we define an operation $b: S_n \rightarrow S_n$, that takes a given sequence of cards and increments each member by a constant value (subtracting $n$ if the result is greater than $n$) such that the starting value of the resulting sequence becomes $n$. Eg. $b(2,1,5,3,4) = (5,4,3,1,2)$ . Here the starting value of the sequence is $2$, so the increment is $n-2 = 3$. This balancing morphism will give us a way to count the number of the number of moves for an arbitrary sequence by relating it to its balanced counterpart, a sequence starting with $n$ (for which the moves are easy to count). The theorem we aim to prove is:
$$m(p) = m(b(p)) + (s(p) - n) (n-1) \tag{1} $$
For a sequence $p$ starting with $k\neq n$, there are two possible values for $s(p)$: Either $s(p) < n$ in which case $s(p) = k$, (corresponding to the transition $k\rightarrow (k-1) \rightarrow \dots 1$ ) or $s(p) > n$ in which case $s(p) = k + n$. (corresponding to the transition $k\rightarrow (k-1) \rightarrow \dots 1 \rightarrow n \rightarrow (n-1) \rightarrow \dots 1$).
We see that there is a parallelism between the moves required to order a sequence $p$ and its balanced counterpart $b(p)$. We may order both simultaneously until one becomes fully ordered and the other becomes of the form $r^{n}_{j}$, for some $j$. If $s(p) > s(b(p))$ then $b(p)$ will become ordered first, and if $s(p) < s(b(p))$ then $p$ becomes ordered first. If $s(p) = s(b(p))$ then $p = b(p)$ (as $s(b(p))$ is always $n$). For our theorem, we will only explicitly prove the case where $s(p) > s(b(p))$ . The other cases can be proved analogously. If $p$ starts with $k$, then the value difference between $p$ and $b(p)$ will be $n-k$. That is maintained as the sequences get ordered, so when $b(p)$ becomes fully ordered then $p$ becomes $r_{k+1}^n$, needing an additional $(k+1-1)(n-1)$ moves to become ordered. As $s(p) > s(b(p)) = n$ we see $s(p) = k + n$, so the result matches our theorem $(1)$.
To complete the formula for counting the moves of a sequence $p$ starting in $k$, we require a reliable way to compute $s(p)$. Namely, when do we have $s(p) = k$ as opposed to $s(p) = n + k$? For this we have the following theorem:
Theorem 2: A sequence $p$ starting in $k$ has $s(p) = k$ if and only if it has $(k,k+1, \dots n)$ as a subsequence. If not, we have $s(p) = n+k$. For example $(2,3,1,4)$ has $(2,3,4)$ as a subsequence, but $(2,4,1,3)$ does not.
This combined with $(1)$ and Theorem 1 gives us a way to fully count the moves required to order an arbitrary sequence, allowing us to compute a formula for the total number of moves of all sequences.
The total number of sequences starting with $k$ that contain $(k,k+1\dots n)$ as a subsequence is ${{n-1}\choose{k-1}} (k-1)! = \frac{(n-1)!}{(n-k)!}$ . Aplying the $(1)$ formula, the difference in their number of moves compared to their balanced counterparts is $\frac{(n-1)!}{(n-k)!}(s(p)-n)(n-1) = \frac{(n-1)!}{(n-k)!}(k-n)(n-1)$. Doing the same for the sequences that do not contain $(k,k+1\dots n)$ as subsequence we get their difference as $( (n-1)!-\frac{(n-1)!}{(n-k)!})(s(p)-n)(n-1) = ( (n-1)!-\frac{(n-1)!}{(n-k)!})k(n-1)$
For the sum over the balanced components the average number of moves over such a component is $\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4}$ giving a total of $(n-1)!(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4})$
Thus the total number moves for sequences starting with $k$ is:
$$\tiny{m_{k} \;= \; \frac{(n-1)!}{(n-k)!}(k-n)(n-1) \;+ \; ( (n-1)!-\frac{(n-1)!}{(n-k)!})k(n-1) \;+ \; (n-1)!(\frac{n(n-1)}{2} + \frac{(n-1)(n-2)}{4}) }$$
By summing over $m_{k}$ for $k\in\{1,\dots n\}$ and grouping the terms, we recover our original formula.