Probl`emes de Math´ematiques Nombre de surjections entre ensembles finis ´Enonc´e Nombre de surjections entre ensembles finis Pour tout n de IN∗, on note En = {1, 2, . . . , n}. On note Sn,p le nombre de surjections de En sur Ep. 1. Calculer Sn,p si p > n. [ S ] 2. Calculer Sn,n, Sn,1, et Sn,2. [ S ] 3. Calculer Sp+1,p. [ S ] On suppose d´esormais que 0 < p ≤ n. 4. Montrer que p� k=0 (−1)kC k p = 0 [ S ] 5. Montrer que 0 ≤ k ≤ q ≤ p ⇒ C q p C k q = C k p C q−k p−k . [ S ] 6. En d´eduire que, si 0 ≤ k < p, alors p� q=k (−1)qC q p C k q = 0 (et si k = p ?). [ S ] 7. Montrer que pour tout entier q de {1, 2, . . . , p} le nombre d’applications de En dans Ep ayant un ensemble image `a q ´el´ements est ´egal `a C q p Sn,q. [ S ] 8. En d´eduire que pn = p� q=1C q p Sn,q. [ S ] 9. En utilisant ce qui pr´ec`ede, montrer que : Sn,p = (−1)p p� k=1 (−1)kC k p kn. Indication : – Transformer le second membre `a l’aide de la question pr´ec´edente. – Justifier l’´egalit´e p� k=1 k� q=1 · · · = p� q=1 p� k=q · · · [ S ] 10. Montrer que si 0 < p ≤ n − 1, alors Sn,p = p(Sn−1,p + Sn−1,p−1). Indication : – ´Etant donn´e une surjection ϕ de En sur Ep, consid´er sa restriction ϕ1 `a En−1. – Distinguer deux cas suivant que ϕ1 est ou n’est pas surjective [ S ] 11. Retrouver la valeur de Sp+1,p, puis montrer que Sp+2,p = p(3p+1) 24 (p + 2)!. [ S ] 12. En s’inspirant du triangle de Pascal, montrer qu’on peut construire une table des Sn,p. Construire cette table pour 0 < p ≤ n ≤ 7. [ S ] Page 1 Jean-Michel Ferrard www.klubprepa.net c⃝EduKlub S.A. Tous droits de l’auteur des œuvres r´eserv´es. Sauf autorisation, la reproduction ainsi que toute utilisation des œuvres autre que la consultation individuelle et priv´ee sont interdites.