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 a random recursive DAG G_n on the vertex set [n] where every vertex i ≥ 2 has out-degree d, with the targets chosen uniformly at random among the earlier i-1 vertices. For this model, we propose a novel way to investigate the descendants of n (which have recently been studied in a paper by Janson) through what we call ancestry processes. The ancestor process a_i(n) of a vertex i is defined as the number of ancestors of i in G_n, and is closely related to the evolutions of multi-draw Pólya urns. Results on the descendants can then be obtained via asymptotic results on functionals of the ancestry processes, generally leading to technical integral expressions. We employ this method to make progress on two open problems posed by Janson, as well as to provide an alternative proof of a first-moment result contained in his work. We further prove limit theorems for the ancestor processes a_i(n) depending on i.

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.

We propose a modification to the random destruction of graphs: Given a finite network with a distinguished set of sources and targets, remove (cut) vertices at random, discarding components that do not contain a source node. We investigate the number of cuts required until all targets are removed, and the size of the remaining graph. This model interpolates between the random cutting model going back to Meir and Moon [28] and site percolation. We prove several general results, including that the size of the remaining graph is a tight family of random variables for compatible sequences of expander-type graphs, and determine limiting distributions complete binary trees.