Licence 1 Mathématiques  Université Rennes 1 Matthieu Romagny, 25 novembre 201

Licence 1 Mathématiques  Université Rennes 1 Matthieu Romagny, 25 novembre 2016 Algèbre et Arithmétique 1 Corrigé des exercices 3, 5, 8, 16, 17, 18 de la feuille de TD no 4 Exercice 3. Corrigé. 1. Notons C l'ensemble à 8 éléments formé par les 8 élèves de la classe. La question posée est de compter le nombre de manière d'écrire C = A ∪B avec A et B deux ensembles à 4 éléments. (On peut noter que A et B forment une partition de C.) Le nombre de choix possibles pour A est égal à 8 4  = 8! 4!4! = (8.7.6.5)/(4.3.2.1) = 70. Une fois choisie A, on n'a plus de choix possible pour la partie B qui doit nécessairement être égale à C ∖A. Dans cette manière de compter, on a ordonné les parties A ( la première ) et B ( la seconde ) alors qu'en réalité elles ne le sont pas ; dit autrement, le choix de la partie A et de la partie C ∖A donnent lieu à la même partition de C en deux groupes de 4. Il faut donc diviser par 2 le nombre précédent pour obtenir la réponse à la question, qui est donc 70/2 = 35. 2. Soit n le nombre d'éléments de S. L'énoncé nous dit que n 3  = 364, c'est-à-dire n(n−1)(n−2) 6 = 364 ou encore n(n −1)(n −2) = 2184. Notons E l'ensemble des entiers naturels supérieurs ou égaux à 3. La fonction f : E →E dé nie par f(n) = n(n −1)(n −2) est strictement croissante car si n′ > n ⩾3, on a n′−1 > n−1 ⩾2 et n′−2 > n−2 ⩾1, donc en multipliant ces trois quantités on trouve f(n′) > f(n) ⩾6. On en déduit que f est injective. Donc s'il existe un entier n ⩾3 solution de l'équation f(n) = 2184, alors celui-ci est unique. Comme f(n) est de l'ordre de n3, en calculant 3 √ 2184 on voit que n doit être proche de 13 ou 14. En prenant n = 14 on voit qu'on gagne : f(14) = 2184. Donc nalement card(S) = 14. Exercice 5. Corrigé. 1. On calcule : n −1 p −1  + n −1 p  = (n −1)! (p −1)!(n −p)!+ (n −1)! p!(n −1 −p)! = p × (n −1)! + (n −p)(n −1)! p!(n −p)! = n × (n −1)! p!(n −p)! = n! p!(n −p)!. 2. Voir le cours. Exercice 8. Corrigé. 1. Je vous laisse la joie du calcul... 2. Soit E un ensemble ni de cardinal n. Comme n ⩾2, on peut choisir deux éléments a et b dans E. Nous allons dénombrer l'ensemble P2(E) des parties à p éléments de E. On sait d'après le cours qu'il est de cardinal n p  . On peut également dénombrer P2(E) en le partitionnant de la manière suivante. Pour toute partie A ⊂E, on peut dire que : 1) soit A contient a et b ; on notera Q1 l'ensemble de ces parties, 2) soit A contient a mais pas b ; on notera Q3 l'ensemble de ces parties, 3) soit A contient b mais pas a ; on notera Q3 l'ensemble de ces parties, 4) soit A ne contient ni a ni b ; on notera Q4 l'ensemble de ces parties. Les parties A ∈Q1 sont en bijection avec les parties A ∖{a, b} de cardinal p −2 dans l'ensemble E ∖{a, b} qui est de cardinal n −2 ; il y en a n−2 p−2  . Les parties A ∈Q2 sont en bijection avec les parties A ∖{a} de cardinal p −1 dans l'ensemble E ∖{a, b} qui est de cardinal n −2 ; il y en a n−2 p−1  . Le même décompte est valable pour les parties de Q3. En n les parties A ∈Q4 sont en bijection avec les parties A de cardinal p dans l'ensemble E ∖{a, b} qui est de cardinal n −2 ; il y en a n−2 p  . Finalement n p  = card P2(E) = P4 i=1 card(Qi) = n−2 p−2  + 2 n−2 p−1  + n−2 p  . Exercice 16. Corrigé. 1. Je vous laisse la joie de la récurrence... 2.a. Pour une partie A quelconque dont on note m le plus grand élément, si m ⩽p, alors la partie A est incluse dans {1, . . . , p} donc son cardinal est inférieur ou égal à p. Par contraposée, si card(A) = p+1 > p, alors le plus grand élément m est ⩾p + 1. Il est donc compris entre p + 1 et m + 1. 2.b. Notons a1 < a2 < · · · < ap < ap+1 les p + 1 éléments de A, une fois ordonnés. Les parties A dont le plus grand élément ap+1 est xé égal à m sont déterminées par le choix des p éléments a1, a2, . . . , ap qui appartiennent à {1, . . . , m −1}. (Plus formellement, on peut formuler cet argument en disant qu'on a une bijection f entre l'ensemble des parties A ⊂E ayant p + 1 éléments et dont le plus grand élément est m, et l'ensemble des parties A′ ⊂{1, . . . , m −1} ayant p éléments, donnée par f(A) = A ∖{m}. Sa bijection réciproque g est donnée par g(A′) = A′ ∪{m}.) Le nombre de telles parties A′ = {a1, a2, . . . , ap} est m−1 p  . 2.c. Notons P := Pp+1(E) l'ensemble des parties à p + 1 éléments de E. On sait d'après le cours que card(P) = n+1 p+1  . Pour chaque m ∈{p + 1, . . . , n + 1} notons Pm l'ensemble des parties A comme ci- dessus dont le plus grand élément est m. On a calculé dans la question b que card(Pm) = m−1 p  . D'après la question a, chaque partie A possède un plus grand élément m ∈{p + 1, . . . , n + 1} donc les parties Pp+1, . . . , Pn+1 recouvrent P, c'est-à-dire que leur réunion est égale à P. Comme chaque partie ne possède qu'un seul plus grand élément, les parties Pm sont toutes disjointes deux à deux. On peut donc écrire P = Pp+1 ⨿· · ·⨿Pn+1. En utilisant la formule qui donne le cardinal d'un ensemble qui est exprimé comme une réunion disjointe de parties, on trouve : n + 1 p + 1  = card(P) = n+1 X m=p+1 m −1 p  . En faisant le changement d'indices k = m −1 on obtient n+1 p+1  = n X k=p k p  . Remarque : nous avons vu dans le cours que si {A1, . . . , An} est une partition de E, alors card(E) = card(A1) + · · · + card(An). Les parties Ai d'une partition sont par dé nition non vides, mais plus généra- lement, si E est recouvert par des parties disjointes A1, . . . , An dont certaines sont éventuellement vides, alors cette formule est encore valable. Exercice 17. Corrigé. Avertissement : exercice di cile ! Nous n'avons pas vu en cours le terme permutation. Voici donc sa dé nition : pour les ensembles nis, une permutation est simplement une bijection. Cette terminologie est utilisée surtout (si ce n'est exclusivement) pour les ensembles nis. Pour une permutation f : {1, . . . , n} →{1, . . . , n}, un point xe est un i ∈{1, . . . , n} tel que f(i) = i. Par exemple, pour n = 3 voici deux permutations f et g : f est dé nie par f(1) = 3, f(2) = 2 et f(3) = 1 et g est dé nie par g(1) = 2, g(2) = 3 et g(3) = 1. La permutation f possède donc un point xe, qui est i = 2, alors que la permutation g ne possède aucun point xe. Parmi les permutations de {1, . . . , n}, la seule qui possède n points xes est l'identité. Par ailleurs, il convient de corriger un peu la terminologie de l'exercice : classiquement, ce qu'on appelle dérangement est une permutation qui ne possède aucun point xe. Lorsque k ⩾1, les permutations ayant k points xes sont plutôt appelées... permutations ayant k points xes. 1. Notons E = {1, . . . , n} et P = Bij(E) l'ensemble des permutations de E. On sait que card(P) = n! (formule pour le cardinal de l'ensemble des bijections d'un ensemble ni). Pour tout k ∈ {0, . . . , n}, notons Ak l'ensemble des permutations de E qui possèdent exactement k points xes : l'énoncé nous dit que Dn,k = card(Ak). L'observation utile pour l'exercice est que {A0, A1, . . . , An} forme une partition de P, puisque chaque permutation uploads/s3/ corrige-feuille-4 1 .pdf

Tags
Administrationl'ensemble parties cardinal éléments alors
Documents similaires
  • 27
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager