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}.
Calculer {S_{n,p}} si {p>n}.
Question 2.
Calculer {S_{n,n}}, {S_{n,1}}, et {S_{n,2}}.
Calculer {S_{n,n}}, {S_{n,1}}, et {S_{n,2}}.
Question 3.
Calculer {S_{p+1,p}}.
On suppose désormais que {0\lt p\leq n}.
Calculer {S_{p+1,p}}.
Question 4.
Montrer que {\displaystyle\sum_{k=0}^p(-1)^k\dbinom pk=0}
Montrer que {\displaystyle\sum_{k=0}^p(-1)^k\dbinom pk=0}
Question 5.
Montrer l’implication : {0\leq k\leq q\leq p\Rightarrow\dbinom pq\dbinom qk =\dbinom pk\dbinom{p-k}{q-k}}
Montrer l’implication : {0\leq k\leq q\leq p\Rightarrow\dbinom pq\dbinom qk =\dbinom pk\dbinom{p-k}{q-k}}
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}?)
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}?)
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}}.
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}}.
Question 8.
En déduire que {p^n=\displaystyle\sum_{q=1}^p\dbinom pq S_{n,q}}.
En déduire que {p^n=\displaystyle\sum_{q=1}^p\dbinom pq S_{n,q}}.
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 :
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}
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 :
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
Question 11.
Retrouver la valeur de {S_{p+1,p}}, puis montrer que :{S_{p+2,p}=\dfrac{p(3p+1)}{24}(p+2)!}
Retrouver la valeur de {S_{p+1,p}}, puis montrer que :{S_{p+2,p}=\dfrac{p(3p+1)}{24}(p+2)!}
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}.
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}.