TAILIEUCHUNG - 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
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.