DMTCS Proceedings vol. AG, Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities

---

1. Density of truth in modal logics

Zofia Kostrzycka.

The aim of this paper is counting the probability that a random modal formula is a tautology. We examine $\{ \to,\Box \}$ fragment of two modal logics $\mathbf{S5}$ and $\mathbf{S4}$ over the language with one propositional variable. Any modal formula written in such a language may be interpreted as a unary binary tree. As it is known, there are finitely many different formulas written in one variable in the logic $\mathbf{S5}$ and this is the key to count the proportion of tautologies of $\mathbf{S5}$ among all formulas. Although the logic $\mathbf{S4}$ does not have this property, there exist its normal extensions having finitely many non-equivalent formulas.

---

2. Mixed Powers of Generating Functions

Manuel Lladser.

Given an integer $m \geq 1$, let $\| \cdot \|$ be a norm in $\mathbb{R}^{m+1}$ and let $\mathbb{S}_+^m$ denote the set of points $\mathbf{d}=(d_0,\ldots,d_m)$ in $\mathbb{R}^{m+1}$ with nonnegative coordinates and such that $\| \mathbf{d} \|=1$. Consider for each $1 \leq j \leq m$ a function $f_j(z)$ that is analytic in an open neighborhood of the point $z=0$ in the complex plane and with possibly negative Taylor coefficients. Given $\mathbf{n}=(n_0,\ldots,n_m)$ in $\mathbb{Z}^{m+1}$ with nonnegative coordinates, we develop a method to systematically associate a parameter-varying integral to study the asymptotic behavior of the coefficient of $z^{n_0}$ of the Taylor series of $\prod_{j=1}^m \{f_j(z)\}^{n_j}$, as $\| \mathbf{n} \| \to \infty$. The associated parameter-varying integral has a phase term with well specified properties that make the asymptotic analysis of the integral amenable to saddle-point methods: for many $\mathbf{d} \in \mathbb{S}_+^m$, these methods ensure uniform asymptotic expansions for $[z^{n_0}] \prod_{j=1}^m \{f_j(z)\}^{n_j}$ provided that $\mathbf{n}/ \| \mathbf{n} \|$ stays sufficiently close to $\mathbf{d}$ as $\| \mathbf{n} \| \to \infty$. Our method finds applications in studying the asymptotic behavior of the coefficients of a certain multivariable generating functions as well as in problems related to the Lagrange inversion formula for instance in the context random planar maps.

---

3. Statistical Properties of Similarity Score Functions

Jérémie Bourdon ; Alban Mancheron.

In computational biology, a large amount of problems, such as pattern discovery, deals with the comparison of several sequences (of nucleotides, proteins or genes for instance). Very often, algorithms that address this problem use score functions that reflect a notion of similarity between the sequences. The most efficient methods take benefit from theoretical knowledge of the classical behavior of these score functions such as their mean, their variance, and sometime their asymptotic distribution in a given probabilistic model. In this paper, we study a recent family of score functions introduced in Mancheron 2003, which allows to compare two words having the same length. Here, the similarity takes into account all matches and mismatches between two sequences and not only the longest common subsequence as in the case of classical algorithms such as BLAST or FASTA. Based on generating functions, we provide closed formulas for the mean and the variance of these functions in an independent probabilistic model. Finally, we prove that every function in this family asymptotically behaves as a Gaussian random variable.

---

4. LOGLOG counting for the estimation of IP traffic

Olivier Gandouet ; Alain Jean-Marie.

In this paper, we discuss the problem of estimating the number of "elephants'' in a stream of IP packets. First, the problem is formulated in the context of multisets. Next, we explore some of the theoretical space complexity of this problem, and it is shown that it cannot be solved with less than $\Omega (n)$ units of memory in general, $n$ being the number of different elements in the multiset. Finally, we describe an algorithm, based on Durand-Flajolet's LOGLOG algorithm coupled with a thinning of the packet stream, which returns an estimator of the number of elephants using a small amount of memory. This algorithm allows a good estimation for particular families of random multiset. The mean and variance of this estimator are computed. The algorithm is then tested on synthetic data.

---

5. Random assignment and shortest path problems

Johan Wästlund.

We explore a similarity between the $n$ by $n$ random assignment problem and the random shortest path problem on the complete graph on $n+1$ vertices. This similarity is a consequence of the proof of the Parisi formula for the assignment problem given by C. Nair, B. Prabhakar and M. Sharma in 2003. We give direct proofs of the analogs for the shortest path problem of some results established by D. Aldous in connection with his $\zeta (2)$ limit theorem for the assignment problem.

---

6. An invariance principle for random planar maps

Grégory Miermont.

We show a new invariance principle for the radius and other functionals of a class of conditioned `Boltzmann-Gibbs'-distributed random planar maps. It improves over the more restrictive case of bipartite maps that was discussed in Marckert and Miermont (2006). As in the latter paper, we make use of a bijection between planar maps and a class of labelled multitype trees, due to Bouttier et al. (2004). We also rely on an invariance principle for multitype spatial Galton-Watson trees, which is proved in a companion paper.

---

7. Some exactly solvable models of urn process theory

Philippe Flajolet ; Philippe Dumas ; Vincent Puyhaubert.

We establish a fundamental isomorphism between discrete-time balanced urn processes and certain ordinary differential systems, which are nonlinear, autonomous, and of a simple monomial form. As a consequence, all balanced urn processes with balls of two colours are proved to be analytically solvable in finite terms. The corresponding generating functions are expressed in terms of certain Abelian integrals over curves of the Fermat type (which are also hypergeometric functions), together with their inverses. A consequence is the unification of the analyses of many classical models, including those related to the coupon collector's problem, particle transfer (the Ehrenfest model), Friedman's "adverse campaign'' and Pólya's contagion model, as well as the OK Corral model (a basic case of Lanchester's theory of conflicts). In each case, it is possible to quantify very precisely the probable composition of the urn at any discrete instant. We study here in detail "semi-sacrificial'' urns, for which the following are obtained: a Gaussian limiting distribution with speed of convergence estimates as well as a characterization of the large and extreme large deviation regimes. We also work out explicitly the case of $2$-dimensional triangular models, where local limit laws of the stable type are obtained. A few models of dimension three or greater, e.g., "autistic'' (generalized Pólya), cyclic chambers (generalized […]

---

8. On the spectral dimension of random trees

Bergfinnur Durhuus ; Thordur Jonsson ; John Wheater.

We determine the spectral dimensions of a variety of ensembles of infinite trees. Common to the ensembles considered is that sample trees have a distinguished infinite spine at whose vertices branches can be attached according to some probability distribution. In particular, we consider a family of ensembles of $\textit{combs}$, whose branches are linear chains, with spectral dimensions varying continuously between $1$ and $3/2$. We also introduce a class of ensembles of infinite trees, called $\textit{generic random trees}$, which are obtained as limits of ensembles of finite trees conditioned to have fixed size $N$, as $N \to \infty$. Among these ensembles is the so-called uniform random tree. We show that generic random trees have spectral dimension $d_s=4/3$.

---

9. Computing generating functions of ordered partitions with the transfer-matrix method

Masao Ishikawa ; Anisse Kasraoui ; Jiang Zeng.

An ordered partition of $[n]:=\{1,2,\ldots, n\}$ is a sequence of disjoint and nonempty subsets, called blocks, whose union is $[n]$. The aim of this paper is to compute some generating functions of ordered partitions by the transfer-matrix method. In particular, we prove several conjectures of Steingrímsson, which assert that the generating function of some statistics of ordered partitions give rise to a natural $q$-analogue of $k!S(n,k)$, where $S(n,k)$ is the Stirling number of the second kind.

---

10. The first ascent of size $d$ or more in compositions

Charlotte Brennan ; Arnold Knopfmacher.

A composition of a positive integer $n$ is a finite sequence of positive integers $a_1, a_2, \ldots, a_k$ such that $a_1+a_2+ \cdots +a_k=n$. Let $d$ be a fixed nonnegative integer. We say that we have an ascent of size $d$ or more at position $i$, if $a_{i+1}\geq a_i+d$. We study the average position, initial height and end height of the first ascent of size $d$ or more in compositions of $n$ as $n \to \infty$.

---

11. On the non-randomness of modular arithmetic progressions: a solution to a problem by V. I. Arnold

Eda Cesaratto ; Alain Plagne ; Brigitte Vallée.

We solve a problem by V. I. Arnold dealing with "how random" modular arithmetic progressions can be. After making precise how Arnold proposes to measure the randomness of a modular sequence, we show that this measure of randomness takes a simplified form in the case of arithmetic progressions. This simplified expression is then estimated using the methodology of dynamical analysis, which operates with tools coming from dynamical systems theory. In conclusion, this study shows that modular arithmetic progressions are far from behaving like purely random sequences, according to Arnold's definition.

---

12. Multivariate generalizations of the Foata-Schützenberger equidistribution

Florent Hivert ; Jean-Christophe Novelli ; Jean-Yves Thibon.

A result of Foata and Schützenberger states that two statistics on permutations, the number of inversions and the inverse major index, have the same distribution on a descent class. We give a multivariate generalization of this property: the sorted vectors of the Lehmer code, of the inverse majcode, and of a new code (the inverse saillance code), have the same distribution on a descent class, and their common multivariate generating function is a flagged ribbon Schur function.

---

13. Walking Cautiously Into the Collatz Wilderness: Algorithmically, Number Theoretically, Randomly

Edward G. Belaga ; Maurice Mignotte.

Building on theoretical insights and rich experimental data of our preprints, we present here new theoretical and experimental results in three interrelated approaches to the Collatz problem and its generalizations: \emphalgorithmic decidability, random behavior, and Diophantine representation of related discrete dynamical systems, and their \emphcyclic and divergent properties.

---

14. The Diameter of the Minimum Spanning Tree of a Complete Graph

Louigi Addario-Berry ; Nicolas Broutin ; Bruce Reed.

Let $X_1,\ldots,X_{n\choose 2}$ be independent identically distributed weights for the edges of $K_n$. If $X_i \neq X_j$ for$ i \neq j$, then there exists a unique minimum weight spanning tree $T$ of $K_n$ with these edge weights. We show that the expected diameter of $T$ is $Θ (n^{1/3})$. This settles a question of [Frieze97].

---

15. Complete k-ary trees and generalized meta-Fibonacci sequences

Chris Deugau ; Frank Ruskey.

We show that a family of generalized meta-Fibonacci sequences arise when counting the number of leaves at the largest level in certain infinite sequences of k-ary trees and restricted compositions of an integer. For this family of generalized meta-Fibonacci sequences and two families of related sequences we derive ordinary generating functions and recurrence relations.

---

16. A coupon collector's problem with bonuses

Toshio Nakata ; Izumi Kubo.

In this article, we study a variant of the coupon collector's problem introducing a notion of a \emphbonus. Suppose that there are c different types of coupons made up of bonus coupons and ordinary coupons, and that a collector gets every coupon with probability 1/c each day. Moreover suppose that every time he gets a bonus coupon he immediately obtains one more coupon. Under this setting, we consider the number of days he needs to collect in order to have at least one of each type. We then give not only the expectation but also the exact distribution represented by a gamma distribution. Moreover we investigate their limits as the Gumbel (double exponential) distribution and the Gauss (normal) distribution.

---

17. A probabilistic analysis of a leader election algorithm

Hanene Mohamed.

A leader election algorithm is an elimination process that divides recursively into tow subgroups an initial group of n items, eliminates one subgroup and continues the procedure until a subgroup is of size 1. In this paper the biased case is analyzed. We are interested in the cost of the algorithm e. the number of operations needed until the algorithm stops. Using a probabilistic approach, the asymptotic behavior of the algorithm is shown to be related to the behavior of a hitting time of two random sequences on [0,1].

---

18. Concentration Properties of Extremal Parameters in Random Discrete Structures

Michael Drmota.

The purpose of this survey is to present recent results concerning concentration properties of extremal parameters of random discrete structures. A main emphasis is placed on the height and maximum degree of several kinds of random trees. We also provide exponential tail estimates for the height distribution of scale-free trees.

---

19. Analysis of a new skip list variant

Guy Louchard ; Helmut Prodinger.

For a skip list variant, introduced by Cho and Sahni, we analyse what is the analogue of horizontal plus vertical search cost in the original skip list model. While the average in Pugh's original version behaves like $Q \log_Q n$, with $Q = \frac{1}{q}$ a parameter, it is here given by $(Q+1) \log_Q n$.

---

20. Survival probability of a critical multi-type branching process in random environment

Elena Dyakonova.

We study a multi-type branching process in i.i.d. random environment. Assuming that the associated random walk satisfies the Doney-Spitzer condition, we find the asymptotics of the survival probability at time $n$ as $n \to \infty$.

---

21. Polyominoes determined by permutations

I. Fanti ; A. Frosini ; E. Grazzini ; R. Pinzani ; S. Rinaldi.

In this paper we consider the class of $\textit{permutominoes}$, i.e. a special class of polyominoes which are determined by a pair of permutations having the same size. We give a characterization of the permutations associated with convex permutominoes, and then we enumerate various classes of convex permutominoes, including parallelogram, directed-convex, and stack ones.

---

22. Constrained exchangeable partitions

Alexander Gnedin.

For a class of random partitions of an infinite set a de Finetti-type representation is derived, and in one special case a central limit theorem for the number of blocks is shown.

---

23. Limit distribution of the size of the giant component in a web random graph

Yuri Pavlov.

Consider random graph with $N+ 1$ vertices as follows. The degrees of vertices $1,2,\ldots, N$ are the independent identically distributed random variables $\xi_1, \xi_2, \ldots , \xi_N$ with distribution $\mathbf{P}\{\xi_1 \geq k\}=k^{− \tau},$ $k= 1,2,\ldots,$ $\tau \in (1,2)$,(1) and the vertex $N+1$ has degree $0$, if the sum $\zeta_N=\xi_1+ \ldots +\xi_N$ is even, else degree is $1$. From (1) we get that $p_k=\mathbf{P}\{\xi_1=k\}=k^{−\tau}−(k+ 1)^{−\tau}$, $k= 1,2,\ldots$ Let $G(k_1, \ldots , k_N)$ be a set of graphs with $\xi_1=k_1,\ldots, \xi_N=k_N$. If $g$ is a realization of random graph then $\mathbf{P}\{g \in G(k_1, \ldots , k_N)\}=p_{k_1} \cdot \ldots \cdot p_{k_N}$. The probability distribution on the set of graph is defined such that for a vector $(k_1, \ldots, k_N)$ all graphs, lying in $G(k_1, \ldots , k_N)$, are equiprobable. Studies of the past few years show that such graphs are good random graph models for Internet and other networks topology description (see, for example, H. Reittu and I. Norros (2004)).To build the graph, we have $N$ numbered vertices and incident to vertex $i \xi_i$ stubs, $i= 1, \ldots , N$.All stubs need to be connected to another stub to construct the graph. The stubs are numbered in an arbitrary order from $1$ to $\zeta_N$. Let $\eta_{(N)}$ be the maximum degree of the vertices.

---

24. Samples of geometric random variables with multiplicity constraints

Margaret Archibald ; Arnold Knopfmacher.

We investigate the probability that a sample $\Gamma=(\Gamma_1,\Gamma_2,\ldots,\Gamma_n)$ of independent, identically distributed random variables with a geometric distribution has no elements occurring exactly $j$ times, where $j$ belongs to a specified finite $\textit{'forbidden set'}$ $A$ of multiplicities. Specific choices of the set $A$ enable one to determine the asymptotic probabilities that such a sample has no variable occuring with multiplicity $b$, or which has all multiplicities greater than $b$, for any fixed integer $b \geq 1$.

---

25. Trees with product-form random weights

Konstantin Borovkov ; Vladimir Vatutin.

We consider growing random recursive trees in random environment, in which at each step a new vertex is attached according to a probability distribution that assigns the tree vertices masses proportional to their random weights.The main aim of the paper is to study the asymptotic behavior of the mean numbers of outgoing vertices as the number of steps tends to infinity, under the assumption that the random weights have a product form with independent identically distributed factors.

---

26. Efficient estimation of the cardinality of large data sets

Philippe Chassaing ; Lucas Gerin.

Giroire has recently proposed an algorithm which returns the $\textit{approximate}$ number of distinct elements in a large sequence of words, under strong constraints coming from the analysis of large data bases. His estimation is based on statistical properties of uniform random variables in $[0,1]$. In this note we propose an optimal estimation, using Kullback information and estimation theory.

---

27. Structure of Stable Sand Piles Model

Thi Ha Duong Phan ; Thi Thu Huong Tran.

In this paper we study a variant of the Sand Piles Model, where the evolution rule consists of the falling down of one grain to a random column and an avalanche to reach a stable configuration. We prove that the infinite set of all stable configurations have a lattice structure which is a sublattice of Young lattice. At the end, based on a discussion about avalanches, we construct a generating tree of this model and show its strongtly recursive structure.

---

28. Spanning trees of finite Sierpiński graphs

Elmar Teufl ; Stephan Wagner.

We show that the number of spanning trees in the finite Sierpiński graph of level $n$ is given by $\sqrt[4]{\frac{3}{20}} (\frac{5}{3})^{-n/2} (\sqrt[4]{540})^{3^n}$. The proof proceeds in two steps: First, we show that the number of spanning trees and two further quantities satisfy a $3$-dimensional polynomial recursion using the self-similar structure. Secondly, it turns out, that the dynamical behavior of the recursion is given by a $2$-dimensional polynomial map, whose iterates can be computed explicitly.

---

29. Left and right length of paths in binary trees or on a question of Knuth

Alois Panholzer.

We consider extended binary trees and study the common right and left depth of leaf $j$, where the leaves are labelled from left to right by $0, 1, \ldots, n$, and the common right and left external pathlength of binary trees of size $n$. Under the random tree model, i.e., the Catalan model, we characterize the common limiting distribution of the suitably scaled left depth and the difference between the right and the left depth of leaf $j$ in a random size-$n$ binary tree when $j \sim \rho n$ with $0< \rho < 1$, as well as the common limiting distribution of the suitably scaled left external pathlength and the difference between the right and the left external pathlength of a random size-$n$ binary tree.

---

30. Average depth in a binary search tree with repeated keys

Margaret Archibald ; Julien Clément.

Random sequences from alphabet $\{1, \ldots,r\}$ are examined where repeated letters are allowed. Binary search trees are formed from these, and the average left-going depth of the first $1$ is found. Next, the right-going depth of the first $r$ is examined, and finally a merge (or 'shuffle') operator is used to obtain the average depth of an arbitrary node, which can be expressed in terms of the left-going and right-going depths. The variance of each of these parameters is also found.

---

31. On the number of decomposable trees

Stephan G. Wagner.

A tree is called $k$-decomposable if it has a spanning forest whose components are all of size $k$. Analogously, a tree is called $T$-decomposable for a fixed tree $T$ if it has a spanning forest whose components are all isomorphic to $T$. In this paper, we use a generating functions approach to derive exact and asymptotic results on the number of $k$-decomposable and $T$-decomposable trees from a so-called simply generated family of trees - we find that there is a surprisingly simple functional equation for the counting series of $k$-decomposable trees. In particular, we will study the limit case when $k$ goes to $\infty$. It turns out that the ratio of $k$-decomposable trees increases when $k$ becomes large.

---

32. An extension to overpartitions of Rogers-Ramanujan identities for even moduli

Sylvie Corteel ; Jeremy Lovejoy ; Olivier Mallet.

We investigate class of well-poised basic hypergeometric series $\tilde{J}_{k,i}(a;x;q)$, interpreting these series as generating functions for overpartitions defined by multiplicity conditions. We also show how to interpret the $\tilde{J}_{k,i}(a;1;q)$ as generating functions for overpartitions whose successive ranks are bounded, for overpartitions that are invariant under a certain class of conjugations, and for special restricted lattice paths. We highlight the cases $(a,q) \to (1/q,q)$, $(1/q,q^2)$, and $(0,q)$, where some of the functions $\tilde{J}_{k,i}(a;x;q)$ become infinite products. The latter case corresponds to Bressoud's family of Rogers-Ramanujan identities for even moduli.

---

33. Accessible and Deterministic Automata: Enumeration and Boltzmann Samplers

Frédérique Bassino ; Cyril Nicaud.

We present a bijection between the set $\mathcal{A}_n$ of deterministic and accessible automata with $n$ states on a $k$-letters alphabet and some diagrams, which can themselves be represented as partitions of the set $[\![ 1..(kn+1) ]\!]$ into $n$ non-empty parts. This combinatorial construction shows that the asymptotic order of the cardinality of $\mathcal{A}_n$ is related to the Stirling number $\{^{kn}_n\}$. Our bijective approach also yields an efficient random sampler of automata with $n$ states, of complexity $O(n^{3/2})$, using the framework of Boltzmann samplers.

---

34. $S$-constrained random matrices

Sylvain Gravier ; Bernard Ycart.

Let $S$ be a set of $d$-dimensional row vectors with entries in a $q$-ary alphabet. A matrix $M$ with entries in the same $q$-ary alphabet is $S$-constrained if every set of $d$ columns of $M$ contains as a submatrix a copy of the vectors in $S$, up to permutation. For a given set $S$ of $d$-dimensional vectors, we compute the asymptotic probability for a random matrix $M$ to be $S$-constrained, as the numbers of rows and columns both tend to infinity. If $n$ is the number of columns and $m=m_n$ the number of rows, then the threshold is at $m_n= \alpha_d \log (n)$, where $\alpha_d$ only depends on the dimension $d$ of vectors and not on the particular set $S$. Applications to superimposed codes, shattering classes of functions, and Sidon families of sets are proposed. For $d=2$, an explicit construction of a $S$-constrained matrix is given.

---

35. Analytic Combinatorics of Lattice Paths: Enumeration and Asymptotics for the Area

Cyril Banderier ; Bernhard Gittenberger.

This paper tackles the enumeration and asymptotics of the area below directed lattice paths (walks on $\mathbb{N}$ with a finite set of jumps). It is a nice surprise (obtained via the "kernel method'') that the generating functions of the moments of the area are algebraic functions, expressible as symmetric functions in terms of the roots of the kernel. For a large class of walks, we give full asymptotics for the average area of excursions ("discrete'' reflected Brownian bridge) and meanders ("discrete'' reflected Brownian motion). We show that drift is not playing any role in the first case. We also generalise previous works related to the number of points below a path and to the area between a path and a line of rational slope.

---

36. Label-based parameters in increasing trees

Markus Kuba ; Alois Panholzer.

Grown simple families of increasing trees are a subclass of increasing trees, which can be constructed by an insertion process. Three such tree families contained in the grown simple families of increasing trees are of particular interest: $\textit{recursive trees}$, $\textit{plane-oriented recursive trees}$ and $\textit{binary increasing trees}$. Here we present a general approach for the analysis of a number of label-based parameters in a random grown simple increasing tree of size $n$ as, e.g., $\textit{the degree of the node labeled j}$, $\textit{the subtree-size of the node labeled j}$, etc. Further we apply the approach to the random variable $X_{n,j,a}$, which counts the number of size-$a$ branches attached to the node labeled $j$ (= subtrees of size $a$ rooted at the children of the node labeled $j$) in a random grown simple increasing tree of size $n$. We can give closed formulæ for the probability distribution and the factorial moments. Furthermore limiting distribution results for $X_{n,j,a}$ are given dependent on the growth behavior of $j=j(n)$ compared to $n$.

---

37. Conditioned Galton-Watson trees do not grow

Svante Janson.

An example is given which shows that, in general, conditioned Galton-Watson trees cannot be obtained by adding vertices one by one, while this can be done in some important but special cases, as shown by Luczak and Winkler.

---

38. Around the root of random multidimensional quadtrees

Gilbert Labelle ; Louise Laforest ; Xavier Provençal.

We analyse the distribution of the root pattern of randomly grown multidimensional point quadtrees. In particular, exact, recursive and asymptotic formulas are given for the expected arity of the root.

---

39. A Cross Entropy Algorithm for Classification with $\delta$−Patterns

Gabriela Alexe ; Gyan Bhanot ; Adriana Climescu-Haulica.

A classification strategy based on $\delta$-patterns is developed via a combinatorial optimization problem related with the maximal clique generation problem on a graph. The proposed solution uses the cross entropy method and has the advantage to be particularly suitable for large datasets. This study is tailored for the particularities of the genomic data.

---

40. Bipartite Random Graphs and Cuckoo Hashing

Reinhard Kutzelnigg.

The aim of this paper is to extend the analysis of Cuckoo Hashing of Devroye and Morin in 2003. In particular we make several asymptotic results much more precise. We show, that the probability that the construction of a hash table succeeds, is asymptotically $1-c(\varepsilon)/m+O(1/m^2)$ for some explicit $c(\varepsilon)$, where $m$ denotes the size of each of the two tables, $n=m(1- \varepsilon)$ is the number of keys and $\varepsilon \in (0,1)$. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph. We apply a double saddle point method to obtain asymptotic results covering tree sizes, the number of cycles and the probability that no complex component occurs.

---

41. Explicit computation of the variance of the number of maxima in hypercubes

Christian Costermans ; Hoang Ngoc Minh.

We present a combinatorial approach of the variance for the number of maxima in hypercubes. This leads to an explicit expression, in terms of Multiple Zeta Values, of the dominant term in the asymptotic expansion of this variance.Moreover, we get an algorithm to compute this expansion, and show that all coefficients occuring belong to the $\mathbb{Q}$-algebra generated by Multiple Zeta Values, and by Euler's constant $\gamma$.

---

42. Extended Rate, more GFUN

Martin Rubey.

We present a software package that guesses formulas for sequences of, for example, rational numbers or rational functions, given the first few terms. Thereby we extend and complement Christian Krattenthaler’s program $\mathtt{Rate}$ and the relevant parts of Bruno Salvy and Paul Zimmermann’s $\mathtt{GFUN}$.

---