COURS 9
Nombresentiers naturels –Combinatoire
IMPORTANT
En particulier, si A ∈P(E),
Card C E A = Card E − Card A.
Démonstration
Soit n = Card E et p = Card F . Il existe une bijection f de E dans [[ 1 , n ]]
et une bijection g de F dans [[ n +1,n+p]] . Soit h l’applicationd e E∪F
dans [[ 1 , n + p ]] qui, àt out élément x de E ∪ F , associe f (x)s ix∈E ,et
g(x)s ix∈F . hest bijective, car E ∩ F = ∅. Donc E ∪ F est fini et
Card (E ∪ F ) = n + p.
3.3 • Réunionquelconque
Théorème 5
Quels que soient les ensembles finis E et F : E ∪ F est fini et :
Card (E ∪ F ) = Card E +Card F − Card (E ∩ F )
IMPORTANT
En ajoutant Card E et Card F ,
on compte deuxf ois les éléments de
E ∩ F . C’est pourquoi il faut retrancherl ec ardinal de cette intersection.
Dans une situation concrète de dénombrement, on peut compter plusieurs fois les mêmes objets,àc ondition d’en être conscient et de les retrancher autant de foisq u’il le faut
dans le résultat final.
Démonstration
E ∪ F = E ∪ (F \E)e tE∩( F \ E )=∅ ,d’où E ∪ F estfini et :
Card (E ∪ F ) = Card (E)+Card (F \E)
Par ailleurs, F \E = C F E ∩ F ;d onc Card (F \E) = Card F − Card (E ∩ F ).
En définitive,C ard (E ∪ F ) = Card E +Card F − Card (E ∩ F ).
Pour s’entraîner:ex. 7
3.4 • Produit cartésien
Théorème 6
Si E et F sont deux ensembles finis, E × F est fini et :
Card (E × F ) = Card E× Card F
EXEMPLE
Combien peut-on écrire de mots de
trois lettres ?
Il s’agit de 3-listes d’éléments de l’alphabet,qui possède 26 éléments ;
d’où 26
3 = 17 576 mots distincts.
Démonstration
Soit E = {e 1 , e 2 , ··· ,e p };
E ×F = ({e 1 }×F) ∪ ({e 2 }×F) ∪· ·· ∪ ({e p }×F).
Il s’agit d’une réunion disjointe, donc E × F est fini et :
Card (E × F ) =
p
i=1
Card ({e i }×F)
Chacun de ces ensembles este nb ijection avec F , donc Card ({e i }×F) =
Card F .
En définitive, Card(E×F)=pCard F = Card E × Card F .
Plusg énéralement, Card (F
n
) = (Card F )
n
. C’estl en ombre de n-listes d’élémentsde F. On utilise les n-listes danstousles problèmesdechoix successifsde
n éléments d’un ensemble, avec d’éventuelles répétitions.
3.5 • Applications
Théorème 7
Si E et F sont deux ensembles finis, F
E
est fini et :
Card (F
E
) = (Card F )
Card E
172
Nombresentiers naturels –Combinatoire
IMPORTANT
En particulier, si A ∈P(E),
Card C E A = Card E − Card A.
Démonstration
Soit n = Card E et p = Card F . Il existe une bijection f de E dans [[ 1 , n ]]
et une bijection g de F dans [[ n +1,n+p]] . Soit h l’applicationd e E∪F
dans [[ 1 , n + p ]] qui, àt out élément x de E ∪ F , associe f (x)s ix∈E ,et
g(x)s ix∈F . hest bijective, car E ∩ F = ∅. Donc E ∪ F est fini et
Card (E ∪ F ) = n + p.
3.3 • Réunionquelconque
Théorème 5
Quels que soient les ensembles finis E et F : E ∪ F est fini et :
Card (E ∪ F ) = Card E +Card F − Card (E ∩ F )
IMPORTANT
En ajoutant Card E et Card F ,
on compte deuxf ois les éléments de
E ∩ F . C’est pourquoi il faut retrancherl ec ardinal de cette intersection.
Dans une situation concrète de dénombrement, on peut compter plusieurs fois les mêmes objets,àc ondition d’en être conscient et de les retrancher autant de foisq u’il le faut
dans le résultat final.
Démonstration
E ∪ F = E ∪ (F \E)e tE∩( F \ E )=∅ ,d’où E ∪ F estfini et :
Card (E ∪ F ) = Card (E)+Card (F \E)
Par ailleurs, F \E = C F E ∩ F ;d onc Card (F \E) = Card F − Card (E ∩ F ).
En définitive,C ard (E ∪ F ) = Card E +Card F − Card (E ∩ F ).
Pour s’entraîner:ex. 7
3.4 • Produit cartésien
Théorème 6
Si E et F sont deux ensembles finis, E × F est fini et :
Card (E × F ) = Card E× Card F
EXEMPLE
Combien peut-on écrire de mots de
trois lettres ?
Il s’agit de 3-listes d’éléments de l’alphabet,qui possède 26 éléments ;
d’où 26
3 = 17 576 mots distincts.
Démonstration
Soit E = {e 1 , e 2 , ··· ,e p };
E ×F = ({e 1 }×F) ∪ ({e 2 }×F) ∪· ·· ∪ ({e p }×F).
Il s’agit d’une réunion disjointe, donc E × F est fini et :
Card (E × F ) =
p
i=1
Card ({e i }×F)
Chacun de ces ensembles este nb ijection avec F , donc Card ({e i }×F) =
Card F .
En définitive, Card(E×F)=pCard F = Card E × Card F .
Plusg énéralement, Card (F
n
) = (Card F )
n
. C’estl en ombre de n-listes d’élémentsde F. On utilise les n-listes danstousles problèmesdechoix successifsde
n éléments d’un ensemble, avec d’éventuelles répétitions.
3.5 • Applications
Théorème 7
Si E et F sont deux ensembles finis, F
E
est fini et :
Card (F
E
) = (Card F )
Card E
172