CaltechAUTHORS
  A Caltech Library Service

Tournament Sequences and Meeussen Sequences

Cook, Matthew and Kleber, Michael (2000) Tournament Sequences and Meeussen Sequences. Electronic Journal of Combinatorics, 7 (1). R44. ISSN 1077-8926. http://resolver.caltech.edu/CaltechAUTHORS:COOejc00

[img]
Preview
PDF
See Usage Policy.

179Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:COOejc00

Abstract

A tournament sequence is an increasing sequence of positive integers (t1; t2; : : :) such that t1 = 1 and ti+1 <= 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 {mi}, 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.


Item Type:Article
Additional Information:Submitted: March 22, 2000; Accepted: September 5, 2000 Partially supported by an NSF Mathematical Sciences Postdoctoral Research Fellowship. The authors would like to acknowledge W. Meeussen for suggesting the question, and N. J. A. Sloane for his Encyclopedia of Integer Sequences [9], which led us to notice the coincidence. Thanks also to J. Polito for useful conversations, J. Shallit for helpful comments on an earlier draft of this work, and D. Knuth for excellent suggestions about the asymptotics questions.
Record Number:CaltechAUTHORS:COOejc00
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:COOejc00
Alternative URL:http://www.combinatorics.org/Volume_7/Abstracts/v7i1r44.html
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:768
Collection:CaltechAUTHORS
Deposited By: Archive Administrator
Deposited On:29 Sep 2005
Last Modified:26 Dec 2012 08:41

Repository Staff Only: item control page