login
A208569
Triangular array T(n,k), n>=1, k=1..2^(n-1), read by rows in bracketed pairs such that highest ranked element is bracketed with lowest ranked.
3
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
1,3
COMMENTS
In a knockout competition with m players, arranging the competition brackets (see links) in T(m,k) order, where T(m,k) is the rank of the 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.
LINKS
FORMULA
T(1,1) = 1, T(n,2k-1) = T(n-1,k), T(n,2k) = 2^(n-1)+1 - T(n-1,k).
T(n,1) = 1; for 1 < k <= 2^(n-1), T(n,k) = 1 + (2^n)/(2*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
MATHEMATICA
T[n_, k_] := T[n, k] = If[Union @ {n, k} == {1}, 1, If[Mod[k, 2] == 1, T[n - 1, (k + 1)/2], 2^(n - 1) + 1 - T[n - 1, k/2]]];
Table[T[n, k], {n, 1, 7} , {k, 1, 2^(n - 1)}] // Flatten (* Jean-François Alcover, May 31 2018, after Alois P. Heinz *)
CROSSREFS
Cf. A049773. From row 4 onwards same as finite sequence A131271.
Cf. A005578 (last elements in rows), A155944 (T(n,2^(n-2)) for n>1).
Cf. A006519.
Sequence in context: A123755 A118291 A118290 * A341392 A351886 A323901
KEYWORD
nonn,tabf
AUTHOR
Colin Hall, Feb 28 2012
STATUS
approved