Tournament Sequences and Meeussen Sequences

  • Matthew Cook
  • Michael Kleber

Abstract

A tournament sequence is an increasing sequence of positive integers $(t_1,t_2,\ldots)$ such that $t_1=1$ and $t_{i+1} \leq 2t_i$. A Meeussen sequence is an increasing sequence of positive integers $(m_1,m_2,\ldots)$ such that $m_1=1$, every nonnegative integer is the sum of a subset of the $\{m_i\}$, and each integer $m_i-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.

Published
2000-09-05
Article Number
R44