Débombrements d’applications

Exercice 1.
Combien y a-t-il de surjections de {E} vers {F} si {\text{card}(E)=n+1} et {\text{card}(F)=n}?
Même question avec {\text{card}(E)=n+2} et avec {\text{card}(E)=n+3}.
Cliquer ici pour voir (ou cacher) le corrigé
Dans tout cet exercice, et pour tout entier {m\ge1}, on note {E_m=\{1,\ldots,m\}}.

  1. Pour construire une surjection {f} de {E_{n+1}} vers {E_n}, il faut :

    • Choisir l’élément {y} de {E_n} qui va posséder deux antécédents.
    • Choisir la paire {\{a,b\}} des antécédents de {y} dans {E_{n+1}}.
    • Mettre en bijection les {n-1} éléments de {E_{n+1}\setminus\{a,b\}} et ceux de {E_n\setminus\{y\}}.

    Le nombre de surjections de {E_{n+1}} dans {E_n} est donc : {n\dbinom{n+1}{2}(n-1)!=\dfrac{n}{2}(n+1)!}

  2. Soit {f} une surjection de {E_{n+2}} sur {E_n}.

    Deux cas sont possibles qui s’excluent mutuellement :

    • Premier cas :

      Il existe {y\in E_{n}} possédant {3} antécédents distincts {a,b,c}.

      Il y a {n} manières de choisir {y}, puis {\dbinom{n+2}{3}} manières de choisir {\{a,b,c\}}.

      Il y a ensuite {(n-1)!} bijections de {E_{n+2}\setminus\{a,b,c\}} sur {E_{n}\setminus\{y\}}.

      Le nombre de solutions dans ce premier cas est donc : {n\dbinom{n+2}{3}(n-1)!=\dfrac{n}{6}(n+2)!}

    • Deuxième cas :

      Il existe deux éléments distincts {y,z} de {E_n}, ayant chacun deux antécédents.

      Supposons par exemple {y\lt z} pour éviter de compter une même solution deux fois.

      Il y a {\dbinom{n}{2}} manières de choisir le couple {(y,z)}.

      Il y a ensuite {\dbinom{n+2}{2}} manières de choisir les antécédents {a,b} de {y}.

      Puis il y a {\dbinom{n}{2}} manières de choisir les antécédents {c,d} de {z}, dans {E_{n+2}\setminus\{a,b\}}.

      Il y a enfin {(n-2)!} bijections entre {E_{n+2}\setminus\{a,b,c,d\}} et {E_n\setminus\{y,z\}}.

      Dans ce second cas, le nombre de solutions est donc : {\dbinom{n}{2}\dbinom{n+2}{2}\dbinom{n}{2}(n-2)!=\dfrac{n(n-1)}{8}\,(n+2)!}

    • Finalement, le nombre de surjections de {E_{n+2}} sur {E_{n}} est :{\begin{array}{rl}\dfrac{n}{6}(n+2)!+\dfrac{n(n-1)}{8}(n+2)!&=\dfrac{(n+2)!}{24}(3n(n-1)+4n)\\\\&=\dfrac{n(3n+1)}{24}(n+2)!\end{array}}
  3. Soit {f} une surjection de {E_{n+3}} sur {E_n}.

    Trois cas sont possibles qui s’excluent mutuellement.

    • Premier cas :

      Il existe un élément {y} de {E_n} ayant quatre antécédents distincts.

      On choisit {y}, puis ses quatre antécédents, puis on met en bijection les {n-1} éléments restant de part et d’autre.

      Il y a {n\dbinom{n+3}{4}(n-1)!=n\,\dfrac{(n+3)!}{4!}} possibilités distinctes.

    • Deuxième cas :

      Il existe un élément {y} ayant trois antécédents et un autre élément {z} ayant deux antécédents.

      Il faut choisir {y}, puis ses trois antécédents parmi {n+3}, puis {z} dans {E_n-\{y\}} puis les deux antécédents de {z} parmi les {n} éléments encore disponibles.

      Il reste enfin à mettre en bijection les {n-2} éléments restant de part et d’autre.

      Le nombre de possibilités distinctes est : {n(n-1)\dbinom{n+3}{3}\dbinom{n}{2}(n-2)!=\dfrac{n(n-1)}{12}(n+3)!}

    • Troisième cas :

      Il existe trois éléments {y,z,t} de {E_n} ayant chacun deux antécédents.

      Supposons {y\lt z\lt t} pour éviter de compter plusieurs fois une même solution.

      Il y a {\dbinom{n}{3}} manières de choisir {\{y,z,t\}} dans {E_n}.

      Il faut ensuite choisir les deux antécédents de {y} parmi {n+3}, puis ceux de {z} parmi {n+1} puis ceux de {t} parmi {n-1}, avant de mettre en bijection les {n-3} éléments restant de part et d’autre. Le nombre de possibilités distinctes est donc : {\begin{array}{l}\dbinom{n}{3}\dbinom{n+3}{2}\dbinom{n+1}{2}\dbinom{n-1}{2}(n-3)!\\\\\quad=\dfrac{n(n-1)(n-2)}{48}\,(n+3)!\end{array}}

    • Finalement, le nombre de surjections de {E_{n+3}} sur {E_{n}} est :
      {n\left(\dfrac{1}{24}+\dfrac{n-1}{12}+\dfrac{(n-1)(n-2)}{48}\right)(n+3)!=\dfrac{n^2(n+1)}{48}(n+3)!}
    • Il faut avoir la présence d’esprit de vérifier pour des valeurs simples de {n}.

      Par exemple, avec {n=1} on trouve une seule solution (il n’y a qu’une application de {E_4} dans {E_1} et elle est surjective!)

      Pour {n=2}, on trouve la valeur {30} : il y a en effet {2^5=32} applications de {E_5} dans {E_2}, et il faut éliminer les deux applications constantes qui sont les seules à ne pas être surjectives.

Exercice 2.
Soit {E_p} un ensemble de cardinal {p}.
Soit {{\mathcal F}_{p,n}} l’ensemble des applications {f:E_p\rightarrow\mathbb{N}} telles que { \displaystyle\sum_{x\in E}f(x)\le n}.
Montrer que le cardinal de {{\mathcal F}_{p,n}} est {\dbinom{n+p}p} (donner deux démonstrations).
Cliquer ici pour voir (ou cacher) le corrigé
Pour simplifier les notations, on note {E_p=\{1,\ldots,p\}}.

Ainsi {{\mathcal F}_{p,n}} est l’ensemble des {f:E_p\rightarrow\mathbb{N}} telles que {f(1)+f(2)+\cdots+f(p)\le n}.

Notons {\lambda_{p,n}} le cardinal de {{\mathcal F}_{p,n}}.

L’énoncé demande donc de prouver que: {\forall p\in\mathbb{N}^*,\;\forall n\in\mathbb{N},\;\lambda_{p,n}=\dbinom{n+p}{p}}.

  • Première méthode :

    On prouve le résultat par récurrence sur {p}.

    C’est vrai si {p=1} car {\lambda_{1,n}=n+1} (solutions définies par {f(1)=k\in\{0\le k\le n\}}).

    Soit {p} un entier {\ge2}.

    On suppose la propriété vraie pour les {k\in\{0,\ldots,p-1\}} (et tous les entiers {n}).

    Soit {f} une application de {E_{p+1}} dans {\mathbb{N}}.

    Dire que {f\in{\mathcal F}_{p+1,n}} c’est écrire : {f(1)+\cdots+f(p)\le n-f(p+1)}.

    On discute suivant la valeur de {k=n-f(p+1)} dans {\{0,\ldots,n\}}.

    On constate donc que {\lambda_{p+1,n}= \displaystyle\sum_{k=0}^{n}\lambda_{p,k}}.

    Compte tenu de l’hypothèse de récurrence, on trouve : {\begin{array}{rl}\lambda_{p+1,n}&= \displaystyle\sum_{k=0}^{n}\dbinom{k+p}{p}=1+ \displaystyle\sum_{k=1}^{n}\dbinom{k+p}{p}\\\\&=1+ \displaystyle\sum_{k=1}^{n}\left(\dbinom{k+p+1}{p+1}-\dbinom{k+p}{p+1}\right)\\\\&=1+ \displaystyle\sum_{k=2}^{n+1}\dbinom{k+p}{p+1}- \displaystyle\sum_{k=1}^{n}\dbinom{k+p}{p+1}\\\\&=1+\dbinom{n+p+1}{p+1}-\dbinom{p+1}{p+1}=\dbinom{n+p+1}{p+1}\end{array}}Ce qui démontre la propriété au rang {p+1} et achève la récurrence.

  • Deuxième méthode :

    À toute application {f:E_p\rightarrow\mathbb{N}} on associe {g:E_p\rightarrow\mathbb{N}^*} définie par : {\forall k\in\{1,\ldots,p\},g(k)=f(1)+f(2)+\cdots+f(k)+k}L’application {g} est strictement croissante.

    En effet : {\forall k\in\{2,\ldots,p\}, g(k)-g(k-1)=f(k)+1>0}.

    Réciproquement, soit {g} strictement croissante de {E_p} dans {\mathbb{N}^*}.

    Alors {g} est l’image (au sens de la correspondance précédente) d’une unique application {f} de {E_p} dans {\mathbb{N}}, et cette application est définie par {f(1)=g(1)-1} et par : {\forall k\in\{2,\ldots,p\},\;f(k)=g(k)-g(k-1)-1}Par construction on a bien sûr {g(p)=f(1)+f(2)+\ldots+f(p)+p}.

    La condition {f(1)+f(2)+\ldots+f(p)\le n} équivaut donc à {g(p)\le n+p}.

    Cette correspondance bijective montre donc qu’il y a autant d’éléments dans {{\mathcal F}_{p,n}} qu’il y a d’applications strictement croissantes de {E_p} dans {E_{n+p}}.

    Or une application strictement croissante de {E_p} dans {E_{n+p}} est déterminée de manière unique par son ensemble image, c’est-à-dire par une partie quelconque à {p} éléments de {E_{n+p}}.

    Il y a donc {\dbinom{n+p}{p}} solutions distinctes, ce qui achève la démonstration.

Exercice 3.
Soit {E} un ensemble à {n} éléments. Déterminer le nombre de relations sur {E}, de relations réflexives sur {E}, de relations symétriques sur {E}, puis enfin de relations réflexives et symétriques sur {E}.
Cliquer ici pour voir (ou cacher) le corrigé

  1. Une relation sur {E} est une partie de {E\times E}, et {\text{card}(E\times E)=n^2}.

    Le nombre de relations sur {E} est donc {2^{n^2}}.

  2. On note {\Delta=\{(x,x),x\in E\}} la “diagonale” de {E\times E}.

    Une relation réflexive sur {E} est une partie de {E\times E} qui contient {\Delta}.

    Choisir une telle relation, c’est en fait choisir une partie de {(E\times E)\setminus\Delta}.

    Cet ensemble est de cardinal {n^2-n}. Il y a donc {2^{n^2-n}} relations réflexives sur {E}.

  3. Posons {E=\{1,2,\ldots,n\}} pour fixer les idées.

    Une relation symétrique sur {E} est une partie {G} de {E\times E} telle que : {(x,y)\in G\Leftrightarrow(y,x)\in G}La partie {G} est déterminée par son intersection avec {\Delta^+=\{(x,y)\in E\times E, x\le y\}}.

    D’autre part : {\text{card}(\Delta^{+})=\dfrac12{n(n+1)}}.

    Il y a donc {2^{n(n+1)}/2} relations symétriques sur {E}.

  4. Une relation réflexive et symétrique est déterminée de façon unique par son intersection avec : {\Delta^{++}=\{(x,y)\in E\times E, x\lt y\}} dont le cardinal est {\dfrac12{n(n-1)}}.

    Il y a donc {2^{n(n-1)}/2} relations réflexives et symétriques sur {E}.