cp's OEIS Frontend

Complement of A047838.

A135152 is a companion triangle, both having row sums = A047838: (1, 3, 7, 11, 17, 23, 31, 39, ...).

Row sums = A047838: (1, 3, 7, 11, 17, 23, 31, 39, ...). The triangle is a companion to A135151.

Old name: Fill an n X n array with various permutations of the integers 1, 2, 3, 4... n^2. Define the organization number of the n X n array to be the following: Start at 1, count the rectilinear steps to reach 2, then the rectilinear steps to reach 3, etc. Add them up. The array that has the maximum organization number would be the "most disorganized." This sequence is the sequence showing the most disorganized number for n X n arrays starting at 1 X 1.

Similar to sequence A047838.

My computer program worked as follows:

a) generate a permutation

b) place the permutation into the array

c) calculate the array position (row, column) of each integer

d) sort the integers into another array preserving row and column

e) travel the new array from 1..n^2 and summing the absolute value of the differences between the rows of consecutive integers and summing the absolute value of the differences of the columns of consecutive integers. The organization number is the sum of the two sums.

For instance, with the permutation 8, 3, 6, 5, 9, 1, 2, 7, 4 place the integers into a 3 X 3 array as such:

8 3 6

5 9 1

2 7 4

(Notice the next integer is a knight's move away. This is not the only sequence that will give an organization number of 23, but this is why I wonder if the sequence is the same as A098499.)

Then sort the integers preserving their row and column:

number, row, column

1, 2, 3

2, 3, 1

3, 1, 2

4, 3, 3

5, 2, 1

6, 1, 3

7, 3, 2

8, 1, 1

9, 2, 2

Traveling from 1 to 9, the differences in the row numbers are 1, 2, 2, 1, 1, 2, 2, 1 (a sum of 12) and the differences in the column numbers are 2, 1, 1, 2, 2, 1, 1, 1 (a sum of 11) therefore the organization number is 23.

This is basically a traveling salesman variant. - D. S. McNeil, Aug 26 2010

From Andrew Howroyd, Oct 16 2019: (Start)

No permutation with maximal sum of distances between contiguous elements can contain three contiguous elements a, b, c such that a < b < c or a > b > c. Otherwise removing b will not alter the sum and then appending b to the end of the permutation will increase it so that the original permutation could not have been maximal. In this sense all solution permutations are alternating.

For odd n consider an alternating permutation of the form p_1 p_2 ... p_n with p_1 > p2, p_2 < p_3, etc. The sum of distances is given by (p_1 + 2*p_3 + 2*p_5 + ... 2*p_{n-2} + p_n) - 2*(p_2 + p_4 + ... p_{n-1}). This is maximized by choosing the central odd p_i to be as highest possible and the even p_i to be least possible but other than that the order does not alter the sum. Similar arguments can be made for p_1 < p_2 and for the case when n is even.

The above considerations lead to a formula for this sequence with the maximum sum being given by A047838(n). (End)

T(m,n) is defined as follows:

T(m, n) = T(n, m).

T(1, n) = floor(n^2/2) - 1.

T(2, n) = (n+1)^2 - 4.

For m, n >= 3 we have:

T(m, n) = m*n*(m + n)/2 - 3, if m and n are both even;

= m*n*(m + n)/2 - (m + n)/2 - 1, if m and n are both odd;

= m*n*(m + n)/2 - n/2 - 1, if m is odd and n is even.

The disorder number M(G) of a graph G is defined to be the maximal length of a walk along the edges of the graph, according to any ordering of its vertices.

Conjecture: T(m, n) = M(P_m X P_n) where P_m X P_n is the grid graph of size m X n.

The conjecture is proved if m = 1 or n = 1.

The disorder number M(G) of a graph G is defined to be the maximal length of a walk along the edges of the graph, according to any ordering of its vertices.

Conjecture: a(n) = M(P_3 X P_n) where P_3 X P_n is the grid graph of size 3 X n.

A(m, n) ~ Theta((m*n)^2) (see link).