Dénombrement des applications idempotentes — Les-mathematiques.net The most powerful custom community solution in the world

Dénombrement des applications idempotentes

Modifié (April 2023) dans Combinatoire et Graphes
$~~~~$Une application $\phi $ d'un ensemble $E$ dans lui-même est dite idempotente si $\phi \circ \phi =\phi $. Depuis tant de temps que je m’intéresse à la Combinatoire, je n'avais jamais prêté attention a cette question : étudier le nombre $U_{n}$ d'applications idempotentes d'un ensemble de cardinal $n$ dans lui-même. Il faut dire qu'elle n'est pas très présente dans la littérature mathématique, cette question. Même dans le monumental Handbook of Combinatorics, North-Holland 1995, 2400 pages en deux volumes, il n'y a rien à ce sujet, ou alors j'ai mal cherché. On en trouve mention dans : Comtet, Analyse Combinatoire, PUF 1970 (en exercice), et dans quelques autres rares publications.
$~~~~$Un raisonnement pas trop compliqué conduit a : $U_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$. C'est la suite A000248 de l'OEIS. La fonction génératrice exponentielle de ces nombres est : $f(x)=\sum_{n=0}^{+ \infty} U_{n}\frac{x^{n}}{n!}=e^{xe^{x}}$ (c'est l'ami Ferréol qui a donné ce résultat à l'OEIS). Ils satisfont a la relation de récurrence : $U_{n+1}=\sum_{k=0}^{n} \binom{n}{k}(n-k+1)U_{k}$. Ceci rappelle un peu les nombres de Bell $B_{n}$, nombres de partitions d'un ensemble fini, dont nous avons parlé sur ce forum il y a quelque temps.
$~~~~$Mes questions, les voici : comment démontrer tout ceci dans le cadre du programme MPSI-MP 2021 ? Pour la formule  $U_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$, ça va. En déduire la fonction génératrice exponentielle $f(x)=\sum_{n=0}^{+\infty}U_{n}\frac{x^{n}}{n!}=e^{xe^{x}}$, il me semble qu'on peut y arriver avec une interversion de $\sum $, justifiée au moyen d'une famille sommable, mais c'est à confirmer. Je vois comment prouver que la série entière $\sum_{n=0}^{+\infty}U_{n}\frac{x^{n}}{n!}$ a un rayon de convergence non nul, mais comment prouver que c'est $+\infty $ avec juste le programme MP, sans étude plus poussée des fonctions de variable complexe ? La formule de récurrence $U_{n+1}=\sum_{k=0}^{n}\binom{n}{k}(n-k+1)U_{k}$ découle de la dérivation de la fonction génératrice exponentielle, mais peut-on en donner une démonstration combinatoire ?
$~~~~$Que pensez-vous de tout ceci ?
$~~~~$Bonne journée automnale en plein printemps pourtant.
$~~~~$FR. Ch.
$~~~~$26/04/2023

Réponses

  • Modifié (April 2023)
    Bonjour,
    Je réponds à la convergence de la série. Par Stirling, on a : $$\frac{U_{n} }{n!} \leqslant  \frac{1}{n!} \,2^n\! \max\limits _{k\in [[0,n]]} k^{n-k} = O\!\left( \left(\frac{2e}{n}\right)^n  \max\limits _{k\in [[0,n]] }k^{n-k}\right).$$ Pour obtenir $(\forall r>0,\; r^n \frac{U_{n} }{n!}  \underset{n\rightarrow \infty }{\longrightarrow} 0 )$, il suffit donc de montrer que $\forall r>0,\; r^n \max\limits _{k\in [[0,n]]} \frac{k^{n-k} }{n^{n}} \underset{n\rightarrow \infty }{\longrightarrow} 0$. Or $\frac{k^{n-k} }{n^{n}} = \left( \frac{k}{n} \right)^{n} \frac{1}{k^{k}}$. Faisons deux estimations différentes suivant si $k\leqslant a_{n}$ ou $k>a_{n}$ avec $a_{n}$ à choisir plus tard.
    • Si $k>a_{n}$, on a $\left( \frac{k}{n} \right)^{n} \frac{1}{k^{k}} \leqslant  1 \cdot  \frac{1}{a_n ^{a_n}}$. Or pour que $(\forall r>0,\;   \dfrac{r^{n}}{a_n ^{a_n}} \underset{n\rightarrow \infty }{\longrightarrow} 0)$, il suffit que $\frac{a_{n} \ln (a_{n}) }{n} \rightarrow \infty $. Ça donne envie de poser $a_{n} =n$, mais ce serait un découpage idiot, donc on va plutôt poser $a_{n}$ l'unique solution de $a_{n} \ln (a_n) = n \sqrt{\ln n}$. Ainsi $a_n<n$.
    • Ensuite, si $k\leqslant  a_{n}$, on a $\left( \frac{k}{n} \right)^{n} \frac{1}{k^{k}} \leqslant  \left( \frac{a_{n} }{n} \right)^{n} \cdot 1$. Or en prenant le logarithme de la relation $a_{n} \ln (a_n) = n \sqrt{\ln n}$, on a $\ln  a_{n} \sim \ln  n$. Puis en injectant cet équivalent dans la même relation, on a $a_{n} \sim  \frac{n}{\sqrt{\ln n}}$. Ainsi : $\forall r>0,\; r^{n} \left( \frac{a_{n} }{n} \right)^{n} \leqslant  r^{n} \Big( O\left( \frac{1}{\sqrt{\ln n}} \right)\Big)^{n} \underset{n\rightarrow \infty }{\longrightarrow} 0$. C'est gagné !
  • Modifié (April 2023)
    Pour justifier $U_{n+1}=\sum_{k=0}^{n}\binom{n}{k}(n-k+1)U_{k}$, on peut faire le raisonnement suivant. Choisir une application idempotente $f$ de $[\![1,n+1]\!]$, c'est choisir l'élément $f(n+1)$ puis choisir l'ensemble $A=f^{-1}(\{f(n+1)\})$ des éléments qui ont la même image que $n+1$ ($n+1$ compris) puis choisir la restriction $f_{|B}^{|B}$ où $B :=[\![1,n+1]\!]\setminus A$. En changeant l'ordre des choix, c'est aussi choisir l'ensemble $A'=f^{-1}(\{f(n+1)\})\setminus\{n+1\}$ des éléments qui ont la même image que $n+1$ ($n+1$ exclu), puis choisir l'image de $n+1$ parmi $A'\cup\{n+1\}$, puis choisir $f_{|B}^{|B}$. En notant $j$ le cardinal de $A'$ et $k=n-j$, cela donne $$U_{n+1}=\sum_{j=0}^{n}\binom{n}{j}\, (j+1) \,U_{n-j}= \sum_{k=0}^{n}\binom{n}{k}(n-k+1)U_{k}.$$
  • Modifié (April 2023)
    Merci Calli.
    La démonstration du rayon de convergence rappelle celle qui s'applique aux nombres de Bell $B_n$, mais en plus compliqué. C'est curieux, car on dispose d'une expression pour $U_n$ mais non pour $B_n$. Il y a comme ça des bizarreries en mathématiques...
    Au sujet de la deuxième démonstration, je ne connaissais pas la notation $f_{|B}^{|B}$. Je présume qu'il s'agit, pour ainsi dire, d'une double restriction.
    Maintenant, que dites-vous pour le calcul de  la fonction génératrice exponentielle $\sum_{n=0}^{+ \infty} U_{n}\frac{x^{n}}{n!}$ à partir de la formule $U_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$ ?
    Encore grand merci, et bonne soirée.
    Fr. Ch;
  • $f_{|B} ^{|B} $ n'est peut-être pas une notation universelle. Mon prof de sup' l'utilisait mais c'est vrai que je ne l'ai jamais revue. Le $B$ désigne la restriction (réduction de l'espace de départ) et celui du haut la co-restriction (réduction de l'espace d'arrivée). Mais le 2e est un peu superflu, c'était plus pour insister sur le fait que ma restriction va de $B$ dans $B$. 
  • Modifié (April 2023)
    Curieux de savoir quel est le raisonnement pas trop compliqué qui conduit à l'expression $U_n=\sum_{k=0}^n \binom{n}{k}k^{n-k}$. J'ai essayé de retrouver le résultat et ai raisonné comme ceci : $\phi$ est idempotente si et seulement si son ensemble image est égal à son ensemble des points fixes, donc si et seulement si son graphe est une réunion disjointe de graphes en étoile. Dans cette expression, pour chaque $k\leq n$, le facteur $\binom{n}{k}$ correspond au nombre de manières de choisir un ensemble de points fixes de cardinal $k$, et pour chacun de ces choix le facteur $k^{n-k}$ correspond au nombre de manières d'envoyer les $n-k$ éléments restants vers un point fixe (c'est le cardinal de l'ensemble des fonctions d'un ensemble à $n-k$ élément vers un ensemble à $k$ éléments).
    Après ce que je ne comprends pas, c'est qu'une fonction d'un ensemble fini dans lui-même a forcément au moins un point fixe. Donc j'aurais fait courir la somme de $k=1$ à $n$ au lieu de $k=0$ à $n$.
    Edit : La dernière phrase est mal formulée. Une fonction d'un ensemble fini dans lui-même a forcément un point cyclique, et avec l'hypothèse supplémentaire que la fonction est idempotente, tout point cyclique doit être un point fixe; donc une fonction idempotente a au moins un point fixe.
    Après je bloque.
  • C'est bien le raisonnement que tu fais qui peut être qualifié de façon élémentaire d'établir la relation.
  • Dac, merci JLapin. Mais qu'en est-il de la somme ? De $k=0$ à $n$ ou de $k=1$ à $n$ ?
    Après je bloque.
  • Le terme pour $k=0$ est nul car $0^{n-0}=0$. Donc peu importe. 
  • Modifié (July 2023)
    Voici comment je démontre la formule $U_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$.
    • Lemme. Une application $\phi :E\rightarrow E$ est idempotente si et seulement si : $\forall x\in \phi (E),\phi (x)=x$.
    Désignons par $\left\vert X\right\vert $ le cardinal d'un ensemble fini $X$.
    Soit $E$ un ensemble fini non vide, tel que $\left\vert E\right\vert =n$. Soit une partie non vide $X\subset E$, et soit une application idempotente $\phi :E\rightarrow E$ telle que $\phi (E)=X$. D'après le lemme, on a $\phi (x)=x$ pour tout $x\in X$. L'application $\phi $ est donc déterminée par les images par $\phi $ des éléments du complémentaire $E\backslash X$, et ces images sont éléments de $X$. Le nombre d'applications idempotentes $\phi :E\rightarrow E$ telles que $\phi (E)=X$ est donc le nombre d'applications de $E\backslash X$ dans $X$. Si $\left\vert X\right\vert =k$, ce nombre est $k^{n-k}$.
    Pour chaque $k\in \{1,2,...,n\}$, le nombre de parties $X\subset E$ telles que $\left\vert X\right\vert =k$ est $\binom{n}{k}$. Le nombre d'applications idempotentes $\phi :E\rightarrow E$ telles que $\left\vert \phi (E)\right\vert =k$ est donc : $\binom{n}{k}k^{n-k}$.
    On en conclut que le nombre total d'applications idempotentes $f:E\rightarrow E$ est : $U_{n}=\sum_{k=1}^{n}\binom{n}{k}k^{n-k}$. ou encore $U_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$ puisque $n\in \mathbb{N}^{\ast }$.
    On pose $U_{0}=1$, soit par convention pour prolonger la formule $U_{n}=\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$ (car $0^{0}=1$), soit en observant qu'il y a exactement une application de l'ensemble vide dans lui-même, l'application vide, et que cette application est idempotente.
  • Merci à Calli et Chaurien. Evidemment, ça ne m'avait pas traversé l'esprit que mon pinaillage ne faisait aucune différence...
    Après je bloque.
  • Merci à @Chaurien d'avoir rappelé ce problème intéressant que j'avais rencontré en octobre 2007 puis oublié depuis.

    Les trois propriétés intéressantes peuvent toutes se démontrer assez simplement avec le programme actuel de MPSI-MP.

    La  première $U_{n}=\displaystyle\sum_{k=0}^{n}\binom{n}{k}k^{n-k}$ se démontre par le raisonnement combinatoire détaillé par @Chaurien ci-dessus.

    La seconde $U_{n+1}=\displaystyle\sum_{k=0}^{n}\binom{n}{k}(n-k+1)U_{k}$ se démontre par le raisonnement combinatoire détaillé par Calli au-dessus.

    La troisième $f(x)=\displaystyle\sum_{n=0}^{+\infty}U_{n}\frac{x^{n}}{n!}=e^{xe^{x}}$ découle de la seconde : 
    il est clair que le rayon de convergence est au moins égal à $\dfrac1e$ puisque $U_{n}\dfrac{|x|^{n}}{n!}\leqslant n^n\dfrac{|x|^{n}}{n!}\sim \dfrac{|ex|^n}{\sqrt{2\pi n}}$.
    Ensuite $\dfrac{U_{n+1}}{n!}=\displaystyle\sum_{k=0}^{n}\dfrac{k+1}k\dfrac{U_{n-k}}{(n-k)!}$ entraine avec un produit de Cauchy que $f'(x)=(x+1)e^xf(x)$ d'où avec $f(0)=1$ :  $f(x)=e^{xe^{x}}$.

    J'ai une démonstration différente de celle de @Calli pour démontrer que le rayon de convergence est infini.
    $\forall a>0\;\exists n_0 , n\geqslant n_0\Rightarrow e^a(a+a^2)\leqslant n+1$.
    On choisit $M>0$ telque la propriété ${\cal P}(n):\quad \dfrac{U_n}{n!}\leqslant\dfrac M{a^n}$ soit vérifiée jusqu'à $n_0$.

    Si la propriété est vraie jusqu'à $n\geqslant n_0$ alors :  $\dfrac{U_{n+1}}{(n+1)!}=\dfrac1{n+1}\displaystyle\sum_{k=0}^{n}\dfrac{k+1}{k!}\dfrac{U_{n-k}}{(n-k)!}\leqslant \dfrac M{(n+1)a^n}\sum_{k=0}^{n}\dfrac{k+1}{k!}a^k\leqslant \dfrac M{(n+1)a^n}e^a(1+a)\leqslant \dfrac M{a^{n+1}}$.

    Donc ${\cal P}(n)$ est vraie pour tout $n$ et pour tout $a$ le rayon de convergence est au moins égal à $a$.

  • Modifié (April 2023)
    Je continue à travailler les problèmes en relation avec des collègues restés d'active. Mon attention a été attirée sur cette question du dénombrement des applications idempotentes par le problème d'oral 392, Mines-Ponts MP, dans la RMS 133-2 de février 2023. Et comme je l'ai dit plus haut, j'ai été bien étonné de ne pas m'être intéressé plus tôt à cette question, à vrai dire peu évoquée dans les ouvrages de Combinatoire.
     Le problème de Mines-Ponts ne demandait que l'expression de ce nombre $U_n$, mais j'ai tenu à réfléchir aux autres questions qui se posent naturellement pour un dénombrement de ce type, tout en restant dans le cadre du programme MPSI-MP 2021. Je suis très heureux que mon intérêt ait été partagé par d'autres forumeurs, que je remercie pour leurs contributions.
    La formule de récurrence et la fonction génératrice exponentielle ressemblent à celles des des nombres de Bell $B_n$, ce qui est curieux car on ne voit pas la parenté combinatoire entre les partitions et les applications idempotentes. Pour le rayon de convergence, j'ai trouvé une démonstration qui n'est qu'une adaptation de celle que je connaissais depuis longtemps pour les $B_n$.
    j'ai bricolé un énoncé qui donne la fonction génératrice exponentielle, la formule de récurrence, le rayon de convergence, et je la joins. J'ai adopté la mention fantaisiste « Lycée B 612 » après avoir avoir été remercié grossièrement par le vrai lycée où j'assurais des colles.
    La question qui demeure, c'est l'évaluation asymptotique de ces nombres $U_n$. Pour les $B_n$ ce n'est pas très facile, et il en est de même pour les $U_n$. On trouve la réponse dans la littérature, mais il faut voir si c'est adaptable au niveau MP.
    Bonne journée
    Fr. Ch.
  • Modifié (April 2023)
    jandri a dit :
    J'ai une démonstration différente de celle de @Calli pour démontrer que le rayon de convergence est infini.
    Tu veux dire plus courte plutôt, non ?  :D:)
  • Modifié (April 2023)
    Oui mais @Chaurien a une formulation encore plus courte quand il montre que pour tout $r>0$ la suite $M_n(r)=\displaystyle\max_{0\leqslant k\leqslant n}\dfrac{U_kr^k}{k!}$ est stationnaire donc bornée.
  • C'est vrai que c'est une bonne façon de formuler la preuve. 👍
  • MrJMrJ
    Modifié (July 2023)
    @Chaurien : la théorie des familles sommables n’implique-t-elle pas directement que le rayon de convergence est infini ? De toute manière, si $x\geq 0$, les termes de la famille sont positifs.
  • Modifié (July 2023)
    MrJ, je ne comprends pas en quoi la théorie des familles sommables peut donner ici le rayon de convergence, mais il est possible que je ne maîtrise pas suffisamment cette théorie.
  • MrJMrJ
    Modifié (July 2023)
    Soit $x\geq 0$. Comme tous les termes de la famille sont positifs, on peut effectuer le calcul dans $\R\cup\{+\infty\}$ :
    $$\sum_{n=0}^{+\infty} U_n \dfrac{x^n}{n!} = \sum_{n=0}^{+\infty} U_n \dfrac{x^n}{n!} = \sum_{n=0}^{+\infty} \sum_{k=0}^n \binom{n}{k}k^{n-k} \dfrac{x^n}{n!} = \sum_{k=0}^{+\infty} \sum_{n=k}^{+\infty} \binom{n}{k}k^{n-k} \dfrac{x^n}{n!} = \sum_{k=0}^{+\infty} \dfrac{x^k}{k!} \sum_{n=k}^{+\infty} \dfrac{(kx)^{n-k}}{(n-k)!} = \sum_{k=0}^{+\infty} \dfrac{x^k}{k!} \textrm{e}^{k x} = \textrm{e}^{x\textrm{e}^x} < +\infty.$$
    On conclut que la série $\displaystyle{\sum_{n=0}^{+\infty} U_n \dfrac{x^n}{n!}}$ converge pour tout $x\geq 0$, donc son rayon de convergence est $+\infty$.






  • Modifié (July 2023)
    Bon, peut-être, mais je n'aime pas calculer avec $+\infty$. Je ne suis pas à l'aise avec ça. J’aimerais les énoncés précis des théorèmes qui autorisent de telles acrobaties.
  • Modifié (July 2023)
    C'est le théorème de sommation par paquets.
    https://perso.eleves.ens-rennes.fr/~dcaci409/Kholle 12 MP1corrige
  • MrJMrJ
    Modifié (July 2023)
    C’est l’intérêt pratique de la notion de famille sommable : si tous les termes sont positifs, on peut effectuer les calculs dans $\R\cup\{+\infty\}$ en utilisant le théorème de sommation par paquets.
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!