A370006 -id:A370006

Search: a370006 -id:a370006

Displaying 1-2 of 2 results found.

page 1

A375825

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

+10
6

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

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

1,2

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

LINKS

Table of n, a(n) for n=1..91.

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.

EXAMPLE

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.

/ \

4 9

/ \ / \

2 6 8 10

/\ /

1 3 5

PROG

(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

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

KEYWORD

nonn,tabl

AUTHOR

Darío Clavijo, Aug 30 2024

STATUS

approved

A368783

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

+10
1

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

COMMENTS

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.

LINKS

Table of n, a(n) for n=0..22.

geeksforgeeks.org, Lexicographic rank of a String

Sergey Slotin, Eytzinger binary search

sympy.org, Permutation rank

PROG

(Python)

from sympy.combinatorics.permutations import Permutation

def a(n):

def eytzinger(t, k=1, i=0):

if (k < len(t)):

i = eytzinger(t, k * 2, i)