A gene family is a set of genes having evolved from a single ancestral gene. The evolution of a gene family, from this ancestral gene to contemporary genes, can be described by a rooted binary tree (the gene tree) embedded into the evolutionary tree of the considered species (the species tree). It is not uncommon to observe discordances between a gene tree and a species tree, which motivated a large body of work in bioinformatics toward developing methods to understand such discordances. In this work, we look at the search space of such algorithms, and we provide grammars that specify the space of evolutionary histories, conditional to a given species tree. From these grammars, we can obtain asymptotics estimates for the number of evolutionary histories of a given size, as well as efficient sampling algorithms. These tools allow us to show that introducing horizontal gene transfers in an evolutionary model has a huge impact on the search space size. Moreover, our work raises several conjectures that we will discuss. This is joint work with Cedric Chauve and Yann Ponty.