Notes on the organization number of a permutation.

Date: Sat, 19 Aug 2006 21:13:49 -0400 (EDT)
From: Graham Cormode (graham(AT)dimacs.rutgers.edu)

One can build a permutation with "organization number" floor(n^2/2) - 1 by

2, 4, 6, ... 2floor(n/2), 1, 2ceil(n/2)-1, 2ceil(n/2)-3, ... 5, 3

For the equivalent problem of finding a permutation with maximal sum of
absolute differences of adjacent terms, we generate

floor(n/2)+1, 1, n, 2, n-1, ... floor(n/2)+2(n mod 2)

So A047838 is an lower bound on the organization number.  

Now consider the first above permutation as a cyclic permutation, because
n is always adjacent to 1 we obtain a cyclic cost of floor(n^2/2).  
Similarly, for the max adjacent difference version of the problem, one can
show a cyclic permutation with this cost.  But (if A007590 is correct), we
cannot find a cyclic permutation with higher cost i.e.

floor(n^2/2) <= organization number + 1 <= A007590 = floor(n^2/2)

Room E275, AT&T Labs--Research, 180 Park Avenue, NJ 07932
973-360-8957 | http://cormode.org | caecilius est in horto