Permutation Its Own Inverse?

[franktaw at netscape.net]

Here's a sketch.

First of all, since ceiling(n/k) is monotonically decreasing in k, no 
value less than ceiling(n/k) can have occurred, and for the first 
instance of a ceiling(n/k) = j, j itself cannot have occurred 
previously.  This latter immediately implies that the first instance of 
ceiling(n/k) = j will have T(n,k) = j.  Duplicate values can only occur 
when k > sqrt(n), and exactly the initial values are the ones occurring 
before sqrt(n).  A simple counting argument shows that T(n,k) must then 
= k for the non-initial values.

My apologies if that seems a bit cryptic.  It would probably take a 
couple of pages to write it out in full.

Franklin T. Adams-Watters


-----Original Message-----
From: Max A. <maxale at gmail.com>

  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.

 Could you please give a proof for this statement?

 Thanks,
 Max