Non-negative Lukasiewicz paths are special two-dimensional lattice paths never passing below their starting altitude which have only one single special type of down step. They are well-known and -studied combinatorial objects, in particular due to their bijective relation to trees with given node degrees. We study the asymptotic behavior of the number of ascents (i.e., the number of maximal sequences of consecutive up steps) of given length for classical subfamilies of general non-negative Lukasiewicz paths: those with arbitrary ending altitude, those ending on their starting altitude, and a variation thereof. Our results include precise asymptotic expansions for the expected number of such ascents as well as for the corresponding variance.

The summatory function of a $q$-regular sequence in the sense of Allouche and Shallit is analysed asymptotically. The result is a sum of periodic fluctuations for eigenvalues of absolute value larger than the joint spectral radius of the matrices of a linear representation of the sequence. The Fourier coefficients of the fluctuations are expressed in terms of residues of the corresponding Dirichlet generating function. A known pseudo Tauberian argument is extended in order to overcome convergence problems in Mellin--Perron summation. Two examples are discussed in more detail: The case of sequences defined as the sum of outputs written by a transducer when reading a $q$ary expansion of the input and the number of odd entries in the rows of Pascal's rhombus.

The register function (or Horton–Strahler number) of a binary tree is a well-known combinatorial parameter. We study a reduction procedure for binary trees which offers a new interpretation for the register function as the maximal number of reductions that can be applied to a given tree. In particular, the precise asymptotic behavior of the number of certain substructures (“branches”) that occur when reducing a tree repeatedly is determined. In the same manner we introduce a reduction for simple two-dimensional lattice paths from which a complexity measure similar to the register function can be derived. We analyze this quantity, as well as the (cumulative) size of an (iteratively) reduced lattice path asymptotically.

The number of “nonequivalent” compact Huffman codes of lengthrover an alphabet of sizethas been studied frequently. Equivalently, the number of “nonequivalent” completet-ary trees has been examined. We first survey the literature, unifying several independent approaches to the problem. Then, improving on earlier work, we prove a very precise asymptotic result on the counting function, consisting of two main terms and an error term.

Stanley and Callan considered Dyck paths where the lengths of the run to the origin is always odd resp. the last one even, and the other ones odd. These subclasses are also enumerated by (shifted) Catalan numbers. We study the (average) height of the

Range Quickselect, a simple modification of the well-known Quickselect algorithm for selection, can be used to efficiently find an element with rank k in a given range [i..j], out of n given elements. We study basic cost measures of Range Quickselect by computing exact and asymptotic results for the expected number of passes, comparisons and data moves during the execution of this algorithm.The key element appearing in the analysis of Range Quickselect is a trivariate recurrence that we solve in full generality. The general solution of the recurrence proves to be very useful, as it allows us to tackle several related problems, besides the analysis that originally motivated us.In particular, we have been able to carry out a precise analysis of the expected number of moves of the pth element when selecting the jth smallest element with standard Quickselect, where we are able to give both exact and asymptotic results.Moreover, we can apply our general results to obtain exact and asymptotic results for several parameters in binary search trees, namely the expected number of common ancestors of the nodes with rank i and j, the expected size of the subtree rooted at the least common ancestor of the nodes with rank i and j, and the expected distance between the nodes of ranks i and j.

For the register function for t -ary trees, recently introduced by Auber et al., we prove that the average is log 4 n + O (1), if all such trees with n internal nodes are considered to be equally likely.This result remains true for rooted trees where the set of possible out-degrees is finite. Furthermore we obtain exponential tail estimates for the distribution of the register function. Thus, the distribution is highly concentrated around the mean value.

Several cryptosystems rely on fast calculations of linear combinations in groups. One way to achieve this is to use joint signed binary digit expansions of small “weight.” We study two algorithms, one based on nonadjacent forms of the coefficients of the linear combination, the other based on a certain joint sparse form specifically adapted to this problem. Both methods are sped up using the sliding windows approach combined with precomputed lookup tables. We give explicit and asymptotic results for the number of group operations needed, assuming uniform distribution of the coefficients. Expected values, variances and a central limit theorem are proved using generating functions.Furthermore, we provide a new algorithm that calculates the digits of an optimal expansion of pairs of integers from left to right. This avoids storing the whole expansion, which is needed with the previously known right-to-left methods, and allows an online computation.

We consider the search problem in which one finds a binary word among m words chosen randomly from the set of all words of fixed length n. It is well known that the optimal search is equivalent to the Huffman coding that requires on average log/sub 2/ m bits to be checked plus a small additional cost called the average redundancy. The latter is an oscillating function of m and is bounded between zero and 1-(1+lnln2)/In2/spl ap/0.0860713320. As a matter of fact, it is known that finding the optimal strategy for this problem is NP-hard. We propose here several simple randomized search strategies leading, respectively, to the following average redundancies: 1.332746177, 0.6113986565,0.4310617764, and 0.332746177, plus some small oscillations that we precisely characterize. These results should be compared to the optimal, but NP-hard, search algorithm. Our findings extend and make more precise results of Fedotov and Ryabko (2001).

Cauchy coefficient integrals and Hankel contours provide a natural generalization of Stirling numbers for unrestricted complex values of their arguments. Many classical identities survive such an extension.

For the analysis of an algorithm to generate binary trees, the behaviour of a certain sequence of numbers is essential. In the original paper, it was expressed by a recursion. Here, we show how to solve this (and similar) recursions, both explicitly and asymptotically. Some additional information about useful mathematical software is also provided.

This paper studies the asymptotics of the variance for the internal path length in a symmetric digital search tree under the Bernoulli model. This problem has been open until now. It is proved that the variance is asymptotically equal to $N \cdot 0.26600 + N \cdot \delta (\log _2 N)$, where N is the number of stored records and $\delta (x)$ is a periodic function of mean zero and a very small amplitude. This result completes a series of studies devoted to the asymptotic analysis of the variances of digital tree parameters in the symmetric case. In order to prove the previous result a number of nontrivial problems concerning analytic continuations and some others of a numerical nature had to be solved. In fact, some of these techniques are motivated by the methodology introduced in an influential paper by Flajolet and Sedgewick.

Knuth posed it as an open problem to compute the average number of external internal nodes in a random digital search tree. This was settled by Flajolet and Sedgewick using Rice’s method. This note offers an alternative approach using Mellin transforms.

Abstract It is proved that the dth highest leaf, where all planted plane trees with n nodes are assumed to be equally likely, has an average height \documentclass{article}\pagestyle{empty}\begin{document}$ \sqrt {\pi n} ‐ \frac{1}{2} ‐ \frac{2}{3}\sum\nolimits_{s = 1}^{d ‐ 1} {\left({2/9} \right)^s \left({\begin{array}{*{20}c} {2s + 1} \\ s \\ \end{array}} \right)} + O\left({n^{‐ 1/2 + \varepsilon}} \right) $\end{document} for all ϵ > 0 and n → ∞. This solves a problem left open in one of our previous papers.

We study the number of registers required for evaluating arithmetic expressions formed with any set of unary and binary operators. Our approach consists in a singularity analysis of intervening generating functions combined with a use of (complex) Mellin inversion. We illustrate it first by rederiving the known results about binary trees and then extend it to the fully general case of unary–binary trees. The method used, as mentioned in the conclusion, is applicable to a wide class of combinatorial sums.