Nombre de Fubini

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 E à n éléments, c'est-à-dire les familles finies de parties non vides disjointes de E dont la réunion est égale à E. Par exemple, pour n = 3, il y a 13 partitions ordonnées de $\{a,b,c\}$ : 6 du type $\left(\{a\},\{b\},\{c\}\right)$ , 3 du type $\left(\{a\},\{b,c\}\right)$ , 3 du type $\left(\{a,b\},\{c\}\right)$ , plus $\left(\{a,b,c\}\right)$ .

Les 13 classements avec exæquos possibles des objets a, b, c

Présentation

De manière équivalente, les nombres de Fubini dénombrent les classements de n objets, avec éventuellement des exæquos, comme dans les résultats d'une course de chevaux. Ils sont aussi appelés pour cette raison nombres chevaux[1]. Par exemple, pour n = 3, les 13 classements avec exæquos possibles se répartissent en 6 classements sans exæquos, comme $a<b<c$ , 3 avec deux premiers exæquos, comme $a<b\equiv c$ , 3 avec deux seconds exæquos, comme $a\equiv b<c$ , et 1 avec trois exæquos, $a\equiv b\equiv c$ [2].

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

\int _{A}\left(\int _{B}f(x,y)\,{\text{d}}y\right)\,{\text{d}}x=\int _{B}\left(\int _{A}f(x,y)\,{\text{d}}x\right)\,{\text{d}}y=\int _{A\times B}f(x,y)\,{\text{d}}(x,y)

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 suite A000670 de l'OEIS :

F_{0}=1,\quad F_{1}=1,\quad F_{2}=3,\quad F_{3}=13,\quad F_{4}=75,\quad F_{5}=541,\quad F_{6}=4683,\quad \ldots

la notation $F_{n}$ 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 permutoèdre (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 = 75 [4] ).

Nombres de Fubini et arbres de Cayley

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)[5] ; ce dernier les a obtenus comme dénombrement de certains arbres à n + 1 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 i de la racine est strictement inférieur au nombre de nœuds à la distance i + 1. Dans un tel arbre, il y a n 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 $S(n,k)$ dénombrant les partitions d'un n-ensemble en k parties, et ces k parties pouvant être permutées de $k!$ façons, on a :

F_{n}=\sum _{k=0}^{n}k!S(n,k)

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

$F_{n}=\sum _{k=0}^{n}\sum _{i=0}^{k}(-1)^{k-i}{\binom {k}{i}}i^{n}$

Expression en fonction des nombres eulériens

Ces nombres $A (n,k)$ dénombrant les permutations de n objets avec k "montées" (ou k "descentes"), on a :

F_{n}=\sum _{k=0}^{n}2^{k}A(n,k)=A_{n}(2),

où $A_{n}$ est le polynôme eulérien d'indice n. La démonstration ci-dessous est celle donnée dans [6].

Considérons toutes les permutations de $[n]$ , en indiquant les montées par "<" et les descentes par ">". Transformons les $k$ signes ">" d'une permutation en "<" ou en " $\equiv$ " (donc de $2^{k}$ façons). On obtient ainsi un classement quelconque avec exæquos. Par exemple $1<3>2$ va engendrer $1<3<2$ et $1<3\equiv 2$ .

On obtient donc $F_{n}=\sum _{k=0}^{n-1}2^{k}A(n,k)$ et on peut prolonger la somme jusqu'à n car $A(n,n)=0$ .

Relation de récurrence

Les nombres de Fubini, en partant de $F_{0}=1$ , peuvent être calculés via la relation de récurrence forte :

F_{n}=\sum _{k=1}^{n}{\binom {n}{k}}F_{n-k}=\sum _{k=0}^{n-1}{\binom {n}{k}}F_{k}

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

Fonction génératrice exponentielle

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

f(z)=\sum _{n=0}^{\infty }F_{n}{\frac {z^{n}}{n!}}={\frac {1}{2-e^{z}}}.

[6]

Démonstration

Par produit de Cauchy, $e^{z}f(z)=\sum _{n=0}^{+\infty }\left(\sum _{k=0}^{n}{\frac {F_{k}}{k!(n-k)!}}\right)z^{n}=1+\sum _{n=1}^{+\infty }\left({\frac {1}{n!}}\sum _{k=0}^{n-1}{\binom {n}{k}}F_{k}+{\frac {F_{n}}{n}}\right)z^{n}$ .

En utilisant la relation de récurrence, on obtient $e^{z}f(z)=1+\sum _{n=1}^{+\infty }{\frac {2F_{n}}{n!}}z^{n}=2f(z)-1$ , d'où le résultat.

En écrivant que ${\frac {1}{2-e^{z}}}=\sum _{k\geqslant 0}{\frac {e^{kz}}{2^{k+1}}}$ et en développant $e^{kz}$ , on obtient l’expression des nombres de Fubini comme somme de série :

F_{n}={\frac {1}{2}}\sum _{k=0}^{+\infty }{\frac {k^{n}}{2^{k}}},

[6]

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 $(2I-T)^{-1}$ , où $I$ est la matrice d'identité et $T$ la matrice de Pascal triangulaire supérieure[7].

Équivalent

En utilisant une intégrale curviligne de ${\frac {f(z)}{z^{n+1}}}$ et appliquant le théorème des résidus, les nombres de Fubini s'expriment pour $n\geqslant 1$ par la somme infinie

F_{n}={\frac {n!}{2}}\sum _{k=-\infty }^{\infty }{\frac {1}{(\ln 2+2ik\pi )^{n+1}}}

dont on déduit l'équivalent

F_{n}\sim {\frac {n!}{2(\ln 2)^{n+1}}}.

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

{\frac {F_{n+1}}{F_{n}}}\sim n\ln 2.

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,

F_{n+4}\equiv F_{n}{\pmod {10}},

F_{n+20}\equiv F_{n}{\pmod {100}},

F_{n+100}\equiv F_{n}{\pmod {1000}},

F_{n+500}\equiv F_{n}{\pmod {10000}}.

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

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Ordered Bell number » (voir la liste des auteurs).

Jean-Marie DE KONINCK, Ces nombres qui nous fascinent, Paris, Ellipse, 2008 (ISBN 978-2-7298-3851-5), p. 4
Ces classements avec exæquos possibles peuvent être formalisés comme relations binaires réflexives et transitives où tout couple est comparable, autrement dit des préordres totaux.
Louis Comtet, Analyse combinatoire, tome second, PUF, 1970, p. 64
1, 14, 36, 24, est la quatrième ligne de la suite A019538 de l'OEIS.
(en) Arthur Cayley, « On the analytical forms called trees, second part », Philosophical Magazine, Series IV, 18 (121), In Collected Works of Arthur Cayley, p. 112,‎ 1859, p. 374–378 (lire en ligne)
R. L. Graham, D. E. Knuth, O. Patashnik, Mathematiques concrètes, exercice 7.44, International Thomson Publishing France, 1998 p. (ISBN 2-84180-981-1), p. 401 et 604
(en) Barry Lewis, « Revisiting the Pascal matrix », American Mathematical Monthly, 117 (1),‎ 2010, p. 50–66. (lire en ligne)
(en) Good, I. J, « The number of orderings of n candidates when ties are permitted », Fibonacci Quarterly, 13,‎ 1975, p. 11–18 (lire en ligne)

Voir aussi

Le coefficient multinomial ${n \choose k_{1},k_{2},k_{3},\ldots ,k_{m}}$ qui dénombre les partitions ordonnées $(I_{1},\cdots ,I_{m})$ de $\{1,\cdots ,n\}$ telles que $|I_{1}|=k_{1},\cdots ,|I_{m}|=k_{m}$ .

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.