cp's OEIS Frontend

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

%I A375825 #67 Sep 02 2024 03:47:56
%S A375825 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 A375825 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 A375825 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 A375825 Triangle read by rows where row n is the Eytzinger array layout of n elements (a permutation of {1..n}).
%C A375825 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 A375825 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 A375825 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 A375825 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 A375825 Sergey Slotin, <a href="https://algorithmica.org/en/eytzinger">Eytzinger binary search</a>.
%e A375825 Triangle begins:
%e A375825    n  | k 1  2  3  4  5  6  7   8  9  10
%e A375825   ---------------------------------------
%e A375825    1  |   1
%e A375825    2  |   2, 1
%e A375825    3  |   2, 1, 3
%e A375825    4  |   3, 2, 4, 1
%e A375825    5  |   4, 2, 5, 1, 3
%e A375825    6  |   4, 2, 6, 1, 3, 5
%e A375825    7  |   4, 2, 6, 1, 3, 5, 7
%e A375825    8  |   5, 3, 7, 2, 4, 6, 8,  1
%e A375825    9  |   6, 4, 8, 2, 5, 7, 9,  1, 3
%e A375825    10 |   7, 4, 9, 2, 6, 8, 10, 1, 3, 5
%e A375825 For n=10, the binary search tree numbered in-order is as follows and row 10 is by reading row-wise.
%e A375825            7
%e A375825          /   \
%e A375825        4       9
%e A375825      /  \     / \
%e A375825     2    6   8   10
%e A375825    /\   /
%e A375825   1  3  5
%o A375825 (Python)
%o A375825 def A375825row(n):
%o A375825     row = [0] * (n + 1)
%o A375825     def e_rec(j, i):
%o A375825         if j <= n:
%o A375825             i = e_rec(2 * j, i)
%o A375825             row[j] = i
%o A375825             i = e_rec(2 * j + 1, i + 1)
%o A375825         return i
%o A375825     e_rec(1, 1)
%o A375825     return row
%Y A375825 Cf. A000217 (row sums), A375544 (alternating row sums), A006257 (main diagonal, (central terms)/2), A006165 (col 1).
%Y A375825 Cf. A368783 (rank), A370006 (SJT rank), A369802 (inversions).
%K A375825 nonn,tabl
%O A375825 1,2
%A A375825 _Darío Clavijo_, Aug 30 2024