Correction : Algèbre générale, Nombre de surjections

David Delaunay Http://Mpsiddl.Free.Fr

Description

Dénombrement

Sujets

• Classe préparatoire aux grandes écoles
• Mathématiques, physique et sciences de l'ingénieur
• Public Readiness and Emergency Preparedness Act
• exercices

Informations

• Publié par: algebre-mpsi
• Nombre de lectures: 138
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

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−)!.

Pour0 :=+.
=
−1=0+1 ru1oP >0 :
 !(+1)!+1
−1=(−1)!(+1−)=+1!(+1−)=+1.
1 1
σ(,+1)==∑+(−1)−−1+1==∑+(−1)−1−+−1
00
.
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 dequi 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 deversest 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()=. Ainsiest surjective.

∀∈ {1,…,},≠ ∅car puisqueest surjective, l’élémentpossè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 devers{1,…,}:

−
il y a donc(,)=∑(−1) partitions àclasses de.
=0