Tournament sequences and Meeussen sequences

Matthew Cook ; Michael Kleber

The electronic journal of combinatorics, Tome 7 (2000)

Résumé

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.

Détail

DOI : 10.37236/1522

Classification : 11B83, 05A15, 05A16
Mots-clés : rooted tree, Meussen sequence, increasing sequence of positive integers, tournament sequences, counting, asymptotic growth