The asymptotic number of solutions of a diophantine equation from coding theory (Q1215657): Difference between revisions

Let \(a(n)\) denote the number of solutions of the equation \(2^{-x_1}+\ldots+2^{-x_n} =1\), where the \(x_i\) are integers satisfying \(0\leq x_1\leq\ldots\leq x_n\). This equation occurs in the theory of uniquely decipherable codes (see \textit{B. McMillan}, IRE Trans. Inf. Theory 2, No. 4, 115--116 (1965; Zbl 0137.13503)]). By relating this to a problem of enumerating the labels on certain infinite trees, we are able to show that the generating function for \(\{a(n)\}\) is meromorphic in the unit disk and hence that \(a(n) = \alpha\lambda^n + O(\mu^n)\), where \(\alpha,\lambda\) are positive constants and \(0\leq \mu<\lambda\). The first few terms of the continued fraction expansion of the generating function can be calculated and this gives the following estimates: \[ 1.794147176 < \lambda <1.794147186,\quad a=0.14185325\pm 6\times 10^{-3}, \] and the error term is smaller than \(578(1.55)^n\).