Search

A digital search tree (DST) is a fundamental data structure on words that finds various applications from the popular Lempel–Zivʼ78 data compression scheme to distributed hash tables. The profile of a DST measures the number of nodes at the same distance from the root; it depends on the number of stored strings and the distance from the root. Most parameters of DST (e.g., depth, height, fillup) can be expressed in terms of the profile. We study here asymptotics of the average profile in a DST built from sequences generated independently by a memoryless source. After representing the average profile by a recurrence, we solve it using a wide range of analytic tools. This analysis is surprisingly demanding but once it is carried out it reveals an unusually intriguing and interesting behavior. The average profile undergoes phase transitions when moving from the root to the longest path: at first it resembles a full tree until it abruptly starts growing polynomially and oscillating in this range. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, poissonization and depoissonization, the saddle point method, singularity analysis and uniform asymptotic analysis.

It is common to represent a sequence a=(a0, a1, …) of complex numbers with a generating function. G.C. Rota once remarked that among all the possible generating functions that might be used to represent a, the ordinary and exponential generating functions are the most ubiquitous. It is unclear what, if anything, makes these two particular representations special. We show here that the ordinary and exponential representations uniquely possess the property that the determinants of the Hankel matrices of certain convolutional polynomials in a are independent of a1. Hankel matrices are closely associated with the problem of moments and the problem of moment preserving maps and hence the independence of a1 has some curious implications. For example determining if a is a sequence of cumulants for some distribution is necessarily independent of the value for the mean a1. We explore this and other applications of the generating function characterization property within probability and combinatorics.

This paper develops a unified enumerative and asymptotic theory of directed two-dimensional lattice paths in half-planes and quarter-planes. The lattice paths are specified by a finite set of rules that are both time and space homogeneous, and have a privileged direction of increase. (They are then essentially one-dimensional objects.) The theory relies on a specific “kernel method” that provides an important decomposition of the algebraic generating functions involved, as well as on a generic study of singularities of an associated algebraic curve. Consequences are precise computable estimates for the number of lattice paths of a given length under various constraints (bridges, excursions, meanders) as well as a characterization of the limit laws associated to several basic parameters of paths.

International audience; A non-empty word w is a Lyndon word if and only if it is strictly smaller for the lexicographical order than any of its proper suffixes. Such a word w is either a letter or admits a standard factorization uv where v is its smallest proper suffix. For any Lyndon word v, we show that the set of Lyndon words having v as right factor of the standard factorization is regular and compute explicitly the associated generating function. Next, considering the Lyndon words of length n over a twoletter alphabet, we establish that, for the uniform distribution, the average length of the right factor v of the standard factorization is asymptotically 3n/4.

New enumerating functions for the Euler numbers are considered. Several of the relevant generating functions appear in connection to entries in Ramanujan's Lost Notebook. The results presented here are, in part, a response to a conjecture made by M.E.H. Ismail and C. Zhang about the symmetry of polynomials in Ramanujan's expansion for a generalization of the Rogers–Ramanujan series. Related generating functions appear in the work of H. Prodinger and L.L. Cristea in their study of geometrically distributed random variables. An elementary combinatorial interpretation for each of these enumerating functions is given in terms of a related set of statistics.

We prove that for each $k\ge0$, the probability that a root vertex in a random planar graph has degree $k$ tends to a computable constant $d_k$, so that the expected number of vertices of degree $k$ is asymptotically $d_k n$, and moreover that $\sum_k d_k =1$. The proof uses the tools developed by Gimenez and Noy in their solution to the problem of the asymptotic enumeration of planar graphs, and is based on a detailed analysis of the generating functions involved in counting planar graphs. However, in order to keep track of the degree of the root, new technical difficulties arise. We obtain explicit, although quite involved expressions, for the coefficients in the singular expansions of the generating functions of interest, which allow us to use transfer theorems in order to get an explicit expression for the probability generating function $p(w)=\sum_k d_k w^k$. From this we can compute the $d_k$ to any degree of accuracy, and derive the asymptotic estimate $d_k \sim c\cdot k^{-1/2} q^k$ for large values of $k$, where $q \approx 0.67$ is a constant defined analytically.

We present a complete analysis of the statistics of number of occurrences of a regular expression pattern in a random text. This covers “motifs” widely used in computational biology. Our approach is based on: (i) classical constructive results in automata and formal language theory; (ii) analytic combinatorics that is used for deriving asymptotic properties from generating functions; (iii) computer algebra in order to determine generating functions explicitly, analyse generating functions and extract coefficients efficiently. We provide constructions for overlapping or non-overlapping matches of a regular expression. A companion implementation produces: multivariate generating functions for the statistics under study; a fast computation of their Taylor coefficients which yields exact values of the moments with typical application to random texts of size 30,000; precise asymptotic formulæthat allow predictions in texts of arbitrarily large sizes. Our implementation was tested by comparing predictions of the number of occurrences of motifs against the 7 megabytes amino acid database PRODOM. We handled more than 88% of the standard collection of PROSITE motifs with our programs. Such comparisons help detect which motifs are observed in real biological data more or less frequently than theoretically predicted.

The goal of this thesis is to establish enumerative results on several classes of paths and animals. These results are applications of the theory of heaps of pieces developed by Viennot. We study discrete excursions (or generalized Dyck paths) with bounded height; we obtain combinatorial interpretations and extensions of results from Banderier, Flajolet and Bousquet-Mélou. We describe and enumerate several subclasses of self-avoiding walks (SAW), called weakly directed walks. These classes are larger than the class of prudent walks, which is the largest natural subclass of SAW enumerated so far. We compute the average site perimeter of directed animals, proving conjectures from Conway and Le Borgne. Finally, we obtain new results on the enumeration of Klarner animals and multi-directed animals defined by Bousquet-Mélou and Rechnitzer., Le but de cette thèse est d'établir des résultats énumératifs sur certaines classes de chemins et d'animaux. Ces résultats sont obtenus en appliquant la théorie des empilements de pièces développée par Viennot. Nous étudions les excursions discrètes (ou chemins de Dyck généralisés) de hauteur bornée; nous obtenons des interprétations combinatoires et des extensions de résultats de Banderier, Flajolet et Bousquet-Mélou. Nous décrivons et énumérons plusieurs classes de chemins auto-évitants, dits chemins faiblement dirigés. Ces chemins sont plus nombreux que les chemins prudents qui forment la classe naturelle la plus grande jusqu'alors. Nous calculons le périmètre de site moyen des animaux dirigés, prouvant des conjectures de Conway et Le Borgne. Enfin, nous obtenons des résultats nouveaux sur l'énumération des animaux de Klarner et les animaux multi-dirigés de Bousquet-Mélou et Rechnitzer.

Consider a family T of 3-connected graphs, and let G be the class of graphs whose 3-connected components are graphs in T . We present a general framework for analyzing such graphs classes based on singularity analysis of generating functions. This generalizes previously studied cases such as planar graphs and seriesparallel graphs. We provide a general theorem for the asymptotic number of graphs in G, based on the singularities of the exponential generating function associated to T . We derive limit laws for the number of connected components, for the number of edges and for the number of 2-connected components. At last, for some classes under study we show the existence of critical phenomena as the edge density in the class varies.

In queuing theory, it is usual to have some models with a "reset" of the queue. In terms of lattice paths, it is like having the possibility of jumping from any altitude to zero. These objects have the interesting feature that they do not have the same intuitive probabilistic behaviour as classical Dyck paths (the typical properties of which are strongly related to Brownian motion theory), and this article quantifies some relations between these two types of paths. We give a bijection with some other lattice paths and a link with a continued fraction expansion. Furthermore, we prove several formulae for related combinatorial structures conjectured in the On-Line Encyclopedia of Integer Sequences. Thanks to the kernel method and via analytic combinatorics, we provide the enumeration and limit laws of these "lattice paths with catastrophes" for any finite set of jumps. We end with an algorithm to generate such lattice paths uniformly at random., Comment: 32 pages

This paper considers logical formulas built on the single binary connector of implication and a finite number of variables. When the number of variables becomes large, we prove the following quantitative results: asymptotically, all classical tautologies are simple tautologies. It follows that asymptotically, all classical tautologies are intuitionistic.

We analyze some enumerative and asymptotic properties of Dyck paths under a line of slope 2/5.This answers to Knuth's problem \\#4 from his "Flajolet lecture" during the conference "Analysis of Algorithms" (AofA'2014) in Paris in June 2014.Our approach relies on the work of Banderier and Flajolet for asymptotics and enumeration of directed lattice paths. A key ingredient in the proof is the generalization of an old trick of Knuth himself (for enumerating permutations sortable by a stack),promoted by Flajolet and others as the "kernel method". All the corresponding generating functions are algebraic,and they offer some new combinatorial identities, which can be also tackled in the A=B spirit of Wilf--Zeilberger--Petkov{\v s}ek.We show how to obtain similar results for other slopes than 2/5, an interesting case being e.g. Dyck paths below the slope 2/3, which corresponds to the so called Duchon's club model., Comment: Robert Sedgewick and Mark Daniel Ward. Analytic Algorithmics and Combinatorics (ANALCO)2015, Jan 2015, San Diego, United States. SIAM, 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO), eISBN 978-1-61197-376-1, pp.105-113, 2015, 2015 Proceedings of the Twelfth Workshop on Analytic Algorithmics and Combinatorics (ANALCO)

International audience; The \emph{Coppersmith methods} is a family of lattice-based techniques to find small integer roots of polynomial equations. They have found numerous applications in cryptanalysis and, in recent developments, we have seen applications where the number of unknowns and the number of equations are non-constant. In these cases, the combinatorial analysis required to settle the complexity and the success condition of the method becomes very intricate.We provide a toolbox based on \emph{analytic combinatorics} for these studies. It uses the structure of the considered polynomials to derive their generating functions and applies complex analysis techniques to get asymptotics. The toolbox is versatile and can be used for many different applications, including multivariate polynomial systems with arbitrarily many unknowns (of possibly different sizes) and simultaneous modular equations over different moduli. To demonstrate the power of this approach, we apply it to recent cryptanalytic results on number-theoretic pseudorandom generators for which we easily derive precise and formal analysis. We also present new theoretical applications to two problems on RSA key generation and randomness generation used in padding functions for encryption.

We investigate pattern avoidance in permutations satisfying some additional restrictions. These are naturally considered in terms of avoiding patterns in linear extensions of certain forest-like partially ordered sets, which we call binary shrub forests. In this context, we enumerate forests avoiding patterns of length three. In four of the five non-equivalent cases, we present explicit enumerations by exhibiting bijections with certain lattice paths bounded above by the line $y=\ell x$, for some $\ell\in\mathbb{Q}^+$, one of these being the celebrated Duchon's club paths with $\ell=2/3$. In the remaining case, we use the machinery of analytic combinatorics to determine the minimal polynomial of its generating function, and deduce its growth rate.

Until now, the enumeration of connected graphs has been dealt with by probabilistic methods, by special combinatorial decompositions or by somewhat indirect formal series manipulations. We show here that it is possible to make analytic sense of the divergent series that expresses the generating function of connected graphs. As a consequence, it becomes possible to derive analytically known enumeration results using only first principles of combinatorial analysis and straight asymptotic analysis—specifically, the saddle-point method. In this perspective, the enumeration of connected graphs by excess (of number of edges over number of vertices) derives from a simple saddle-point analysis. Furthermore, a refined analysis based on coalescent saddle points yields complete asymptotic expansions for the number of graphs of fixed excess, through an explicit connection with Airy functions.