Surjections entre ensembles finis

Pour tout {n} de {\mathbb{N}^*}, on note {E_n=\{1,2,\ldots,n\}}.

On note {S_{n,p}} le nombre de surjections de {E_n} sur {E_p}.

Question 1.
Calculer {S_{n,p}} si {p>n}.
Cliquer ici pour voir (ou cacher) la réponse
On sait que si {p>n} il n’y a pas de surjection de {E_n} sur {E_p}, donc {S_{n,p}=0}.
Question 2.
Calculer {S_{n,n}}, {S_{n,1}}, et {S_{n,2}}.
Cliquer ici pour voir (ou cacher) la réponse

  • Toute application de {E_n} dans {E_n} est surjective si et seulement si elle est bijective.
    Or il y a {n!} bijections de {E_n} sur lui-même.
    On a donc {S_{n,n}=n!}
  • Il n’y a qu’une application de {E_n} dans {E_1}, et elle est surjective. Donc {S_{n,1}=1}.
  • Il y a {2^n} applications de {E_n} dans {E_2}
    Parmi elles, deux seulement sont non surjectives (les applications constantes).
    Autrement dit {S_{n,2}=2^n-2}.

Question 3.
Calculer {S_{p+1,p}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
On suppose désormais que {0\lt p\leq n}.

Question 4.
Montrer que {\displaystyle\sum_{k=0}^p(-1)^k\dbinom pk=0}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 5.
Montrer l’implication : {0\leq k\leq q\leq p\Rightarrow\dbinom pq\dbinom qk =\dbinom pk\dbinom{p-k}{q-k}}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 6.
En déduire que, si {0\leq k\lt p}, alors : {\displaystyle\sum_{q=k}^p(-1)^q\dbinom pq\dbinom qk=0}(et si {k=p}?)
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 7.
Montrer que pour tout entier {q} de {\{1,2,\ldots,p\}} le nombre d’applications de {E_n} dans {E_p} ayant un ensemble image à {q} éléments est {\dbinom pqS_{n,q}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 8.
En déduire que {p^n=\displaystyle\sum_{q=1}^p\dbinom pq S_{n,q}}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 9.
En utilisant ce qui précède, montrer que : {S_{n,p}=(-1)^p\displaystyle\sum_{k=1}^p(-1)^k\dbinom pk k^n}Indication :

  • Transformer le second membre à l’aide de la question précédente.
  • Justifier l’égalité {\displaystyle\sum_{k=1}^p\,\displaystyle\sum_{q=1}^k\cdots=\displaystyle\sum_{q=1}^p\,\displaystyle\sum_{k=q}^p\cdots}

Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 10.
Montrer que si {0\lt p\leq n-1}, alors :{S_{n,p}=p(S_{n-1,p}+S_{n-1,p-1})}Indication :

  • Étant donné une surjection {\varphi} de {E_n} sur {E_p}, considérer sa restriction {\varphi_1} à {E_{n-1}}.
  • Distinguer deux cas suivant que {\varphi_1} est ou n’est pas surjective

Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 11.
Retrouver la valeur de {S_{p+1,p}}, puis montrer que :{S_{p+2,p}=\dfrac{p(3p+1)}{24}(p+2)!}
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :
Question 12.
En s’inspirant du triangle de Pascal, montrer qu’on peut construire une table des {S_{n,p}}.
Construire cette table pour {0\lt p\leq n\leq7}.
Cliquer ici pour voir (ou cacher) la réponse
Pour voir la suite de ce contenu, vous devez : Pour poursuivre votre exploration, vous pouvez :