cp's OEIS Frontend

A179094 Disorder number of the n X n grid graph.

%I A179094 #32 Oct 10 2024 13:23:29
%S A179094 0,5,23,61,119,213,335,509,719,997,1319,1725,2183,2741,3359,4093,4895
%N A179094 Disorder number of the n X n grid graph.
%C A179094 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.
%C A179094 Similar to sequence A047838.
%C A179094 My computer program worked as follows:
%C A179094 a) generate a permutation
%C A179094 b) place the permutation into the array
%C A179094 c) calculate the array position (row, column) of each integer
%C A179094 d) sort the integers into another array preserving row and column
%C A179094 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.
%C A179094 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:
%C A179094    8 3 6
%C A179094    5 9 1
%C A179094    2 7 4
%C A179094 (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.)
%C A179094 Then sort the integers preserving their row and column:
%C A179094   number, row, column
%C A179094    1, 2, 3
%C A179094    2, 3, 1
%C A179094    3, 1, 2
%C A179094    4, 3, 3
%C A179094    5, 2, 1
%C A179094    6, 1, 3
%C A179094    7, 3, 2
%C A179094    8, 1, 1
%C A179094    9, 2, 2
%C A179094 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.
%C A179094 This is basically a traveling salesman variant. - _D. S. McNeil_, Aug 26 2010
%H A179094 Sela Fried, <a href="https://arxiv.org/abs/2208.03788">On a conjecture of McNeil</a>, arXiv:2208.03788 [math.CO], 2023.
%H A179094 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/DisorderNumber.html">Disorder Number</a>.
%H A179094 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>
%F A179094 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
%F A179094 Let b(n) correspond to McNeil's formula. Then b(n) <= a(n) <= b(n) + 1 (see link). - _Sela Fried_, Nov 28 2023
%F A179094 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
%Y A179094 Cf. A047838, A098499.
%K A179094 nonn,more
%O A179094 1,2
%A A179094 _Thomas Young_, Jun 29 2010
%E A179094 a(3) corrected and a(4)-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.
%E A179094 Edited by _N. J. A. Sloane_, Aug 26 2010
%E A179094 Typo in formula corrected by _D. S. McNeil_, Aug 26 2010
%E A179094 Equivalent simpler description from _Eric W. Weisstein_, Oct 08 2024