vignette|Les 13 classements avec exæquos possibles des objets a, b, c En mathématiques, et plus particulièrement en combinatoire, les nombres de Fubini, ou nombres de Bell ordonnés, dénombrent les partitions ordonnées d'un ensemble à éléments, c'est-à-dire les familles finies de parties non vides disjointes de dont la réunion est égale à . Par exemple, pour , il y a 13 partitions ordonnées de : 6 du type , 3 du type , 3 du type , plus .

Présentation De manière équivalente, les nombres de Fubini dénombrent les classements de objets, avec éventuellement des ex æquo, comme dans les résultats d'une course de chevaux. Ils sont aussi appelés pour cette raison nombres chevaux. Par exemple, pour , les 13 classements avec ex æquo possibles se répartissent en six classements sans ex æquo, comme , trois avec deux premiers ex æquo, comme , trois avec deux seconds ex æquo, comme , et un avec trois ex æquo, Ces classements avec ex æquo possibles peuvent être formalisés comme relations binaires réflexives et transitives où tout couple est comparable, autrement dit des préordres totaux..

L'appellation « nombres de Fubini » vient de leur introduction par Louis Comtet, sous la forme du dénombrement des diverses formes équivalentes d'une somme ou d'une intégrale n-uple, en conséquence du théorème de Fubini. Par exemple, une intégrale double, possède trois formes équivalentes :

.

L'appellation « nombres de Bell ordonnés » provient de celle des nombres de Bell qui dénombrent les partitions non ordonnées.

Les nombres de Fubini forment la :,la notation pouvant porter à confusion avec la notation identique des nombres de Fibonacci, ainsi que ceux de Fermat.

Les nombres de Fubini peuvent être calculés via une formule de sommation impliquant des coefficients binomiaux, ou via une relation de récurrence. Outre les partitions ordonnées, ils dénombrent plusieurs autres types d'objets combinatoires, tels que les partitions multiplicatives ordonnées d'un carré d'entier ou les faces de toutes dimensions d'un (par exemple, le nombre de faces de toutes dimensions de l'hexagone est 1 + 6 + 6 = 13 et celui de l'octaèdre tronqué est 1 + 14 + 36 + 24 = 751, 14, 36, 24, est la quatrième ligne de la .).

Nombres de Fubini et arbres de Cayley vignette|300x300px|Les 13 arbres avec des feuilles ordonnées et des chemins racine-feuille de longueurs égales ; les trois espaces entre les feuilles adjacentes sont marqués par la hauteur au-dessus des feuilles de l'ancêtre commun le plus proche. Ceci induit un classement sur ces espaces. Par exemple, « 1 1 2 » indique que les deux premiers espaces sont exæquos et le troisième est deuxième dans le classement. Les nombres de Fubini apparaissent dans un article de Cayley (1859) ; ce dernier les a obtenus comme dénombrement de certains arbres à feuilles, arbres dont les chemins de la racine jusqu'à une feuille sont de même longueur, et dont le nombre de nœuds à la distance de la racine est strictement inférieur au nombre de nœuds à la distance . Dans un tel arbre, il y a paires de feuilles adjacentes, auxquelles on attribue la hauteur de leur plus petit ancêtre commun ; ces derniers nombres déterminent un rang dans un classement avec exæquo de ces paires de feuilles, et inversement ce classement détermine l'arbre.

Formules

Expression en fonction des nombres de Stirling de seconde espèce Ces nombres dénombrant les partitions d'un n-ensemble en parties, et ces parties pouvant être permutées de façons, on a :

En utilisant la formule explicite des nombres de Stirling, on en déduit la formule suivante impliquant des coefficients binomiaux:

Expression en fonction des nombres eulériens Ces nombres dénombrant les permutations de objets avec « montées » (ou « descentes »), on a :

où est le polynôme eulérien d'indice . La démonstration ci-dessous est celle donnée dans. Considérons toutes les permutations de , en indiquant les montées par « < » et les descentes par « > ». Transformons les signes « > » d'une permutation en « < » ou en « » (donc de façons). On obtient ainsi un classement quelconque avec exæquos. Par exemple va engendrer et .

On obtient donc et on peut prolonger la somme jusqu'à n car . La formule donne alors , voir la .

Relation de récurrence Les nombres de Fubini, en partant de , peuvent être calculés via la relation de récurrence forte :

Cette formule provient de ce qu'une partition ordonnée d'un n-ensemble est obtenue par le choix d'un ensemble non vide à éléments (la première classe de la partition), puis d'une partition ordonnée sur les éléments restants .

Fonction génératrice exponentielle La fonction génératrice exponentielle des nombres de Fubini est donnée par

Par produit de Cauchy, .

En utilisant la relation de récurrence, on obtient , d'où le résultat.

En écrivant que et en développant , on obtient l’expression des nombres de Fubini comme somme de série :

expression à mettre en parallèle avec la formule de Dobinski pour les nombres de Bell.

On en déduit aussi que les nombres de Fubini sont les nombres de la première ligne de la matrice infinie , où est la matrice d'identité et la matrice de Pascal triangulaire supérieure.

Équivalent En utilisant une intégrale curviligne de et appliquant le théorème des résidus, les nombres de Fubini s'expriment pour par la somme infinie

dont on déduit l'équivalent

Comme ln 2 est inférieur à 1, ceci montre que les nombres de Fubini surpassent les factorielles (qui dénombrent les classements sans exæquo) d'un facteur exponentiel. On en déduit

Récurrence et périodicités modulaires À l'aide de la relation de récurrence, on montre que ces nombres obéissent à certains modèles périodiques de l'arithmétique modulaire : pour  n assez grand,

et

Plusieurs autres identités modulaires ont été données par Good (1975).

Notes et références

Voir aussi

Le coefficient multinomial qui dénombre les partitions ordonnées de telles que .

Catégorie:Suite d'entiers Catégorie:Pages avec des traductions non relues