login
Lexicographic ordering of N x N, where N = {1,2,3...}.
8

%I #26 Jul 09 2015 20:05:38

%S 1,1,1,2,2,1,1,3,2,2,3,1,1,4,2,3,3,2,4,1,1,5,2,4,3,3,4,2,5,1,1,6,2,5,

%T 3,4,4,3,5,2,6,1,1,7,2,6,3,5,4,4,5,3,6,2,7,1,1,8,2,7,3,6,4,5,5,4,6,3,

%U 7,2,8,1,1,9,2,8,3,7,4,6,5,5,6,4,7,3,8,2,9,1,1,10,2,9,3,8,4,7,5,6,6,5,7,4,8,3,9,2,10,1,1,11,2,10,3,9,4,8,5,7,6,6,7,5,8,4,9,3,10,2,11,1,1,12,2,11,3,10,4,9,5,8,6,7,7,6,8,5,9,4,10,3,11,2,12,1

%N Lexicographic ordering of N x N, where N = {1,2,3...}.

%F a(2n) = A004736(n), a(2n+1) = A002260(n). - _Michael Somos_, Mar 06 2004

%F Let p(i,j) be the position of (i,j) in the ordering. Then p(i,j) = ((i+j)^2-i-3j+2)/2. Inversely, the pair (i,j) in a given position p is given by i=p-q(q-1)/2 and j=q+1-i, where q=floor((1+sqrt(8k-7))/2).

%e Flatten the ordered lattice points (1,1) < (1,2) < (2,1) < (1,3) < (2,2) < ... as 1,1, 1,2, 2,1, 1,3, 2,2, ...

%t lexicographicLattice[{dim_,maxHeight_}]:= Flatten[Array[Sort@Flatten[(Permutations[#1]&)/@IntegerPartitions[#1+dim-1,{dim}],1]&,maxHeight],1]; Flatten@lexicographicLattice[{2,12}] (* _Peter J. C. Moses_, Feb 10 2011 *)

%t u[x_] := Floor[3/2 + Sqrt[2*x]]; v[x_] := Floor[1/2 + Sqrt[2*x]]; n[x_] := x - v[x]*(v[x] - 1)/2; k[x_] := 1 - x + u[x]*(u[x] - 1)/2; Flatten[Table[{n[m], k[m]}, {m, 45}]] (* _L. Edson Jeffery_, Jun 20 2015 *)

%o (PARI) a(n)= if(n<1, 0, 1+(-1)^(n%2) * (binomial((n+1)%2+(sqrtint(4*n)+1)\2, 2)-n\2)) /* _Michael Somos_, Mar 06 2004 */

%Y Cf. A057554, A057557, A057559.

%Y Cf. A181118.

%K nonn

%O 1,4

%A _Clark Kimberling_, Sep 07 2000

%E Extended by _Clark Kimberling_, Feb 10 2011