Probl`emes de Math´ematiques Partitions d’un ensemble fini, surjections, involutions ´Enonc´e Partitions d’un ensemble fini, surjections, involutions Soit E un ensemble fini non vide. Pour tout entier k, on dit que {A1, . . . , Ak} est une partition de E en k classes si : k� i=1 Ai = E; ∀i, Ai ̸= ∅; ∀i, j (avec i ̸= j), Ai ∩ Aj = ∅ Partie I Dans cette partie, on suppose que Card(E) = n. On note r(n) le nombre de partitions de E. On note r(0) = 1. Pour tout k ≥ 1, on note r(n, k) le nombre de partitions de E en k classes. 1. Montrer que : ∀ k, n ∈ IN∗, k > n ⇒ r(n, k) = 0. [ S ] 2. Montrer que : ∀ n ∈ IN∗, r(n) = n � k=1 r(n, k). [ S ] 3. Montrer que : ∀ n ∈ IN, r(n + 1) = n � k=0 C k n r(k). [ S ] 4. Calculer r(n) pour n ∈ {1, 2, 3, 4, 5, 6}. [ S ] 5. Montrer que : ∀ n ≥ 5, r(n) ≥ 2n et ∀ n ∈ IN∗, r(n) ≤ nn. [ S ] 6. Dans cette question, on note Sk n le nombre de surjections d’un ensemble `a n ´el´ements sur un ensemble `a k ´el´ements. Montrer que : ∀ k, n ∈ IN∗, Sk n = k!r(n, k). [ S ] Partie II On suppose que Card(E) = 2m, avec m ≥ 1. On note am le nombre de partitions de E en m classes qui sont des paires. 1. D´eterminer a1, a2, a3. Par convention, on pose a0 = 1. [ S ] 2. Montrer que : ∀ m ∈ IN∗, am = (2m − 1)am−1. [ S ] 3. En d´eduire am = (2m)! 2mm!. [ 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.