Combinatoire/Exercices/Combinaisons
Exercice 4-1
modifierSoient . Montrer les propriétés suivantes de deux façons : par le calcul et par un raisonnement combinatoire.
a) ;
b) et plus généralement, (identité de Vandermonde) ;
c) puis ;
d) ;
e) si , .
a) Par le calcul : si ou , les deux membres sont nuls. Si alors .
Par un raisonnement combinatoire : ces deux expressions correspondent à deux façons de dénombrer les couples , où est une partie à éléments d'un ensemble fixé de cardinal , et .
b) La première égalité est le cas de la seconde. Démontrons cette dernière.
Par le calcul : si ou , les deux membres sont nuls. Si , utiliser la formule du binôme pour développer l'identité polynomiale puis identifier le coefficient de (cf. Sommation/Exercices/Formule du binôme#Exercice 5-4).
Par un raisonnement combinatoire : ces deux expressions correspondent à deux façons de dénombrer les parties à r éléments de E ∪ F, où E et F sont deux ensembles disjoints fixés, de cardinaux respectifs m et n, cf. Sommation/Définition et premiers calculs#Établissement des formules à l'aide des dénombrements.
c) Par le calcul : si ou , les deux membres sont nuls. Si , cf. Sommation/Exercices/Formule du binôme#Exercice 5-1.
Par un raisonnement combinatoire : est le nombre de couples tels que , , et .
est le nombre de couples tels que , , et .
Ces deux ensembles de couples sont en bijection, par , de réciproque .
Ceci démontre la première égalité. La seconde s'en déduit en sommant sur , ce qui revient à dénombrer de deux façons les couples , où et (cf. Sommation/Exercices/Calculs élémentaires#Exercice 2-8).
d) Par le calcul : si , les deux membres sont nuls. Pour , on peut montrer la formule de deux façons :
- par récurrence sur , pour fixé : l'initialisation (cas ) est immédiate et l'hérédité se déduit de la formule de Pascal : Sommation/Exercices/Sommation de combinaisons#Exercice 6-3.
- par identification des coefficients du polynôme .
Par un raisonnement combinatoire : pour choisir une partie à éléments dans l'ensemble , on peut choisir d'abord dans le plus grand élément de cette partie, puis une partie à éléments dans l'ensemble . Autrement dit, en notant : on choisit un entier puis une partie à éléments dans .
e) Soient et . Il suffit de montrer que et
- Par le calcul : d'après la formule du binôme, et .
- Par un raisonnement combinatoire : soient un ensemble de cardinal et (resp. ) l'ensemble des parties de de cardinal pair (resp. impair). Alors, . D'autre part, car si est un élément fixé de , l'involution de qui, à toute partie , associe si et si , se restreint en une bijection entre et .
Déduire de l'égalité d) ci-dessus que , pour tout entier ou même complexe.
D'après d), d'où, par changement d'indice : . Pour fixé, on obtient ainsi que deux polynômes en coïncident en une infinité de points. Ils sont donc égaux.
Exercice 4-2
modifierGrâce à la question a) de l'exercice précédent, calculer :
- .
- (si , même résultat par calcul direct) ;
- (cas particuliers ou : mais ) ;
- ;
- .
Exercice 4-3
modifierDe combien de manières peut-on distribuer pièces de 1 euro :
- à enfants de sorte que chaque enfant ait au moins un euro ?
- à enfants ? (à présent, un enfant peut ne rien recevoir).
- à filles et garçons de sorte que chaque fille ait au moins un euro ?
- à filles et garçons de sorte que chaque fille ait au moins euros et chaque garçon au moins euros ?
- à filles et garçons de sorte que chaque fille ait exactement euros ?
(Dans chaque cas, on suppose qu'il y a au moins un enfant.)
- C'est le nombre de -uplets (avec par hypothèse) d'entiers strictement positifs de somme , c'est-à-dire (cf. chapitre « Combinaisons avec répétition ») .
- C'est le nombre de -uplets (avec par hypothèse) d'entiers positifs ou nuls de somme , c'est-à-dire (cf. chapitre « Combinaisons avec répétition ») .
- C'est le nombre de ( )-uplets (avec par hypothèse) d'entiers de somme , tels que les premiers soient strictement positifs et les suivants soient positifs ou nuls, ou encore, en ajoutant 1 aux derniers : le nombre de ( )-uplets d'entiers strictement positifs de somme , c'est-à-dire (d'après la question 1) : .
- Remarque : la question 1 est le cas particulier et la question 2 est le cas particulier .
- C'est le nombre de ( )-uplets d'entiers de somme , tels que les premiers soient supérieurs ou égaux à et les suivants soient supérieurs ou égaux à , ou encore, en retranchant aux premiers et aux suivants : le nombre de ( )-uplets d'entiers strictement positifs de somme , c'est-à-dire (d'après la question 1) .
- Remarques :
- ce nombre est non nul si et seulement si ;
- la question 3 est le cas particulier .
- Remarques :
- C'est le nombre de -uplets d'entiers positifs ou nuls de somme , c'est-à-dire (d'après la question 2) .
Exercice 4-4
modifier- Une urne contient boules distinctes et l'on veut sélectionner boules. Cette sélection peut se faire de quatre manières différentes (avec ou sans remise de la boule qui vient d'être tirée, en tenant compte ou non de l'ordre dans lequel les boules ont été sélectionnées). Compléter le tableau suivant en indiquant dans chaque cas le nombre de sélections possibles.
- Soient et . On considère les ensembles :
- ;
- ;
- .
- Vérifier que , , et remplissent les cases du tableau de la question 1.
Exercice 4-5
modifierSoient . Combien existe-t-il de -uplets tels que ?
Ces -uplets sont en bijection avec les -uplets d'entiers tels que , par l'application qui à associe .
Il y en a donc .
Exercice 4-6
modifierSoient . Combien existe-t-il de -uplets de somme tels que ?
Ces -uplets sont en bijection avec les -uplets d'entiers tels que , par l'application qui à associe .
Il y en a donc .
Exercice 4-7
modifierPour , on note le nombre de surjections de dans .
- Démontrer que .
- En déduire que .
- Choisir une surjection revient à choisir puis la restriction de à , qui doit être une surjection de dans ou dans .
- Récurrence sur .
- Initialisation : .
- Hérédité : soit . Supposons que .
Alors, d'après la question précédente :
Voir aussi Formule du crible/Dénombrement des surjections et Formule d'inversion de Pascal/Application au dénombrement des surjections.
Exercice 4-8
modifierOn note le nombre de Stirling de seconde espèce, égal au nombre de partitions de en parties.
- Démontrer que est lié au nombre de surjections de l'exercice précédent par : .
- En déduire une formule explicite pour , ainsi qu'une relation de récurrence.
- Redémontrer directement cette relation de récurrence.
- En utilisant cette relation, démontrer que
,
où désigne le polynôme « factorielle décroissante » : .
- Choisir une surjection de dans revient à choisir une partition de en parties, puis une bijection qui associe à chacune de ces parties un élément de .
- et .
- Dans l'ensemble des partitions de en parties, notons le sous-ensemble des partitions dont l'une des parties est le singleton , et le sous-ensemble complémentaire. Ainsi, .
Notons également , resp. , l'ensemble des partitions de en parties, resp. parties.
L'application de dans qui, à chaque associe la partition constituée des mêmes parties que sauf le singleton , est bijective, donc .
L'application de dans qui, à chaque , associe la partition déduite de en « gommant » du « bloc » qui le contient, est telle que chaque partition a exactement antécédents dans , formés en « recollant » à l'un des « blocs » de . Donc . - Récurrons. et si alors
Exercice 4-9
modifierOn avance sur la droite réelle, dans le sens positif, en partant de . Pour tout entier , on note le nombre de façons d'effectuer un trajet de longueur en faisant uniquement des pas de longueur ou . Les deux questions suivantes sont indépendantes.
- Démontrer que est égal au -ième nombre de Fibonacci , défini par
- .
- Exprimer comme une somme de coefficients binomiaux, en comptant le nombre de façons d'effectuer un trajet de longueur avec k pas de longueur (et les autres de longueur ).
- Récurrence d'ordre 2.
- Initialisation : (il n'y a qu'une façon de faire un trajet de longueur : en restant sur place) et (on ne peut faire un trajet de longueur que par un pas de longueur 1) donc et .
- Hérédité : pour tout , , en partitionnant les trajets de longueur en ceux finissant par un pas de longueur (donc précédés d'un trajet de longueur ) et ceux finissant par un pas de longueur (donc précédés d'un trajet de longueur ). On en déduit que si (hypothèse de récurrence) et , alors .
- Sur un trajet de longueur , si l'on fait pas de longueur , on en fait de longueur , soit au total pas. Le nombre de façon de choisir, parmi ces pas, lesquels seront les pas de longueur , est égal à (qui n'est non nul que si , c'est-à-dire ), et .