A375825 -id:A375825 - cp's OEIS frontend

A375544 a(n) = Sum_{1..n+1} (-1)^(n-k) A375825(n, k).

0, 1, -1, 4, -4, 9, -5, 12, -12, 17, -15, 24, -16, 29, -17, 32, -32, 37, -35, 44, -38, 53, -43, 60, -44, 65, -47, 72, -48, 77, -49, 80, -80, 85, -83, 92, -86, 101, -91, 108, -94, 117, -101, 128, -106, 137, -111, 144, -112, 149, -115, 156, -118, 165, -123, 172

Offset: 0

Peter Luschny, Aug 31 2024

sign

Cf. A375825.

A369802 Inversion count of the Eytzinger array layout of n elements.

Original entry on oeis.org

0, 0, 1, 1, 4, 6, 7, 7, 14, 20, 25, 29, 32, 34, 35, 35, 50, 64, 77, 89, 100, 110, 119, 127, 134, 140, 145, 149, 152, 154, 155, 155, 186, 216, 245, 273, 300, 326, 351, 375, 398, 420, 441, 461, 480, 498, 515, 531, 546, 560, 573, 585, 596, 606, 615, 623, 630

Offset: 0

Darío Clavijo, Feb 01 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.

This layout is a permutation of the elements and its inversion count (number of swaps needed to sort by the bubble sort algorithm) is a measure of how much it differs from an ordinary sorted array.

			For n=5, the Eytzinger array layout is {4, 2, 5, 1, 3} and it contains a(5) = 6 element pairs which are not in ascending order (out of 10 element pairs altogether).

Sergey Slotin, Eytzinger binary search

Cf. A006095, A261692, A375825.

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)
      t[k] = i
      i += 1
      i = eytzinger(t, k * 2 + 1, i)
    return i
  t = [0] * (n+1)
  eytzinger(t)
  return Permutation(t[1:]).inversions()
print([a(n) for n in range(0, 58)])

a(2^n-1) = A006095(n).

Conjecture: a(n) = (A261692(n)-n)/2.

A370006 Steinhaus-Johnson-Trotter rank of the Eytzinger array layout of n elements.

Original entry on oeis.org

0, 0, 1, 5, 14, 102, 603, 4227, 24942, 311276, 3039543, 33478363, 401734770, 5222553212, 73115744891, 1096736173379, 12943332326750, 305107217238968, 5362734402377967, 102024181104606979, 2040455253185256114, 42849570085332342072, 942690540710286167499, 21681882436603204659939

Offset: 0

Darío Clavijo, Feb 07 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.
Permutations are ranked here starting from 0 for the first permutation of n elements.
A207324 is all permutations in Steinhaus-Johnson-Trotter order, so that its row number !n + a(n) is the Eytzinger array of n elements, for n>=1 and where !n = A003422(n) is the left factorial.

Sergey Slotin, Eytzinger binary search
sympy.org, Permutations
Wikipedia, Trotter algorithm

Cf. A003422, A207324, A375825.

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)
      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_trotterjohnson()
print([a(n) for n in range(0, 27)])

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

A375469 Triangle read by rows: a permutation of the nonnegative integers based on the Eytzinger order.

Original entry on oeis.org

0, 2, 1, 4, 3, 5, 8, 7, 9, 6, 13, 11, 14, 10, 12, 18, 16, 20, 15, 17, 19, 24, 22, 26, 21, 23, 25, 27, 32, 30, 34, 29, 31, 33, 35, 28, 41, 39, 43, 37, 40, 42, 44, 36, 38, 51, 48, 53, 46, 50, 52, 54, 45, 47, 49, 62, 58, 64, 56, 60, 63, 65, 55, 57, 59, 61

Offset: 0

Peter Luschny, Sep 01 2024

Let T(n) denote the triangular numbers. Set, for n >= 0, I(n) = [T(n), T(n+1)), lower bound included, upper bound excluded. Applying the Eytzinger ordering to I(n) gives E(n) = [A375825(n + 1, k + 1) + T(n) - 1 for k in 0..n]. Joining E(0), E(1), E(2), ... gives a permutation of the nonnegative integers. The Eytzinger order of 1..n is described in A375825.

			Triangle starts:
  I(n)   ->                   E(n)
  --------------------------------------------------
  0      -> [ 0]
  1..2   -> [ 2,  1]
  3..5   -> [ 4,  3,  5]
  6..9   -> [ 8,  7,  9, 6]
  10..14 -> [13, 11, 14, 10, 12]
  15..20 -> [18, 16, 20, 15, 17, 19]
  21..27 -> [24, 22, 26, 21, 23, 25, 27]
  28..35 -> [32, 30, 34, 29, 31, 33, 35, 28]
  36..44 -> [41, 39, 43, 37, 40, 42, 44, 36, 38]
  45..53 -> [51, 48, 53, 46, 50, 52, 54, 45, 47, 49]

Maxim Zaks, Binary Search vs. Eytzinger Order, blog post, 2020.

Cf. A375825.

Erow := proc(n) local E, row, i, j;
    row := [seq(0, 0..n)]:
    E := proc(n, k, i) option remember; j := i:
    if k <= n + 1 then
        j := E(n, 2 * k, j): row[k] := j:
        j := E(n, 2 * k + 1, j + 1):
    fi: j end:
    E(n, 1, 0):
row end:
Trow := n -> local k; seq((n*(n + 1)/2) + Erow(n)[k + 1], k = 0..n):
seq(Trow(n), n = 0..10);

def A375469row(n: int) -> list[int]:
    t = n * (n + 1) // 2
    return [A375825row(n + 1)[k + 1] + t - 1 for k in range(n + 1)]
print([A375469row(n)[k] for n in range(11) for k in range(n + 1)])

A375959 Partial products of A006257.

Original entry on oeis.org

1, 1, 3, 3, 9, 45, 315, 315, 945, 4725, 33075, 297675, 3274425, 42567525, 638512875, 638512875, 1915538625, 9577693125, 67043851875, 603394666875, 6637341335625, 86285437363125, 1294281560446875, 22002786527596875, 418052944024340625, 8779111824511153125, 201919571963756521875

Offset: 1

Darío Clavijo, Sep 03 2024

Also the determinant of the n X n lower triangular matrix where row j is the Eytzinger array permutation of {1,2,...,j} (A375825), and similarly any lower triangular matrices with A006257 on their diagonal.

a(n) = a(n-1) iff n = 2^k, since those n are where A006257(n) = 1. - Stefano Spezia, Sep 06 2024

			For n = 9, a(9) = 1*1*3*1*3*5*7*1*3 = 945.

Sergey Slotin, Eytzinger binary search.

Cf. A006257, A375825.

Table[Product[Flatten[Table[Range[1, 2^n - 1, 2], {n, 1, 6}]][[i]],{i,n}],{n,1,27}] (* James C. McMahon, Sep 19 2024 *)

a(n) = prod(k=1, n, 2*k-2^logint(2*k, 2)+1); \\ Michel Marcus, Sep 06 2024

from sympy import prod
a = lambda n: prod(((j-(1 << j.bit_length()-1))<<1)+1 for j in range(1, n+1))
print([a(n) for n in range(1, 28)])

a(n) = Product_{k=1..n} A006257(k).

cp's OEIS Frontend

A375544 a(n) = Sum_{1..n+1} (-1)^(n-k) A375825(n, k).

Views

Author

Keywords

Crossrefs

A369802 Inversion count of the Eytzinger array layout of n elements.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

A370006 Steinhaus-Johnson-Trotter rank of the Eytzinger array layout of n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Python

A375469 Triangle read by rows: a permutation of the nonnegative integers based on the Eytzinger order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Python

A375959 Partial products of A006257.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula