Quelques r\'esultats concernant les arborescences hyperquaternaires de recherche

Les arborescences multidimensionnelles de recherche que nous appelons ``arborescences hyperquaternaires'' sont une g\'en\'eralisation des arborescences binaires de recherche. L'esp\'erance du nombre de n\oe uds ayant une propri\'et\'e P donn\'ee v\'erifie la r\'ecurrence fondamentale bien connue~: $\displaystyle{ e_n = p_n + 2^d \sum_{i=0}^{n-1} \pi_{n,i} e_i }$ o\`u $n$ est le nombre de n\oe uds de l'arborescence consid\'er\'ee, $d$ est la dimension, $e_n = e_{n,d}$ est l'esp\'erance voulue, $p_n = p_{n,d}$ est la probabilit\'e que la racine ait la propri\'et\'e P et $\pi_{n,i} = \pi_{n,i,d}$ est la probabilit\'e qu'une sous-arborescence fix\'ee de la racine poss\`ede $i$ n\oe uds. Cette derni\`ere probabilit\'e admet plusieurs expressions \'equivalentes. La r\'ecurrence ci-dessus \'equivaut \`a une \'equation diff\'erentielle d'ordre $d$. Nous reformulons d'abord la r\'ecurrence en une r\'ecurrence plus simple d'ordre 1, par le biais de certaines transformations involutives sur les suites et les s\'eries. Ensuite certaines constantes ``universelles'' $\lambda_{v,d}$ ind\'ependantes des probabilit\'es $p_n$ permettent de calculer la fraction limite $\lambda(\mbox{P})$ du nombre de n\oe uds ayant la propri\'et\'e P sous la forme $\lambda(\mbox{P}) = \sum_{v=0}^{\infty} p_v \lambda_{v,d}$. Nous donnons divers exemples de cette fraction limite sous forme d'int\'egrales explicites et terminons par une analyse th\'eorique et num\'erique de ces constantes universelles.