Correction : Algèbre générale, Nombre de surjections
2
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe et accède à tout notre catalogue !
Découvre YouScribe et accède à tout notre catalogue !
2
pages
Français
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Publié par
Licence :
Langue
Français
Publié par
Licence :
Langue
Français
1.
2.
3.
4.
1.
2.a
2.b
2.c
3.
1.a
Correction
Partie I
Pour≤,=!(!−uoP ! r).>,=0 .
Pour=0 :+−1=1+0=1=+ Pour1 .>0 :
+=!+!=!(−+1)+!=(+1)!=+1
−1!(−)! (−1)!(−+1)!!(−+1)!!(+1−)!.
Pour0 :=+.
=
−1=0+1 ru1oP >0 :
!(+1)!+1
−1=(−1)!(+1−)=+1!(+1−)=+1.
1 1
σ(,+1)==∑+(−1)−−1+1==∑+(−1)−1−+−1
00
.
11() 1 1( 1) 11 ( 1, 1( , ) 1
==∑+0−− −+∑=+0−− −+1+= −σ ++1σ++)
Partie II
Les applications surjectives entre deux ensembles àéléments correspondent aux applications
bijectives. Il y en a! donc(,)=! .
Il n’existe pas d’applications surjectives au départ d’un ensemble àéléments et à l’arrivée dans un
ensemble à>éléments, donc(,)=0 pour>.
Pour former une application telle que proposée, on part d’une surjection de\vers, il y en a
(,+ on choisit de manière quelconque1) puis() dans, ce qui offre+1 choix.
Au total, il y a (+1)(,+ de la forme proposée.1) surjections
Pour former une application telle que proposée, on choisit un élément dequi sera l’image de, il y a
+ on prolonge l’application par une surjection de1 choix, puis\vers\{()}ce qui offre
(,) choix.
Au total, il y a (+1)(,) surjections de la forme proposée.
Une surjection deversest ou bien de la première forme, ou bien de la seconde, donc
(+1,+1)=(+1)((,+1)+(,)).
Procédons par récurrence sur∈ℕ:
Pour=0 :
Pour=0 :(0, 0)=0!=1 etσ(0, 0)=1
.
Pour>0 :(0,)=0 etσ(0,)=0 .
Supposons la propriété établie au rang≥0 .
(+1,+1)=(+1)((,+1)+(,))=(+1)(σ(,+1)+σ(,))=σ(+1,+1) .
Récurrence établie.
Partie III
Existence :∈=∪donc∃∈ {1,…,}tel que∈.
=1
Unicité : Si∈et∈ℓ(avec,ℓ∈ {1,…,}) alors∩ℓ≠ ∅donc=ℓ.
1.b
2.
3.
∀∈ {1,…,},≠ ∅
. Pour∈, on a()=. Ainsiest surjective.
∀∈ {1,…,},≠ ∅car puisqueest surjective, l’élémentpossède au moins un antécédent.
∪⊂et∀∈,∈en prenant=() . Par suite⊂∪puis=∪.
=1=1=1
Soit,ℓ∈ {1,…,}, si∩ℓ≠ ∅alors pour∈∩ℓon a()=et()=ℓdonc=ℓ.
Par contraposée≠ℓ⇒∩ℓ= ∅.
Finalement (1,…,) est une partition àclasses de.
Par ce qui précède, il y a autant de partition àclasses que de fonction surjective devers{1,…,}:
−
il y a donc(,)=∑(−1) partitions àclasses de.
=0
