

A049773


Triangular array T read by rows: if row n is r(1),...,r(m), then row n+1 is 2r(1)1,...,2r(m)1,2r(1),...,2r(m).


10



1, 1, 2, 1, 3, 2, 4, 1, 5, 3, 7, 2, 6, 4, 8, 1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16, 1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, 6, 22, 14, 30, 4, 20, 12, 28, 8, 24, 16, 32, 1, 33, 17, 49, 9, 41, 25, 57, 5, 37, 21, 53, 13, 45, 29, 61, 3, 35, 19
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


COMMENTS

nth row = (r(1),r(2),...,r(m)), where m=2^(n1), satisfies r(r(k))=k for k=1,2,...,m and has exactly 2^[ n/2 ] solutions of r(k)=k. (The function r(k) reverses bits. Or rather, r(k)=revbits(k1)+1.
In a knockout competition with m players, arranging the competition brackets (see links) in r(k) order, where 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 pth from last round of the competition. At the same time the top ranked players in each match meet the highest ranked player possible consistent with this rule. The sequence for the top ranked players meeting the lowest ranked player possible is A208569. See also A131271.  Colin Hall, Jul 31 2011, Feb 29 2012
Row n contains one of A003407(2^(n1)) nonaveraging permutations of [2^(n1)], i.e., a permutation of [2^(n1)] without 3term arithmetic progressions.  Alois P. Heinz, Dec 05 2017


LINKS

Alois P. Heinz, Rows n = 1..13, flattened
Eric Weisstein's World of Mathematics, Nonaveraging Sequence
Wikipedia, Arithmetic progression
Wikipedia, Bracket (tournament)
Index entries related to nonaveraging sequences


EXAMPLE

Triangle begins:
1;
1, 2;
1, 3, 2, 4;
1, 5, 3, 7, 2, 6, 4, 8;
1, 9, 5, 13, 3, 11, 7, 15, 2, 10, 6, 14, 4, 12, 8, 16;
1, 17, 9, 25, 5, 21, 13, 29, 3, 19, 11, 27, 7, 23, 15, 31, 2, 18, 10, 26, ...


MAPLE

T:= proc(n) option remember; `if`(n=1, 1,
[map(x>2*x1, [T(n1)])[], map(x>2*x, [T(n1)])[]][])
end:
seq(T(n), n=1..7); # Alois P. Heinz, Oct 28 2011


MATHEMATICA

row[1] = {1}; row[n_] := row[n] = Join[ 2*row[n1]  1, 2*row[n1] ]; Flatten[ Table[ row[n], {n, 1, 7}]] (* JeanFrançois Alcover, May 03 2012 *)


PROG

(PARI) (a(n, k) = if( k<=0  k>=n, 0, if( k%2, n\2) + a(n\2, k\2))); {T(n, k) = if( k<=0  k>2^n/2, 0, 1 + a(2^n/2, k1))}; /* Michael Somos, Oct 13 1999 */
(Haskell)
a049773 n k = a049773_tabf !! (n1) !! (k1)
a049773_row n = a049773_tabf !! (n1)
a049773_tabf = iterate f [1] where
f vs = (map (subtract 1) ws) ++ ws where ws = map (* 2) vs
 Reinhard Zumkeller, Mar 14 2015


CROSSREFS

Sum of oddindexed terms of nth row gives A007582. Sum of evenindexed terms gives A049775.
A030109 is another version.
Cf. A131271.
Cf. A088370.  Alois P. Heinz, Oct 28 2011
Cf. A208569.  Colin Hall, Feb 29 2012
Cf. A003407, A088208.
Sequence in context: A003602 A265650 A181733 * A261401 A217669 A123021
Adjacent sequences: A049770 A049771 A049772 * A049774 A049775 A049776


KEYWORD

nonn,tabf,nice,look


AUTHOR

Clark Kimberling


STATUS

approved



