On the number of ordered factorizations of natural numbers (Q1972137)

In this paper the authors investigate the function \(H(n)\), defined to be the number of representations of the positive integer \(n\) as an ordered product of factors exceeding 1. They explain how this function arises in molecular biology in the analysis of the probed partial digest problem. In [Acta Arith. 2, 134-144 (1936; Zbl 0015.10002)], \textit{E. Hille} established a recursive rule for \(H(n)\) and showed that \(H(n)=O (n^\rho)\) where \(\rho\) is given by \(\zeta(\rho)=2\) and that, for any \(\varepsilon>0\), \(\lim\sup_{n\to \infty} {H(n)\over n^{\rho- \varepsilon}}= +\infty\) holds. More generally, Hille showed that if \(P\) denotes the set of all positive integers with prime factors restricted to some set \(B\) of primes and \(t=\rho(P)\) is defined by \(\prod_{p\in B}(1-p^{-1})^{-1}=2\), so \(t>1\), then \(H(n)=O (n^{\rho(P)})\) for \(n\in P\). The authors improve these results by showing that \(H(n)<n^{\rho(P)}\) for \(n\in P\). As the authors point out, previously no explicit sequences of integers \(n\) with \(H(n) \geq n^{t(n)}\), where \(\lim_{n\to\infty} t(n)>1\), were known. They were able to remedy this by finding, for \(B\) consisting of the first 2, 3, or 4 primes, explicit sequences \((n_i)\) in the corresponding set \(P\) such that \(H(n_i) \geq n^{t_i}_i\) where \(t_i\to \rho(P)\) as \(i\to\infty\).