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

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, 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, 4, 11, 2, 6, 10, 12, 1, 3, 5, 7, 9, 8, 4, 12, 2, 6, 10, 13, 1, 3, 5, 7, 9, 11

Offset: 1

Author

Darío Clavijo, Aug 30 2024

Keywords

• nonn
• tabl

Comments

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.

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).

Examples

			Triangle begins:
   n  | k 1  2  3  4  5  6  7   8  9  10
  ---------------------------------------
   1  |   1
   2  |   2, 1
   3  |   2, 1, 3
   4  |   3, 2, 4, 1
   5  |   4, 2, 5, 1, 3
   6  |   4, 2, 6, 1, 3, 5
   7  |   4, 2, 6, 1, 3, 5, 7
   8  |   5, 3, 7, 2, 4, 6, 8,  1
   9  |   6, 4, 8, 2, 5, 7, 9,  1, 3
   10 |   7, 4, 9, 2, 6, 8, 10, 1, 3, 5
For n=10, the binary search tree numbered in-order is as follows and row 10 is by reading row-wise.
           7
         /   \
       4       9
     /  \     / \
    2    6   8   10
   /\   /
  1  3  5
		

Links

• Gergely Flamich, Stratis Markou and José Miguel Hernández-Lobato, Fast Relative Entropy Coding with A* coding, arXiv:2201.12857 [cs.IT], 2022. (Section 3)
• Paul-Virak Khuong and Pat Morin, Array Layouts for Comparison-Based Searching, arXiv:1509.05053 [cs.DS], 2017.
• Sergey Slotin, Eytzinger binary search.

Crossrefs

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

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

Programs

Python

def A375825row(n):
    row = [0] * (n + 1)
    def e_rec(j, i):
        if j <= n:
            i = e_rec(2 * j, i)
            row[j] = i
            i = e_rec(2 * j + 1, i + 1)
        return i
    e_rec(1, 1)
    return row