A131271 Triangular array T(n,k), n>=0, k=1..2^n, read by rows in bracketed pairs such that highest ranked element is bracketed with lowest ranked.

1, 1, 2, 1, 4, 2, 3, 1, 8, 4, 5, 2, 7, 3, 6, 1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11, 1, 32, 16, 17, 8, 25, 9, 24, 4, 29, 13, 20, 5, 28, 12, 21, 2, 31, 15, 18, 7, 26, 10, 23, 3, 30, 14, 19, 6, 27, 11, 22, 1, 64, 32, 33, 16, 49, 17, 48, 8, 57

Offset

0,3

Comments

In a knockout competition with 2^n players, arranging the competition brackets (see Wikipedia) in T(n,k) order, where T(n,k) is the rank of the k-th player, ensures that highest ranked players cannot meet until the later stages of the competition. None of the top 2^p ranked players can meet earlier than the p-th from last round of the competition. At the same time the top ranked players in each match meet the lowest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the highest ranked player possible is A049773. - Colin Hall, Feb 28 2012

Ranks in natural order of 2^n increasing real numbers appearing in limit cycles of interval iterations, or Median Spiral Order. [See the works by Demongeot & Waku]

From Andrey Zabolotskiy, Dec 06 2024 (Start):

For n>0, row n-1 is the permutation relating row n of Kepler's tree of fractions with row n of the left half of Stern-Brocot tree. Specifically, if K_n(k) [resp. SB_n(k)] is the k-th fraction in the n-th row of A294442 [resp. A057432], where 1/2 is in row 1 and k=1..2^(n-1), then K_n(k) = SB_n(T(n-1, k)).

The inverse permutation is row n of A088208.

When 1 is subtracted from each term, rows 3-5 become A240908, A240909, A240910. (End)

Links

Alois P. Heinz, Table of n, a(n) for n = 0..8190

Jacques Demongeot and Jules Waku, Counter-Examples about Lower- and Upper-Bounded Population Growth, Math. Pop. Studies 12 (2005), 199-210.

Jacques Demongeot and Jules Waku, Application of interval iterations to the entrainment problem in respiratory physiology, Phil. Trans. R. Soc. A, 367 (2009), 4717-4739.

Wikipedia, Bracket (tournament)

Formula

T(0,1) = 1, T(n,2k-1) = T(n-1,k), T(n,2k) = 2^n+1 - T(n-1,k).

T(n,1) = 1; for 1 < k <= 2^n, T(n,k) = 1 + (2^n)/m - T(n,k-m), where m = A006519(k-1). - Mathew Englander, Jun 20 2021

Example

Triangle begins:
1;
1,  2;
1,  4, 2, 3;
1,  8, 4, 5, 2,  7, 3,  6;
1, 16, 8, 9, 4, 13, 5, 12, 2, 15, 7, 10, 3, 14, 6, 11;
...

Maple

T:= proc(n, k) option remember;
      `if`({n, k} = {1}, 1,
      `if`(irem(k, 2)=1, T(n-1, (k+1)/2), 2^(n-1)+1 -T(n-1, k/2)))
    end:
seq(seq(T(n, k), k=1..2^(n-1)), n=1..7); # Alois P. Heinz, Feb 28 2012, with offset 1

Mathematica

T[0, 1] = 1;
T[n_, k_] := T[n, k] = If[Mod[k, 2] == 1, T[n, (k + 1)/2], 2^n + 1 - T[n, k/2]];
Table[T[n, k], {n, 0, 6}, {k, 2^n}] // Flatten (* Jean-François Alcover, May 31 2018, after Alois P. Heinz *)

Crossrefs

Cf. A049773, A088208, A294442, A057432.

Cf. A005578 (last elements in rows), A155944 (T(n,2^(n-1)) for n>0).

Cf. A006519, A240908, A240909, A240910.

Sequence in context: A123755 A118291 A118290 * A208569 A341392 A351886

Adjacent sequences: A131268 A131269 A131270 * A131272 A131273 A131274

Keyword

nonn,tabf

Author

J. Demongeot (Jacques.Demongeot(AT)imag.fr), Jun 24 2007

Extensions

Edited (with new name from Colin Hall) by Andrey Zabolotskiy, Dec 06 2024

Status

approved