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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).
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 : Mathprepa.fr est le site des mathématiques et de l'informatique des deux années des classes prépa scientifiques: plus de 2500 exercices et 200 problèmes (soigneusement corrigés), un cours complet (maths et info), plus de 400 sujets de concours, etc. Un contenu sans équivalent, dans une présentation fluide et professionnelle adaptée à tous les écrans, pour une souscription de 15€ (six mois), 25€ (un an) ou 35€ (deux ans).