Sujet : 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: 52
• Licence : En savoir +
  Paternité, pas d'utilisation commerciale, partage des conditions initiales à l'identique
• Langue: Français

Extrait

Nombre de surjections

Dans tout le problème,etdésignent des entiers naturels.

Partie I

Pour tout∈ℕet∈ℤ, on notele nombre de parties àéléments d’un ensemble àéléments.

1. Rappeler l’expression deà l’aide de nombres factoriels lorsque∈ {0,…,}.
Que vautpour>ou<0 ?

2.

3.

4.

4.a

4.b

Démontrer, pour tout 0≤≤+1 , la relation+−1=+. 1
Etablir, pour tout 01+1
≤ ≤+, la relation−1=+1


On poseσ(,)=∑(−1)−.
=0
Calculerσ(0, 0) etσ(0,) pour>0 .
Montrer :σ(,+1)= −σ(,)+1+1σ(+1,+1) .

Partie II

On note(, nombre d’applications surjectives au départ d’un ensemble à) leéléments et à l’arrivée dans
un ensemble àéléments.
1. Calculer(,) et(,) pour>.
2. On considèreun ensemble à+1 éléments etun ensemble à+1 éléments.
2.a Combien y a-t-il de surjections:→dont la restriction au départ de\soit encore surjective ?
2.b Combien y a-t-il de surjections:→dont la restriction au départ de\n’est pas surjective ?
2.c En déduire la relation :(+1,+1)=(+1)((,+1)+(,) .

3.

Montrer que(,)=σ(,) .

Partie III

désigne un ensemble àéléments.
On appelle partition enclasses d’un ensemble (, toute famille1,…,) formée de parties detelles
que∀∈ {1,…,},≠ ∅,∪=et∀,ℓ∈ {1,…,},≠ℓ⇒∩ℓ= ∅.
1≤≤
1. Soit (1,…,) une partition àclasses de.
1.a Montrer que∀∈,∃!∈ {1,…,}tel que∈.
On pose alors()=ce qui définit une application:→ {1,…,}.

1.b

Montrer queest surjective.

2.

3.

Inversement, soit:→ {1,…,}surjective.
On pose, pour tout∈ {1,…,},=−1({}) .
Montrer que (1,…,) est une partition àclasses de.
Déduire de ce qui précède le nombre de partitions àclasses de

.