In this paper we study cycles in multiset permutations and parking functions. As combinatorial objects, multiset permutations are essential building blocks for mappings and permutations, while parking functions lie between mappings and permutations. We take both algebraic and analytic views in our investigation and present exact as well as asymptotic results. We point to a surprising correspondence between two statistics on multiset permutations, terminal closers and cyclic points, shedding light on the combinatorial structure.

We consider the asymptotic enumeration of labelled acyclic digraphs (DAGs) with the additional restriction of being bipartite. The analysis leads us to a meromorphic generating function in two variables for the number of bicoloured labelled DAGs whose analysis falls within the scope of analytic combinatorics in several variables. This allows us to obtain asymptotic formulas for the total number of labelled bipartite DAGs with a given number of vertices as well as for the number of such DAGs with a given bipartition (i.e., with prescribed sizes of the two partite sets).

We consider two closely related concepts in rooted trees: the path length is the sum of all distances from the root to the vertices of the tree, while the external path length is the sum of all distances from the root to the leaves of the tree. Upon dividing by the number of vertices and leaves respectively, we obtain the average distance to the root. For two important classes of random trees, we show that the average distance of the root to a random leaf is almost the same as the average distance to a random vertex. For Bienaymé-Galton-Watson trees, the difference is bounded in probability. For three varieties of increasing trees (recursive trees, d-ary increasing trees, generalised plane-oriented recursive trees), on the other hand, the difference converges to a constant in probability.

A B -tree is a type of search tree where every node (except possibly for the root) contains between m and 2 m keys for some positive integer m , and all leaves have the same distance to the root. We study sequences of B -trees that can arise from successively inserting keys, and in particular present a bijection between such sequences (which we call histories) and a special type of increasing trees. We describe the set of permutations for the keys that belong to a given history, and also show how to use this bijection to analyse statistics associated with B -trees.

Making use of a newly developed package in the computer mathematics system SageMath, we show how to perform a full asymptotic analysis of certain types of sums that occur frequently in combinatorics, including explicit error bounds. We present two applications of the general approach to illustrate its use: the first concerns a classical problem due to Ramanujan, while the second one concerns a question of Bóna and DeJonge on 132-avoiding permutations with a unique longest increasing subsequence that can be translated into an inequality for a certain binomial sum.

Composition schemes are ubiquitous in combinatorics, statistical mechanics and probability theory. We give a unifying explanation to various phenomena observed in the combinatorial and statistical physics literature in the context of~$q$-enumeration (this is a model where objects with a parameter of value $k$ have a Gibbs measure/Boltzmann weight $q^k$). For structures enumerated by a composition scheme, we prove a phase transition for any parameter having such a Gibbs measure: for a critical value $q=q_c$, the limit law of the parameter is a two-parameter Mittag-Leffler distribution, while it is Gaussian in the supercritical regime ($q>q_c$), and it is a Boltzmann distribution in the subcritical regime ($0

Abstract A fringe subtree of a rooted tree is a subtree induced by one of the vertices and all its descendants. We consider the problem of estimating the number of distinct fringe subtrees in random trees under a generalized notion of distinctness, which allows for many different interpretations of what “distinct” trees are. The random tree models considered are simply generated trees and families of increasing trees (recursive trees, d-ary increasing trees and generalized plane-oriented recursive trees). We prove that the order of magnitude of the number of distinct fringe subtrees (under rather mild assumptions on what ‘distinct’ means) in random trees with n vertices is $$n/\sqrt{\log n}$$ n / log n for simply generated trees and $$n/\log n$$ n / log n for increasing trees.

We study block statistics in subcritical graph classes; these are statistics that can be defined as the sum of a certain weight function over all blocks. Examples include the number of edges, the number of blocks, and the logarithm of the number of spanning trees. The main result of this paper is a central limit theorem for statistics of this kind under fairly mild technical assumptions.

Given a positive integer n and a real number p ∈ [0,1], let D(n,p) denote the random digraph defined in the following way: each of the binom(n,2) possible edges on the vertex set {1,2,3,…,n} is included with probability 2p, where all edges are independent of each other. Thereafter, a direction is chosen independently for each edge, with probability 1/2 for each possible direction. In this paper, we study the probability that a random instance of D(n,p) is acyclic, i.e., that it does not contain a directed cycle. We find precise asymptotic formulas for the probability of a random digraph being acyclic in the sparse regime, i.e., when np = O(1). As an example, for each real number μ, we find an exact analytic expression for φ(μ) = lim_{n→ ∞} n^{1/3} ℙ{D(n,1/n (1+μ n^{-1/3})) is acyclic}.

Tanglegrams are structures consisting of two binary rooted trees with the same number of leaves and a perfect matching between the leaves of the two trees. We say that a tanglegram is planar if it can be drawn in the plane without crossings. Using a blend of combinatorial and analytic techniques, we determine an asymptotic formula for the number of planar tanglegrams with n leaves on each side.

An additive functional of a rooted tree is a functional that can be calculated recursively as the sum of the values of the functional over the branches, plus a certain toll function. Janson recently proved a central limit theorem for additive functionals of conditioned Galton-Watson trees under the assumption that the toll function is local, i.e. only depends on a fixed neighbourhood of the root. We extend his result to functionals that are almost local, thus covering a wider range of functionals. Our main result is illustrated by two explicit examples: the (logarithm of) the number of matchings, and a functional stemming from a tree reduction process that was studied by Hackl, Heuberger, Kropf, and Prodinger.

In analogy to other concepts of a similar nature, we define the inducibility of a rooted binary tree. Given a fixed rooted binary tree $B$ with $k$ leaves, we let $\gamma(B,T)$ be the proportion of all subsets of $k$ leaves in $T$ that induce a tree isomorphic to $B$. The inducibility of $B$ is $\limsup_{|T| \to \infty} \gamma(B,T)$. We determine the inducibility in some special cases, show that every binary tree has positive inducibility and prove that caterpillars are the only binary trees with inducibility $1$. We also formulate some open problems and conjectures on the inducibility. Finally, we present an application to crossing numbers of random tanglegrams.

For a fixed integer base $$b\ge 2$$ , we consider the number of compositions of 1 into a given number of powers of b and, related, the maximum number of representations a positive integer can have as an ordered sum of powers of b. We study the asymptotic growth of those numbers and give precise asymptotic formulae for them, thereby improving on earlier results of Molteni. Our approach uses generating functions, which we obtain from infinite transfer matrices. With the same techniques the distribution of the largest denominator and the number of distinct parts are investigated.

Hereditarily finite sets (sets which are finite and have only hereditarily finite sets as members) are basic mathematical and computational objects, and also stand at the basis of some programming languages. We solve an open problem proposed by Kirby in 2008 concerning a recurrence relation for the cardinality an of the n-th level of the adjunctive hierarchy of hereditarily finite sets; in this hierarchy, new sets are formed by the addition of a new single element drawn from the already existing sets to an already existing set. We also show that our results can be generalized to sets with atoms, or can be refined by rank, cardinality, or by the maximum level from where the new adjoined element is drawn. We also show that an satisfies the asymptotic formula an=C2n+O(C2n−1)⁠, for a constant C≈1.3399⁠, which is a too fast asymptotic growth for practical purposes. We thus propose a very natural variant of the adjunctive hierarchy, whose asymptotic behaviour we prove to be Θ(2n)⁠.

For fixed $t\ge 2$, we consider the class of representations of $1$ as a sum of unit fractions whose denominators are powers of $t$, or equivalently the class of canonical compact $t$-ary Huffman codes, or equivalently rooted $t$-ary plane “canonical” trees. We study the probabilistic behavior of the height (limit distribution is shown to be normal), the number of distinct summands (normal distribution), the path length (normal distribution), the width (main term of the expectation and concentration property), and the number of leaves at maximum distance from the root (discrete distribution).

The correlation of graph characteristics, such as the number of independent vertex or edge subsets, the number of connected subsets, or the sum of distances, which also play a role in combinatorial chemistry, is studied by a generating function approach and asymptotic analysis. It is shown how an asymptotic formula for the correlation coefficient can be obtained when simply generated families of trees are investigated. For rooted ordered trees, the calculations are done explicitly. Further feasible correlation measures are discussed.