Nombres entiers naturels –Combinatoire
............................................................................................................ MÉTHODE
Pour montrer uneproposition P(n) par récurrence pour n n 0 , on peut :
• démontrer la proposition P(n 0 )e tl’implication :
∀n n 0
P(n) ⇒ P(n +1)
(cf. Application 1 et exercices 2 à 4) ;
• démontrerles propositions P(n 0 ), P(n 0 +1), et l’implication :
∀n n 0
P(n)etP(n+1)
⇒ P(n+2)
(cf. exercice 5) ;
• démontrerlaproposition P(n 0 )e tl’implication :
∀n n 0
∀p ∈ [[ n 0 , n ]] P ( p )
⇒ P ( n +1)
(cf. Application 2) .
Pourmontrer l’existence de deux éléments distincts de E ayantlamême image par uneapplication f de
E dans F ,ilsuffit de montrer que :
Card(E)>Card F
(cf.Application 4 et exercice 8) .
Pour dénombrer un ensemble fini,onpeut:
• soit compter tous les éléments une fois et une seule ;
• soit compter chaque élément p fois,puis diviser le résultat par p
(cf. Application 5 et exercices 9 à 13) .
Pour démontrer une formule de combinatoire,onpeut:
• effectuer une récurrence ;
• interpréter la formule en termes de dénombrement;
• utiliser la formule du binôme (cf. Application 6 et exercices 15 à 19) .
...................................................................................................................................................................................................
178
............................................................................................................ MÉTHODE
Pour montrer uneproposition P(n) par récurrence pour n n 0 , on peut :
• démontrer la proposition P(n 0 )e tl’implication :
∀n n 0
P(n) ⇒ P(n +1)
(cf. Application 1 et exercices 2 à 4) ;
• démontrerles propositions P(n 0 ), P(n 0 +1), et l’implication :
∀n n 0
P(n)etP(n+1)
⇒ P(n+2)
(cf. exercice 5) ;
• démontrerlaproposition P(n 0 )e tl’implication :
∀n n 0
∀p ∈ [[ n 0 , n ]] P ( p )
⇒ P ( n +1)
(cf. Application 2) .
Pourmontrer l’existence de deux éléments distincts de E ayantlamême image par uneapplication f de
E dans F ,ilsuffit de montrer que :
Card(E)>Card F
(cf.Application 4 et exercice 8) .
Pour dénombrer un ensemble fini,onpeut:
• soit compter tous les éléments une fois et une seule ;
• soit compter chaque élément p fois,puis diviser le résultat par p
(cf. Application 5 et exercices 9 à 13) .
Pour démontrer une formule de combinatoire,onpeut:
• effectuer une récurrence ;
• interpréter la formule en termes de dénombrement;
• utiliser la formule du binôme (cf. Application 6 et exercices 15 à 19) .
...................................................................................................................................................................................................
178