A375825 - OEIS

%I #67 Sep 02 2024 03:47:56

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

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

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

%N Triangle read by rows where row n is the Eytzinger array layout of n elements (a permutation of {1..n}).

%C The Eytzinger layout arranges elements of an array so that a binary search can be performed starting with index k = 1 and at a given k step to 2*k or 2*k+1, according to whether the target is smaller or larger than the element at k.

%C Row n is formed by: Take a binary search tree of n vertices which is a complete tree except for a possibly incomplete last row; number the vertices 1 to n by an in-order traversal; then read those vertex numbers row-wise (breadth first).

%H Gergely Flamich, Stratis Markou and José Miguel Hernández-Lobato, <a href="https://doi.org/10.48550/arXiv.2201.12857">Fast Relative Entropy Coding with A* coding</a>, arXiv:2201.12857 [cs.IT], 2022. (Section 3)

%H Paul-Virak Khuong and Pat Morin, <a href="https://doi.org/10.48550/arXiv.1509.05053">Array Layouts for Comparison-Based Searching</a>, arXiv:1509.05053 [cs.DS], 2017.

%H Sergey Slotin, <a href="https://algorithmica.org/en/eytzinger">Eytzinger binary search</a>.

%e Triangle begins:

%e    n  | k 1  2  3  4  5  6  7   8  9  10

%e   ---------------------------------------

%e    1  |   1

%e    2  |   2, 1

%e    3  |   2, 1, 3

%e    4  |   3, 2, 4, 1

%e    5  |   4, 2, 5, 1, 3

%e    6  |   4, 2, 6, 1, 3, 5

%e    7  |   4, 2, 6, 1, 3, 5, 7

%e    8  |   5, 3, 7, 2, 4, 6, 8,  1

%e    9  |   6, 4, 8, 2, 5, 7, 9,  1, 3

%e    10 |   7, 4, 9, 2, 6, 8, 10, 1, 3, 5

%e For n=10, the binary search tree numbered in-order is as follows and row 10 is by reading row-wise.

%e            7

%e          /   \

%e        4       9

%e      /  \     / \

%e     2    6   8   10

%e    /\   /

%e   1  3  5

%o (Python)

%o def A375825row(n):

%o     row = [0] * (n + 1)

%o     def e_rec(j, i):

%o         if j <= n:

%o             i = e_rec(2 * j, i)

%o             row[j] = i

%o             i = e_rec(2 * j + 1, i + 1)

%o         return i

%o     e_rec(1, 1)

%o     return row

%Y Cf. A000217 (row sums), A375544 (alternating row sums), A006257 (main diagonal, (central terms)/2), A006165 (col 1).

%Y Cf. A368783 (rank), A370006 (SJT rank), A369802 (inversions).

%K nonn,tabl

%O 1,2

%A _Darío Clavijo_, Aug 30 2024