Tournament sequences and Meeussen sequences

Publication date 30 November 2000

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0002220, https://eudml.org/doc/121369, http://www.emis.de/journals/EJC/Volume_7/Abstracts/v7i1r44.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

asymptotic growth counting increasing sequence of positive integers Meussen sequence rooted tree tournament sequences

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Special sequences and polynomials (11B83)

Abstract: A "tournament sequence" is an increasing sequence of positive integers (t_1,t_2,...) such that t_1=1 and t_{i+1} <= 2 t_i. A "Meeussen sequence" is an increasing sequence of positive integers (m_1,m_2,...) 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.

Review text

A tournament sequence [see \textit{P. Capell} and \textit{T. V. Narayana}, Can. Math. Bull. 13, 105-109 (1970; Zbl 0225.60006)] is an increasing sequence of positive integers \((t_1, t_2,\dots)\) such that \(t_1+1\) and \(t_{i+1}\leq 2t_i\). The authors define a Meeussen sequence to be an increasing sequence of positive integers \((m_1, m_2,\dots)\) such that \(m_1=1\), every non-negative 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. They then show that Meeussen sequences are precisely the tournament sequences, by exhibiting a bijection between the two sets of sequences which respects the natural tree structure on each set. They also present an efficient way of counting these sequences, and discuss the asymptotic growth of the number of sequences.

Recommendations

Cited in

(4)

This page was built for publication: Tournament sequences and Meeussen sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1583614)