On Multitype Random Forests with a Given Degree Sequence, the Total Population of Branching Forests and Enumerations of Multitype Forests

Osvaldo Angtuncio Hernández

Published 2020-03-06Version 1

In this chapter we introduce the model of multitype random forests chosen uniformly at random from the set of multitype forest with a given degree sequence, denoted by MFGDS. The unitype case was studied by Broutin and Marckert (2014). By mixing our model, one obtains multitype Galton-Watson (MGW) forests conditioned with the number of individuals by types (CMGW). The construction of MFGDS is done using the results of Chaumont and Liu (2016), and a novel path transformation on multidimensional discrete exchangeable increments processes, which is a generalization of the Vervaat transform (Vervaat 1979). We also obtain the joint law of the number of individuals by types in a MGW forest, generalizing the Otter-Dwass formula (Otter 1949, Dwass 1969). This allows us to obtain enumerations of multitype forests with a combinatorial structure (plane, labeled and binary forest), having a prescribed number of roots and individuals by types. Finally, under certain hypotheses, we give an algorithm to simulate CMGW forests, generalizing the unitype case given by Devroye (2012).