Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Université de Batna 2 Module : élément de combinatoire Faculté des Mathématique

Université de Batna 2 Module : élément de combinatoire Faculté des Mathématiques et de l’Informatique Master 1CS Département d’Informatique 2020/2021 Préparer par Dr K.DJEBAILI Page 1 T TD D n n° °0 01 1 Combinatoire énumérative (Corrigé type) Exercice 1 (le principe de recollement (Théorème 2.1) 1. Supposons f et g injectives et soit x et x’ des éléments de E ∪ E’, tels que h(x) = h(x’). Si x appartient à E et x’ appartient à E’, on a h(x) = f(x), qui appartient à F et h(x’) = g(x’), qui appartient à F’ . La condition h(x) = h(x’ ) est alors contradictoire avec F et F’ disjoints. Si x et x’ appartiennent à E, on a f(x) = f(x‘) et si x et x’ appartiennent à E’, on a g(x) = g(x’ ). Dans les deux cas, on obtient x = x’. On a ainsi prouvé que l'application h est injective. Réciproquement, supposons h injective et soit x et x’ des éléments de E, tels que f(x) = f(x’). On a alors h(x) = h(x’), donc x = x’ . On a ainsi prouvé que l'application f est injective. On montre de même que l'application g est injective. 2. h surjective ←f et g surjectives f et g surjectives→im f=F et im g=F’→imf∪img=F∪F’ ……..1 im h=im f∪im g……….2 1et2→imh=F∪F′ → h surjective Réciproquement: h surjective →f et g surjectives. h surjective → imh=F∪F’ …….1 im h=im f∪im g……….2 1et 2 F∪F’= im f∪im g→ F=im f et F’=im g→f et g surjectives. 3. découle de 1) et 2). Exercice 2 (Injective, bijective) On considère 4 ensembles A ,B, C, et D et des application :A→B, g:B→C et h:C→D. • Première implication : soit (a,b) ∈ A2 si f(a)=f(b), alors g◦f(a)=g◦f(b)(car g est une application), et puisque g◦f est injective, on en déduit a=b ce qui signifier que f injective. • Deuxième implication : soit y∈C. Puisque g◦f est surjective, il existe a∈A avec g◦f(a)=y. Posons que b=f(a), on a alors g(b)=y, ce qui prouve que g et surjective. Exercice 3 (Relation d'équivalence) La relation est • Réflexive car x+x=2x est pair. • Symétrique car x+y=y+x et donc si x+y est pair donc y+x est pair. • Transitive car si xℛy et yℛz, alors x+y=2k et y+z=2l pour deux entiers ket l. Si on effectue la somme des ces deux égalités on trouve x+z+2y=2k+2l=x+z=2(k+l-y) et donc x+z est pair. Université de Batna 2 Module : élément de combinatoire Faculté des Mathématiques et de l’Informatique Master 1CS Département d’Informatique 2020/2021 Préparer par Dr K.DJEBAILI Page 2 Pour déterminer la classe d’équivalence de ℛ, il suffit de trouver une famille d’ensemble (Ei) tel que : • La réunion de Ei est ℤ. • Les Ei sont deux à deux disjoints. • Si x et y sont dans le même Ei , alors xℛy. • Si x est dans Ei et y dans Ej avec i≠j, alors x n’est pas en relation avec y. Ici, on peut constater que tous les éléments en relation avec 0 sont les entiers pairs, tandis que tous les entiers en relation avec 1 sont les entiers impairs. Puisque l’ensemble des entiers pairs et l’ensemble des entiers impairs forme une partition de ℤ, on en déduit que ces deux ensembles sont exactement les deux classes d’équivalence de ℤ. Exercice 4 (Relation d’ordre) • Soit A∈ P(E), comme A=A, AℛA la relation est réflexive. • Soit(A,B) ∈ P(E)2 On suppose que AℛB et BℛA Si l’on avait A≠B, on aurait x∈ A⋂B ̅ et x ∈ B⋂A ̅ , donc on aurait x∈ A⋂A ̅ , ce qui impossible on a donc prouvé que A=B. La relation est antisymétrique. • Soit (A,B,C) ∈P(E)3 On suppose que AℛB et BℛC - Si A=B et B=C alors A=C , donc AℛC. - Si A=B et x ∈ B⋂C ̅ alors x∈ A⋂C ̅ donc AℛC. - Si x ∈ A⋂B ̅ et B=C alors x∈ A⋂C ̅ donc AℛC. - Les conditions x∈ A⋂B ̅ et x∈ B⋂C ̅ sont incompatible car elles donnent x∈ B et x ∉B. Par disjonction des cas ; on a prouvé que AℛC. La relation est transitive. Exercice 5 (Ensembles dénombrables) 1. Oui, car c’est une partie de ℕ ou bien l’application n↦2n est une bijection de ℕ sur cet ensemble : ℕ ↦E n↦2n 2. Non, car ℝ ne l'est pas et cet ensemble contient ℝ. Plus précisément, l'application x↦(0,x) est une injection de ℝ dans ℕ× ℝ . 3. Oui, car l'application ϕ:(a,b)↦a+b√2 est une surjection (et même une bijection car √2 est irrationnel) de ℚ2 dans ℚ [√2]. 4. Oui, car c’est une partie de ℕ. 5. Non, car il contientℝ. Université de Batna 2 Module : élément de combinatoire Faculté des Mathématiques et de l’Informatique Master 1CS Département d’Informatique 2020/2021 Préparer par Dr K.DJEBAILI Page 3 Exercice 6 (Notion de cardinal) On commence par remarquer que, si on a prouvé que le nombre de parties de cardinal pair d'un ensemble à n élément est 2n−1, alors le nombre de parties du même ensemble qui sont de cardinal impair vaut également 2n−1. En effet, le nombre total de parties, qui vaut 2n, est la somme du nombre de parties de cardinal pair et du nombre de parties de cardinal impair. Démontrons maintenant le résultat. On procède par récurrence sur n. Si n=1, la seule partie de E de cardinal pair est ∅. On a bien 1=20. Supposons maintenant le résultat démontré au rang n, et prouvons-le au rang n+1. Soit donc E de cardinal n+1, et écrivons E={a}∪F où F est de cardinal n. Alors une partie de E de cardinal pair • ou bien contient a, et on doit alors la compléter avec une partie de cardinal impair de F. Il y a 2n−1 telles parties. • ou bien ne contient pas a, et c'est également une partie de cardinal pair de F. Il y a là aussi exactement 2n−1 telles parties. Finalement, on trouve que le nombre de parties de E de cardinal pair vaut 2n−1. L'hypothèse de récurrence est donc prouvée au rang n+1. uploads/Science et Technologie/ corrige-td1 5 .pdf