Permutation Its Own Inverse?

[Max A.]

On 7/12/06, franktaw at netscape.net <franktaw at netscape.net> wrote:
> Yes, it is (its own inverse - it isn't all that easily answered).
>
> It is easiest to subtract out the triangular numbers, making each row
> its own permutation:
>
> 1
> 2,1
> 3,2,1
> 4,2,3,1
> 5,3,2,4,1
> 6,3,2,4,5,1
> 7,4,3,2,5,6,1
> ...
>
> We can now see the rule: if ceiling(n/ceiling(n/k)) = k, then T(n,k) =
> ceiling(n/k); otherwise T(n,k) = k.  Equivalently, for each pair i, j
> with i*j >= n, but (i-1)*j and i*(j-1) < n, we have T(n,i) = j, T(n,j)
> = i.  For any other k, T(n,k) = k.

Rustem Aidagulov gave the following proof for the fact that for a
fixed n, T(n,k) is a permutation.

Let n be a fixed number and T(n,k)=f(k). First give and equivalent
definition of f(k):
f(k) = minimum t such that k*t>=n and t is different from f(1), f(2),
..., f(k-1).
Moreover,
(*)   f(k) = t  if and only if  there exists s >= 0 such that
f({k-1,k-2,...,k-s}) = {t-1,t-2,...,t-s} and f(i)>t for all i<k-s.
It is clear that the value of s can be determined as s = t - ceil(n/k).

Let us prove that f(f(k))=1 by induction on k. For k=1, it is trivial.
Suppose that f(f(j))=j for all j<k.
According to (*), for t=f(k) and s=t-ceil(n/k),
f({k-1,k-2,...,k-s}) = {t-1,t-2,...,t-s}.
Then
{k-1,k-2,...,k-s} = f(f({k-1,k-2,...,k-s})) = f({f(k)-1,f(k)-2,...,f(k)-s})
and for j < t-s = ceil(n/k) we have f(j)>k. Together with (*) that
proves f(t)=k.

Max