6
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ Do your "moves" (as in the title) and "times" (as in "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") mean the same thing? What to do next when you translate the card $x-1$ to the beginning? $\endgroup$ Nov 17, 2021 at 13:12
  • $\begingroup$ @Miscellaneous yes time and moves are the same. When we put the card x-1 to the beginning we have to check if the cards are sorted in ascending order, and if not then we have to find the cards with a number one lower than this one and give it to the beginning. Also if the first card equals 1 and the sequence is not sorted, we start with the largest card, i.e. the one with the number n $\endgroup$
    – Matey
    Nov 17, 2021 at 17:04
  • $\begingroup$ You never need to pull the highest card to the front. For example, 132 is more quickly sorted as 132-213-123. Basically, just find the highest card k that lies somewhere to the right of card k+1, and start with that card k. In other words, find the highest inverted pair of consecutive values and swap them. The cards k+1 and higher will fall into place automatically when all the lower cards have been sorted. $\endgroup$ Nov 18, 2021 at 13:02
  • $\begingroup$ @user3257842 Notice that moving an element $x$ to the beginning increases the distance from the beginning to elements with smaller index than $x$ by $1$. That is, we are counting inversions. This is easy to count across permutations that start with $n$ (total number of inversions is A001809). But, it gets tricky otherwise because sorting $(a_1,a_2,\dots, a_n),a_1\ne n$ first goes to $(n,1,2,\dots,a_1,b_1,b_2,\dots,b_k)$, only then elements $1,2,\dots, a_1$ get moved again after moving all $b_i\gt a_1$. $\endgroup$
    – Vepir
    Nov 18, 2021 at 17:11

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ Eg: for $n=3$ we have $3! *(3-1)* (\frac{5}{4}*3 - (\frac{1}{0!} + \frac{1}{1!} + \frac{1}{2!})) = 3! * 2 * (\frac{15}{4}- (2 + \frac{1}{2})) = 12 * \frac{5}{4} = 15$ $\endgroup$ Nov 18, 2021 at 14:37
  • $\begingroup$ I noticed too that the number of movers for sequences starting with $n$ is easy to count. Define "balancing" a sequence as incrementing every element mod $n$ until its starting element becomes $n$. Ie. the "balance" of $(2,1,5,3,4)$ is $(5,4,3,1,2)$ . I've added $3$ to every element to "balance it". If you compute the difference between the number of moves needed for an arbitrary sequence and its balanced counterpart, the result will be of the form $(n-1)*k$ where $k\in\{-(n-1),\dots (n-2)\}$. I've counted how many sequences give each particular value of difference to guess the sum. $\endgroup$ Nov 18, 2021 at 16:56
  • $\begingroup$ I suspect a rigorous proof will have to account for how many times the sequence changes its starting value when moving to a fully-ordered state. This is not easy as the number can exceed $n$, as it goes around. $\endgroup$ Nov 18, 2021 at 17:02
  • $\begingroup$ Thanks a lot for the derivation of the formula, and most of all for proving it. It helped me a lot to understand this toppic :) . Could you further explain to me how I could calculate this on a computer using modulo operation? I have a problem with counting moves for large n. $\endgroup$
    – Matey
    Nov 19, 2021 at 23:19
  • $\begingroup$ I derived the formula because it seemed like an interesting challenge. If you want to compute it modulo $10^9+7$ you should at least figure out the modulo part yourself. ;) $\endgroup$ Nov 20, 2021 at 7:19

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .