A369802 -id:A369802 - 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}).

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

Darío Clavijo, Aug 30 2024

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

			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

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.

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

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

A368783 Lexicographic rank of the permutation which is the Eytzinger array layout of n elements.

Original entry on oeis.org

0, 0, 1, 2, 15, 82, 402, 2352, 22113, 220504, 2329650, 26780256, 293266680, 3505934160, 45390355920, 633293015040, 10873520709273, 195823830637744, 3698406245739330, 73192513664010816, 1509611621730135000, 32576548307761013760, 734272503865161846480

Offset: 0

Darío Clavijo, Feb 15 2024

nonn

The Eytzinger array layout (A375825) arranges elements so that a binary search can be performed starting at element k=1 and at a given k step to 2*k or 2*k+1 according as the target is smaller or larger than the element at k.

The lexicographic rank of a permutation of n elements is its position in the ordered list of all possible permutations of n elements, and here taking the first permutation as rank 0.

geeksforgeeks.org, Lexicographic rank of a String
Sergey Slotin, Eytzinger binary search
sympy.org, Permutation rank

Cf. A030298, A369802, A370006, A375825.

from sympy.combinatorics.permutations import Permutation
def a(n):
  if n == 0: return 0
  def eytzinger(t, k=1, i=0):
    if (k < len(t)):
      i = eytzinger(t, k * 2, i)
      t[k] = i
      i += 1
      i = eytzinger(t, k * 2 + 1, i)
    return i
  t = [0] * (n+1)
  eytzinger(t)
  return Permutation(t[1:]).rank()
print([a(n) for n in range(0, 24)])

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python