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

Author

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

Keywords

• nonn
• tabf

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)

Examples

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

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..8190
• John M. Campbell, A generalization of Deterministic Finite Automata related to discharging, arXiv:2506.14072 [cs.FL], 2025. See p. 7.
• 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)

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.

Programs

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

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

Extensions

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