Oral : Dénombrement et formule du crible

Dénombrement et formule du crible

CENTRALEDifficileDénombrement25 min

Consignes de l'examinateur

L'examinateur attend une maîtrise fluide de la formule du crible avec applications immédiates. Le passage de la formule abstraite aux cas concrets (surjections, dérangements) doit être naturel.

Énoncé

Énoncer et démontrer la formule d'inclusion-exclusion (formule du crible).

Surjections : Déterminer le nombre de surjections d'un ensemble à

n

éléments vers un ensemble à

p

éléments (

n \geq p

Dérangements : Un dérangement est une permutation sans point fixe. Déterminer le nombre

D_n

de dérangements de

\{1, \ldots, n\}

Montrer que

D_n/n! \to 1/e

Indices

0/3 révélé

Retour aux oraux

Oraux