# Permutation Its Own Inverse?

franktaw at netscape.net franktaw at netscape.net
Thu Jul 13 06:48:06 CEST 2006

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

```

More information about the SeqFan mailing list