Formule d'inversion de möbius

Formule d'inversion de möbius

Formule d'inversion de Möbius

La formule d’inversion de Möbius classique a été introduite dans la théorie des nombres au cours du XIXe siècle par August Ferdinand Möbius. Elle a été généralisée plus tard à d’autres « formules d’inversion de Möbius »; voir l’algèbre d'incidence. La version classique déclare que si f et g sont des fonctions arithmétiques vérifiant

\forall n\in \mathbb{N}^* \quad g(n)=\sum_{d\mid n}f(d)

alors

\forall n\in \mathbb{N}^* \quad f(n)=\sum_{d\mid n}g(d)\mu(n/d)

où μ est la fonction de Möbius et les sommes portent sur tous les diviseurs positifs d de n. La formule reste valable si f et g sont des fonctions définies sur l’ensemble des entiers naturels non nuls à valeurs dans un certain groupe abélien.

En utilisant la convolution (voir fonction multiplicative), la formule d’inversion peut également s’écrire

μ * 1 = ε (en fait μ * 1 * f = f)

où 1 est la fonction constante prenant la valeur 1, et ε est la fonction telle que ε(1)=1 et pour tout n≠1, ε(n)=0.

Une formulation équivalente de la formule d’inversion plus utile en combinatoire s’énonce ainsi :

si F et G sont des fonctions définies sur l’intervalle [1, +∞[ de \mathbb{R} à valeurs complexes vérifiant

\forall x\ge 1 \quad G(x) = \sum_{1 \le n \le x}F(x/n)

alors

\forall x\ge 1 \quad F(x) = \sum_{1 \le n \le x}\mu(n)G(x/n)

Ici les sommes portent sur des entiers naturels non nuls qui sont inférieurs ou égaux à x.

La formule d’inversion de Möbius donnée ci-dessus est la formule d’inversion originale de Möbius. Lorsque l’ensemble partiellement ordonné des nombres entiers muni de la relation de divisibilité est remplacé par d’autres ensembles partiellement ordonnés localement finis, nous obtenons d’autres formules d’inversion de Möbius comprenant entre autres le principe d'inclusion-exclusion de Moivre ; pour avoir un aperçu, voir l’algèbre d'incidence.

Une application: dénombrement des irréductibles de \mathbf{F}_{p}[X] de degré donné

Soit p un nombre premier et \mathbf{F}_{p} le corps fini à p éléments. Par des arguments d'algèbre élémentaires on peut démontrer que, pour tout entier naturel non nul n, X^{p^{n}}-X est le produit des polynômes irréductibles unitaires de \mathbf{F}_{p}[X] dont le degré divise n; en notant \nu(d)\, le nombre d'irréductibles unitaires de degré d on a donc, en prenant les degrés: \sum_{d|n}{d\nu(d)}=p^{n}\,. La formule d'inversion de Möbius permet alors d'obtenir, avec f(n)=n\nu(n)\, et g(n)=p^{n}\, : \nu(n)=\frac{1}{n}\sum_{d|n}{\mu(n/d)p^{d}}\,. On voit en particulier que \nu(n)\, n'est jamais nul.

Voir aussi

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Formule d%27inversion de M%C3%B6bius ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Formule d'inversion de möbius de Wikipédia en français (auteurs)

Игры ⚽ Нужно сделать НИР?

Regardez d'autres dictionnaires:

  • Formule D'inversion De Möbius — La formule d’inversion de Möbius classique a été introduite dans la théorie des nombres au cours du XIXe siècle par August Ferdinand Möbius. Elle a été généralisée plus tard à d’autres « formules d’inversion de Möbius »; voir l’algèbre… …   Wikipédia en Français

  • Formule d'inversion de Mobius — Formule d inversion de Möbius La formule d’inversion de Möbius classique a été introduite dans la théorie des nombres au cours du XIXe siècle par August Ferdinand Möbius. Elle a été généralisée plus tard à d’autres « formules d’inversion de… …   Wikipédia en Français

  • Formule d'inversion de Möbius — La formule d’inversion de Möbius classique a été introduite dans la théorie des nombres au cours du XIXe siècle par August Ferdinand Möbius. Elle a été généralisée plus tard à d’autres « formules d’inversion de Möbius ». Énoncé La… …   Wikipédia en Français

  • Formule Du Crible De Poincaré — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du …   Wikipédia en Français

  • Formule du crible — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du …   Wikipédia en Français

  • Formule du crible de Poincare — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du …   Wikipédia en Français

  • Formule du crible de Poincaré — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du …   Wikipédia en Français

  • Formule du crible de poincaré — Principe d inclusion exclusion Exemple d inclusion exclusion à partir de trois ensembles. En combinatoire, le principe d’inclusion exclusion permet d’exprimer le nombre d’éléments (ou cardinal) d une réunion finie d ensembles finis en fonction du …   Wikipédia en Français

  • Fonction De Möbius — Pour les articles homonymes, voir Moebius. August Ferdinand Möbius est le premier à étudier systématiquement la fonction qui por …   Wikipédia en Français

  • Fonction de Mobius — Fonction de Möbius Pour les articles homonymes, voir Moebius. August Ferdinand Möbius est le premier à étudier systématiquement la fonction qui por …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”