We study the coefficients of algebraic functions ∑n≥0fnzn. First, we recall the too-little-known fact that these coefficients fn always admit a closed form. Then we study their asymptotics, known to be of the type fn ~ CAnnα. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the critical exponents α cannot be 1/3 or −5/2; they in fact belong to a proper subset of the dyadic numbers. We initiate the study of the set of possible values for A. We extend what Philippe Flajolet called the Drmota–Lalley–Woods theorem (which states that α=−3/2 when the dependency graph associated to the algebraic system defining the function is strongly connected). We fully characterize the possible singular behaviours in the non-strongly connected case. As a corollary, the generating functions of certain lattice paths and planar maps are not determined by a context-free grammar (i.e., their generating functions are not ℕ-algebraic). We give examples of Gaussian limit laws (beyond the case of the Drmota–Lalley–Woods theorem), and examples of non-Gaussian limit laws. We then extend our work to systems involving non-polynomial entire functions (non-strongly connected systems, fixed points of entire functions with positive coefficients). We give several closure properties for ℕ-algebraic functions. We end by discussing a few extensions of our results (infinite systems of equations, algorithmic aspects).

The depth of a trie has been deeply studied when the source which produces the words is a simple source (a memoryless source or a Markov chain). When a source is simple but not an unbiased memoryless source, the expectation and the variance are both of logarithmic order and their dominant terms involve characteristic objects of the source, for instance the entropy. Moreover, there is an asymptotic Gaussian law, even though the speed of convergence towards the Gaussian law has not yet been precisely estimated. The present paper describes a ‘natural’ class of general sources, which does not contain any simple source, where the depth of a random trie, built on a set of words independently drawn from the source, has the same type of probabilistic behaviour as for simple sources: the expectation and the variance are both of logarithmic order and there is an asymptotic Gaussian law. There are precise asymptotic expansions for the expectation and the variance, and the speed of convergence toward the Gaussian law is optimal. The paper first provides analytical conditions on the Dirichlet series of probabilities of a general source under which this Gaussian law can be derived: a pole-free region where the series is of polynomial growth. In a second step, the paper focuses on sources associated with dynamical systems, called dynamical sources, where the Dirichlet series of probabilities is expressed with the transfer operator of the dynamical system. Then, the paper extends results due to Dolgopyat, already generalized by Baladi and Vallée, and shows that the previous analytical conditions are fulfilled for ‘most’ dynamical sources, provided that they ‘strongly differ’ from simple sources. Finally, the present paper describes a class of sources not containing any simple source, where the trie depth has the same type of probabilistic behaviour as for simple sources, even with more precise estimates.

We describe a general framework for realistic analysis of sorting algorithms, and we apply it to the average-case analysis of three basic sorting algorithms (QuickSort, InsertionSort, BubbleSort). Usually the analysis deals with the mean number of key comparisons, but here we view keys as words produced by the same source, which are compared via their symbols in lexicographic order. The ‘realistic’ cost of the algorithm is now the total number of symbol comparisons performed by the algorithm, and, in this context, the average-case analysis aims to provide estimates for the mean number of symbol comparisons used by the algorithm. For sorting algorithms, and with respect to key comparisons, the average-case complexity of QuickSort is asymptotic to 2n log n, InsertionSort to n2/4 and BubbleSort to n2/2. With respect to symbol comparisons, we prove that their average-case complexity becomes Θ (n log2n), Θ(n2), Θ (n2 log n). In these three cases, we describe the dominant constants which exhibit the probabilistic behaviour of the source (namely entropy and coincidence) with respect to the algorithm.

We show that the diameter diam(Gn) of a random labelled connected planar graph with n vertices is equal to n1/4+o(1), in probability. More precisely, there exists a constant c > 0 such that

$$ P(\D(G_n)\in(n^{1/4-\e},n^{1/4+\e}))\geq 1-\exp(-n^{c\e}) $$

We establish a relation between two uniform models of random k-graphs (for constant k ⩾ 3) on n labelled vertices: ℍ(k)(n,m), the random k-graph with exactly m edges, and ℍ(k)(n,d), the random d-regular k-graph. By extending the switching technique of McKay and Wormald to k-graphs, we show that, for some range of d = d(n) and a constant c > 0, if m ~ cnd, then one can couple ℍ(k)(n,m) and ℍ(k)(n,d) so that the latter contains the former with probability tending to one as n → ∞. In view of known results on the existence of a loose Hamilton cycle in ℍ(k)(n,m), we conclude that ℍ(k)(n,d) contains a loose Hamilton cycle when d ≫ log n (or just d ⩾ C log n, if k = 3) and d = o(n1/2).

We analyse the first-order asymptotic growth of

\[ a_{n}=\int_{0}^{1}\prod_{j=1}^{n}4\sin^{2}(\pi jx)\, dx. \]

Compound Poisson population models are particular conditional branching process models. A formula for the transition probabilities of the backward process for general compound Poisson models is verified. Symmetric compound Poisson models are defined in terms of a parameter θ ∈ (0, ∞) and a power series φ with positive radius r of convergence. It is shown that the asymptotic behaviour of symmetric compound Poisson models is mainly determined by the characteristic value θrφ′(r−). If θrφ′(r−)≥1, then the model is in the domain of attraction of the Kingman coalescent. If θrφ′(r−) < 1, then under mild regularity conditions a condensation phenomenon occurs which forces the model to be in the domain of attraction of a discrete-time Dirac coalescent. The proofs are partly based on the analytic saddle point method. They draw heavily from local limit theorems and from results of S. Janson on simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Several examples of compound Poisson models are provided and analysed.

A two-row array of integers

\[ \alpha_{n}= \begin{pmatrix}a_1 & a_2 & \cdots & a_n\\ b_1 & b_2 & \cdots & b_n \end{pmatrix} \]

${\cal D}$

${\cal D} = ({\cal D}_{n})_{n\in\NN}$

A univariate polynomial f over a field is decomposable if it is the composition f = g ○ h of two polynomials g and h whose degree is at least 2. We determine an approximation to the number of decomposables over a finite field. The tame case, where the field characteristic p does not divide the degree n of f, is reasonably well understood, and we obtain exponentially decreasing relative error bounds. The wild case, where p divides n, is more challenging and our error bounds are weaker.

We call a tree parameter additive if it can be determined recursively as the sum of the parameter values of all branches, plus a certain toll function. In this paper, we prove central limit theorems for very general toll functions, provided that they are bounded and small on average. Simply generated families of trees are considered as well as Pólya trees, recursive trees and binary search trees, and the results are illustrated by several examples of parameters for which we prove normal or log-normal limit laws.

We generalize and improve recent results by Bóna and Knopfmacher and by Banderier and Hitcz-enko concerning the joint distribution of the sum and number of parts in tuples of restricted compositions. Specifically, we generalize the problem to general combinatorial classes and relax the requirement that the sizes of the compositions be equal. We extend the main explicit results to enumeration problems whose counting sequences are Riordan arrays. In this framework, we give an alternative method for computing asymptotics in the supercritical case, which avoids explicit diagonal extraction.

The authors would like to rectify a mistake made in Theorem 1.1 of their article (Behrisch, Cojaa-Oghlan & Kang 2014), published in issue 23 (3). The text below explains the changes required.