tailieunhanh - Báo cáo toán học: "Tournament Sequences and Meeussen Sequences"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: Tournament Sequences and Meeussen Sequences. | Tournament Sequences and Meeussen Sequences Matthew Cook Computational and Neural Systems Program California Institute of Technology Pasadena CA 91125 cook@ Michael Kleber Department of Mathematics Massachusetts Institute of Technology Cambridge MA 02139 kleber@ Submitted March 22 2000 Accepted September 5 2000 Abstract A tournament sequence is an increasing sequence of positive integers ti t2 . such that ti 1 and ti i 2ti. A Meeussen sequence is an increasing sequence of positive integers m1 m2 . such that m1 1 every nonnegative integer is the sum of a subset of the m and each integer mi 1 is the sum of a unique such subset. We show that these two properties are isomorphic. That is we present a bijection between tournament and Meeussen sequences which respects the natural tree structure on each set. We also present an efficient technique for counting the number of tournament sequences of length n and discuss the asymptotic growth of this number. The counting technique we introduce is suitable for application to other well-behaved counting problems of the same sort where a closed form or generating function cannot be found. MSC 11B99 Primary 05A15 05A16 Secondary . Partially supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship 1 THE ELECTRONIC .JOURNAL OF COMBINATORICS 7 2000 R44 2 1 Introduction An infinite tournament sequence T is an infinite sequence of positive integers T t1 t2 . such that t1 1 and tj ti 1 2ti for i 1 2 . For example the first infinite tournament sequence in lexicographic order is ti i and the last is ti 2i-1. A finite tournament sequence T t1 . tn is a truncated infinite tournament sequence. An infinite Meeussen sequence M is an infinite sequence of positive integers M m1 m2 . such that m1 1 and mi mi 1 for i 1 2 . Every nonnegative integer is the sum of a subset of the mi and Each integer mi 1 is the sum of a unique subset of the mJ. For example the first infinite Meeussen sequence in .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN