1,2

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.

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

Alternate description (of the algorithm, now in example): To each k in 1..n^2, associate a unique position p(k) = (row(k), col(k)) with row(k), col(k) in 1..n (= 1, ..., n). Then organization_number(p) = Sum_{k=2..n^2} |p(k) - p(k-1)|, where |(x,y)| = |x| + |y| is the taxicab- or 1-norm. The sum can also be written as |p' - p"|, where p' = p(2..n^2), p" = p(1..n^2-1) are vectors with n^2-1 2D-components, and |.| is again the 1-norm. - M. F. Hasler, Sep 05 2025

Sela Fried, On a conjecture of McNeil, arXiv:2208.03788 [math.CO], 2023.

Eric Weisstein's World of Mathematics, Disorder Number.

Eric Weisstein's World of Mathematics, Grid Graph

A possible formula: a(n) = 0 for n=1, n^3-n-1 for odd n > 1, n^3-3 for even n? - D. S. McNeil, Aug 26 2010

Let b(n) correspond to McNeil's formula. Then b(n) <= a(n) <= b(n) + 1 (see link). - Sela Fried, Nov 28 2023

Empirical G.f.: x^2*(5+13*x+10*x^2-6*x^3+x^4+x^5)/((1-x)^4*(1+x)^2). - Colin Barker, Mar 29 2012

[Original example, reworded by M. F. Hasler, Sep 05 2025]

To compute an organization number, we proceed as follows:

a) Fill an n X n array with a permutation of (1, ..., n^2).

b) List the positions (row, column) of the elements, from 1 to n^2.

c) Sum the absolute value of the differences between the rows of consecutive integers, and also for the columns of consecutive integers. The organization number is the sum of the two sums.

For instance, the permutation 8, 3, 6, 5, 9, 1, 2, 7, 4 gives the 3 X 3 array

8 3 6

5 9 1

2 7 4

(Here the next integer is always a knight's move away, except for the final 9, which gives a result of 7*3 + 2 = 23. This is not the only permutation that will give 23, but this is why I wonder if the sequence is the same as A098499.) [Remark: It isn't, the terms for n=4 differ. - M. F. Hasler, Sep 05 2025]

Now we list the integers with 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), so we get again the organization number 23.

(PARI) /* Compute organization number of permutation p of 1..n^2 */

ON(p, n=sqrtint(#p))={p=[divrem(k-1, n)|k<-vecsort(p, , 1)]; normlp(p[^1]-p[^#p], 1)}

/* Compute the largest of all ON(p) for all n²! partitions of 1..n^2.

(For illustration only -- Not usable for n > 3, since 16! ~ 2e14.) */

a(n)={my(m); forperm(n^2, p, ON(p)>m && m=ON(p)); m} \\ M. F. Hasler, Sep 05 2025

Cf. A047838, A098499.

Sequence in context: A362338 A098498 A159241 * A373538 A176874 A331987

Adjacent sequences: A179091 A179092 A179093 * A179095 A179096 A179097

nonn,more

Thomas Young, Jun 29 2010

a(4) corrected and a(5)-a(17) computed by D. S. McNeil, Aug 26 2010. D. S. McNeil also finds that a(19) = 6839, a(21) = 9239, a(23) = 12143.

Edited by N. J. A. Sloane, Aug 26 2010

Typo in formula corrected by D. S. McNeil, Aug 26 2010

Simpler name from Eric W. Weisstein, Oct 08 2024

approved