COMBINATORIAL VARIATIONS ON MULTIDIMENSIONAL QUADTREES

We present a parallel study of three variants of the notion of multidi mensional quadtrees: quadtrees of Catalan's type, increasing quadtrees , and point quadtrees. Using the language of the theory of species, we present for these models of tree-like structures some combinatorial e quations that lead, for example, to several explicit, recursive or asy mptotic formulas for the probability of having k nodes in a fixed hype roctant, the expected value and the variance of the number of leaves. (c) 1995 Academic Press, Inc.