Permutation $\pi$ of $\{1,\dots,n\}$ is called stable if the set $\{\pi (k)-k|k=1,\dots,n\}$ is consisted of exactly two different elements. Prove that the number of stable permutation of $\{1,\dots,n\}$ equals to $\sigma (n)-\tau (n)$ in which $\sigma (n)$ is the sum of positive divisors of $n$ and $\tau (n)$ is the number of positive divisors of $n$. Time allowed for this problem was 75 minutes.
Problem
Source: Iran 3rd round 2009 - final exam problem 2
Tags: combinatorics unsolved, combinatorics
04.01.2015 00:54
It's very much combinatorics. Part 1 of a solution: We see $\sigma(n)-\tau(n)$ and we realize that this number is $\sum_{d|n}d-1$. Then we look at the stable permutations for $n= 4$ (you can look for 2 and 3, too, but they aren't very interesting), and what we see is (in cycle notation) the following things: (12)(34) (13)(24) (1234) (1432) So who are these, and how should they be grouped to form a set of size $2-1=1$ and a set of size $4-1=3$? The answer is that they are exactly the non-identity powers of the permutations $(1\cdots d)(d+1\,\cdots\, 2d)\cdots(n-d+1\,\cdots\,n)$. Moreover it's very easy to see that every such permutation works, and that there are the right number of them. So all the work must go to showing that there are no others.
09.11.2019 23:12
We wish to show that the number of stable permutations is $\sum_{d | n} (d-1).$ For a stable permutation $\pi$ of $[n]$, we will say that its type is the pair $(a, -b)$ of integers with $a, b \in \mathbb{N}$ so that $\pi(x) - x \in \{a, b\}$ for all $x \in [n].$ Let $\gcd(a, b)$ be its inefficiency . Lemma. $[n]$ has exactly $n-1$ stable permutations with inefficiency $1$. Proof. Call these stable permutations special. We will show that there are $\phi(d)$ special permutations so that the absolute difference of the two integers in its type is $d$, for any $d | n$ greater than $1.$ Fix some $d|n$ which is greater than $1.$ It will suffice to show that for any $1 \le a < d$ with $\gcd(a, d) = 1,$ there's exactly one special permutation with type $(a, a-d).$ To show this, simply note that the permutation is fixed. For $1 \le i \le d-a$, it's clear that we must add $a.$ For $d-a < i \le d$ we must subtract $(d-a)$, as else $1, 2, \cdots, a$ have nothing mapping to them. This means that the first $d$ elements form a cycle on their own. Repeating this with the next $d$ elements and so on, it's clear that the permutation is unique. From here, $\sum_{d | n, d> 1} \phi(d) = n-1$ proves the lemma. $\blacksquare$ From the lemma, we can do casework on the inefficiency of stable permutations to solve the problem. $\square$