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