Cardinal d'une réunion, principe multiplicatif, arrangements, permutations et anagrammes, combinaisons, tirages dans une urne et binôme de Newton : cette série de 16 exercices corrigés couvre le chapitre « Dénombrement » de la 1re année du bac sciences mathématiques, seule filière qui l'étudie en 1re année. Elle suit l'ordre du cours et résumé de dénombrement, et chaque corrigé dit quel objet il compte (liste, arrangement, permutation, partie) avant d'écrire une formule.
Niveaux : 3 exercices faciles, 10 moyens et 3 difficiles, puis quatre questions flash et un devoir d'une heure qui associe le dénombrement, les applications et le raisonnement par récurrence. On compte des cas, sans calculer de probabilité : les probabilités viennent en 2e année.
Sommaire11 parties
Cardinal d’une réunion et diagrammes de Venn
On n'ajoute des cardinaux que pour des parties disjointes ; sinon on retranche les intersections, deux à deux puis, pour trois ensembles, on rajoute l'intersection des trois. Un diagramme de Venn se remplit du centre vers l'extérieur.
Exercice 1 : Cardinal d’une réunion de deux ensembles
Facile
Parmi les 120 élèves de 1 bac d'un lycée de Safi, 68 sont inscrits à la bibliothèque, 45 au club sportif, et 27 sont inscrits aux deux.
Combien d'élèves sont inscrits à la bibliothèque ou au club sportif ?
Combien d'élèves ne sont inscrits ni à l'une ni à l'autre ?
Combien d'élèves sont inscrits à une seule des deux activités ?
Voir le corrigé
On note E l'ensemble des 120 élèves, L celui des inscrits à la bibliothèque et S celui des inscrits au club sportif : card(L)=68,card(S)=45 et card(L∩S)=27.
Les deux parties ne sont pas disjointes, donc card(L∪S)=68+45−27=86 élèves.
On cherche le complémentaire de L∪S dans E :120−86=34 élèves.
Seulement la bibliothèque : 68−27=41 ; seulement le club sportif : 45−27=18. Ces deux parties sont disjointes : 41+18=59 élèves. Contrôle : 59+27=86=card(L∪S).
Exercice 2 : Formule de Poincaré pour trois ensembles
Moyen
Un centre de langues de Rabat accueille 60 élèves. 38 étudient l'anglais, 21 l'espagnol et 14 l'allemand ; 9 étudient l'anglais et l'espagnol, 6 l'anglais et l'allemand, 4 l'espagnol et l'allemand, et 2 étudient les trois langues.
Combien d'élèves étudient au moins une de ces trois langues ? Combien n'en étudient aucune ?
Combien d'élèves étudient exactement deux de ces langues ?
Combien d'élèves étudient exactement une de ces langues ?
Vérifier la cohérence des résultats.
Indication
Placer d'abord les 2 élèves des trois langues au centre du diagramme, puis compléter chaque intersection de deux langues.
Voir le corrigé
On note A,S,D les ensembles des élèves qui étudient l'anglais, l'espagnol et l'allemand.
Par la formule de Poincaré :
card(A∪S∪D)=38+21+14−9−6−4+2=56.
Il reste 60−56=4 élèves qui n'étudient aucune des trois langues.
Dans A∩S, 2 élèves étudient aussi l'allemand, donc 9−2=7 étudient exactement l'anglais et l'espagnol. De même 6−2=4 pour l'anglais et l'allemand seulement, et 4−2=2 pour l'espagnol et l'allemand seulement. Exactement deux langues : 7+4+2=13 élèves.
Anglais seulement : 38−7−4−2=25 ; espagnol seulement : 21−7−2−2=10 ; allemand seulement : 14−4−2−2=6. Exactement une langue : 25+10+6=41 élèves.
Les sept régions du diagramme sont disjointes : 41+13+2=56, ce qui est bien card(A∪S∪D). Avec les 4 élèves hors du diagramme, on retrouve 60.
Principe multiplicatif : codes, nombres et drapeaux
On décrit chaque résultat comme une suite de choix, en commençant par l'étape la plus contrainte (premier chiffre non nul, couleur imposée). On vérifie que le nombre de possibilités de chaque étape ne dépend pas des choix précédents. « Au moins un » se compte par le contraire.
Exercice 3 : Codes d’un casier, principe multiplicatif
Facile
Le code d'un casier de vestiaire est formé de 3 chiffres, de 0 à 9, suivis de 2 lettres prises parmi A, B, C, D, E, F (par exemple 507DA). Chiffres et lettres peuvent se répéter.
Combien de codes peut-on former ?
Combien de codes ont trois chiffres distincts ?
Combien de codes contiennent au moins un chiffre 0 ?
Combien de codes ont leurs trois chiffres rangés dans l'ordre strictement croissant et deux lettres distinctes ?
Voir le corrigé
Un code est une liste de 3 chiffres suivie d'une liste de 2 lettres, avec répétition : par le principe multiplicatif, 103×62=1000×36=36000 codes.
Les chiffres forment un arrangement sans répétition de 3 éléments parmi 10 : A103×62=720×36=25920 codes.
On compte le contraire : sans aucun 0, chaque chiffre a 9 choix, soit 93×36=26244 codes. Donc 36000−26244=9756 codes contiennent au moins un 0.
Une partie de 3 chiffres distincts ne se range que d'une seule façon dans l'ordre croissant : les triplets croissants correspondent aux combinaisons, C103=120. Les deux lettres distinctes forment un arrangement : A62=30. Total : 120×30=3600 codes.
Exercice 4 : Nombres de cinq chiffres avec contraintes
Moyen
On écrit des nombres de cinq chiffres, dont le premier n'est pas 0, avec les chiffres 0, 1, 2, 3, 4, 5 et 6.
Combien de tels nombres peut-on écrire ?
Combien d'entre eux ont cinq chiffres distincts ?
Parmi les nombres de la question 2, combien sont pairs ?
Parmi les nombres de la question 2, combien sont supérieurs à 50 000 ?
Indication
Question 3 : le chiffre des unités est 0, 2, 4 ou 6, mais le cas 0 ne contraint pas le premier chiffre de la même façon que les trois autres.
Voir le corrigé
Le premier chiffre a 6 choix (tous sauf 0), chacun des quatre autres en a 7 : 6×74=6×2401=14406 nombres.
Le premier chiffre a 6 choix ; les quatre suivants forment un arrangement de 4 chiffres parmi les 6 restants (le 0 est de nouveau permis) : 6×A64=6×360=2160 nombres.
On sépare selon le chiffre des unités, deux cas disjoints.
Unités 0 : les quatre premiers chiffres sont un arrangement de 4 chiffres parmi 1, …, 6, soit A64=360.
Unités 2, 4 ou 6 (3 choix) : le premier chiffre n'est ni 0 ni le chiffre des unités, 5 choix ; les trois chiffres du milieu forment un arrangement de 3 parmi les 5 restants, A53=60. Soit 3×5×60=900.
Total : 360+900=1260 nombres pairs.
Cinq chiffres distincts et supérieur à 50 000 : le premier chiffre est 5 ou 6 (le nombre 50 000 n'a pas ses chiffres distincts). Puis A64 choix pour les quatre suivants : 2×360=720 nombres.
Exercice 5 : Drapeaux à trois bandes, arrangements avec contraintes
Moyen
On colorie un drapeau de trois bandes verticales, lues de gauche à droite, avec 5 couleurs : rouge, vert, bleu, jaune et blanc.
Combien de drapeaux ont trois couleurs distinctes ?
On impose seulement que deux bandes voisines soient de couleurs différentes. Combien de drapeaux obtient-on ?
Combien de drapeaux à trois couleurs distinctes ont le vert au milieu ?
Combien de drapeaux à trois couleurs distinctes utilisent le rouge ? Répondre de deux façons.
Voir le corrigé
Les places sont ordonnées et les couleurs distinctes : arrangements de 3 couleurs parmi 5, A53=5×4×3=60 drapeaux.
Bande de gauche : 5 choix ; bande du milieu : toute couleur sauf celle de gauche, 4 choix ; bande de droite : toute couleur sauf celle du milieu, 4 choix (elle peut reprendre celle de gauche). Soit 5×4×4=80 drapeaux. Ce n'est pas un arrangement : la répétition est permise entre bandes non voisines. Contrôle : les drapeaux à bandes extrêmes de même couleur sont 5×4=20, et 80−20=60.
Le milieu est imposé ; les bandes extrêmes forment un arrangement de 2 couleurs parmi les 4 autres : A42=12.
Directement : le rouge occupe l'une des 3 bandes, puis les deux autres bandes reçoivent un arrangement de 2 couleurs parmi 4, soit 3×A42=36. Par le contraire : les drapeaux sans rouge sont A43=24, et 60−24=36.
Applications et parties d’un ensemble fini : exercices
Une application de E dans F se construit en choisissant l'image de chaque élément de E, et une application injective est un arrangement des images. Une partie de E se code par l'application qui vaut 1 sur la partie et 0 ailleurs.
Exercice 6 : Applications, injections et surjections d’ensembles finis
Difficile
Soient E={1;2;3;4} et F={a;b;c}.
Combien y a-t-il d'applications de E dans F ? de F dans E ?
Combien y a-t-il d'applications injectives de F dans E ? Existe-t-il une application injective de E dans F ?
Pour x∈F, on note Nx l'ensemble des applications de E dans F qui ne prennent pas la valeur x. Calculer card(Na),card(Na∩Nb) et card(Na∩Nb∩Nc).
En déduire le nombre d'applications surjectives de E sur F.
Combien de parties de E contiennent 1 et ne contiennent pas 2 ?
Indication
Question 4 : une application qui n'est pas surjective manque au moins une valeur, elle appartient donc à Na∪Nb∪Nc.
Voir le corrigé
On choisit l'image de chacun des 4 éléments de E parmi 3 : 34=81 applications de E dans F. Dans l'autre sens, 43=64 applications de F dans E.
Une application injective de F dans E envoie a,b,c sur trois éléments distincts de E, pris dans l'ordre : A43=4×3×2=24. De E dans F, c'est impossible : quatre éléments distincts devraient avoir quatre images distinctes dans un ensemble qui n'en a que trois.
Une application de Na prend ses valeurs dans {b;c} :card(Na)=24=16. Une application de Na∩Nb ne prend que la valeur c :card(Na∩Nb)=1. Enfin Na∩Nb∩Nc=∅, car une application de E prend au moins une valeur. Par symétrie des rôles, card(Nb)=card(Nc)=16 et chaque intersection de deux de ces ensembles a 1 élément.
Une application est surjective si elle prend chacune des trois valeurs, c'est-à-dire si elle n'est dans aucun Nx. Par la formule de Poincaré :
card(Na∪Nb∪Nc)=3×16−3×1+0=45.
Le nombre d'applications surjectives est donc 81−45=36. Contrôle : une surjection de E sur F donne à une valeur deux antécédents et aux deux autres un seul ; on choisit cette valeur (3 façons), ses deux antécédents (C42=6), puis les images des deux éléments restants (2 façons) : 3×6×2=36.
Une telle partie s'écrit {1}∪X, où X est une partie quelconque de {3;4}, et cette écriture est unique : il y en a 22=4, à savoir {1},{1;3},{1;4} et {1;3;4}.
Factorielles, permutations et anagrammes
Une permutation range tous les objets : n! rangements. Des objets qui doivent rester voisins forment un bloc, rangé comme un seul objet puis permuté à l'intérieur ; des lettres identiques divisent le nombre de rangements par la factorielle de leur nombre.
Exercice 7 : Factorielles, arrangements et combinaisons, calculs et équations
Facile
Calculer sans calculatrice 6!8!,A92,C143 et C2523.
8!=8×7×6!, donc 6!8!=56.A92=9×8=72.C143=3×2×114×13×12=364. Par symétrie, C2523=C252=225×24=300.
(n+2)!=(n+2)(n+1)×n!, donc n!(n+2)!=(n+2)(n+1). Contrôle avec n=6 :8×7=56, comme à la question 1.
An3=n(n−1)(n−2). Comme n≥3,n=0 et l'équation équivaut à (n−1)(n−2)=20, soit n2−3n−18=0, c'est-à-dire (n−6)(n+3)=0. Seule la solution n=6 convient : A63=120=20×6.
Pour n≥5,Cn3=3!(n−3)!n! et Cn5=5!(n−5)!n!. Comme n!=0, l'égalité Cn3=Cn5 équivaut à
5!(n−5)!=3!(n−3)!⇔20=(n−3)(n−4).
On divise par 3!(n−5)! et l'on utilise (n−3)!=(n−3)(n−4)×(n−5)!. Puis n2−7n−8=0, soit (n−8)(n+1)=0 : n=8. On retrouve la symétrie C83=C85=56, puisque 3+5=8.
Exercice 8 : Photo de famille, permutations et blocs
Moyen
Une famille de 9 personnes pose en ligne pour une photo : quatre couples et la grand-mère. Hamid et Salma forment l'un des quatre couples.
Combien de dispositions sont possibles ?
Combien de dispositions placent chaque couple côte à côte ?
Combien de dispositions placent la grand-mère au milieu de la ligne et chaque couple côte à côte ?
Combien de dispositions placent Hamid et Salma côte à côte ?
Indication
Question 3 : un couple côte à côte ne peut pas entourer la grand-mère ; combien de couples tiennent alors de chaque côté ?
Voir le corrigé
Une disposition est une permutation des 9 personnes : 9!=362880.
Chaque couple forme un bloc. Les 4 blocs et la grand-mère font 5 objets, rangés de 5!=120 façons ; dans chaque bloc, les deux époux se rangent de 2 façons : 5!×24=120×16=1920 dispositions.
La grand-mère occupe la 5e place. Un bloc occupe deux places voisines qui ne contiennent pas la 5e : les places 1 à 4 reçoivent deux blocs, les places 6 à 9 aussi, et les blocs occupent les paires de places 1-2, 3-4, 6-7 et 8-9. On range les 4 blocs sur ces 4 paires de places (4!=24 façons), puis chaque couple dans son bloc : 4!×24=384 dispositions.
Le bloc « Hamid et Salma » et les 7 autres personnes font 8 objets, rangés de 8! façons, et le bloc a 2 ordres internes : 2×8!=80640 dispositions.
Exercice 9 : Anagrammes du mot CASABLANCA
Moyen
On appelle anagramme de CASABLANCA tout mot de 10 lettres, ayant un sens ou non, formé avec exactement les lettres de ce mot.
Combien y a-t-il d'anagrammes de CASABLANCA ?
Combien commencent par C ?
Combien commencent et finissent par A ?
Combien ont leurs quatre A côte à côte ?
Combien ont leurs deux C séparés ?
Voir le corrigé
Le mot contient quatre A, deux C, et S, B, L, N une fois chacune : 4+2+1+1+1+1=10 lettres. On compte des permutations avec répétition.
4!×2!10!=483628800=75600 anagrammes.
On place C en tête ; il reste 9 lettres, dont quatre A et un seul C : 4!9!=15120.
Deux A sont aux extrémités ; les 8 places du milieu reçoivent deux A, deux C, S, B, L, N : 2!×2!8!=10080.
Le bloc AAAA, les deux C et S, B, L, N forment 7 objets, dont deux C identiques : 2!7!=2520.
Par le contraire. Si les deux C sont voisins, le bloc CC, les quatre A et S, B, L, N forment 9 objets dont quatre A identiques : 4!9!=15120 anagrammes. Les C sont séparés dans 75600−15120=60480 anagrammes. On retrouve le nombre de la question 2 : dans les deux cas, on range 9 objets dont quatre A identiques et cinq objets distincts.
Combinaisons : comités et points d’un cercle
Un groupe sans rôles est une partie : on compte des combinaisons. On découpe selon la composition imposée et l'on multiplie ; « au moins un » ou « pas ensemble » se comptent par le contraire. Un segment, un triangle ou un quadrilatère inscrit est déterminé par l'ensemble de ses sommets.
Exercice 10 : Comité d’une association, combinaisons
Moyen
Une association de Kénitra compte 10 femmes et 6 hommes, parmi lesquels Nadia et Karim. On forme un comité de 4 membres aux rôles identiques.
Combien de comités peut-on former ?
Combien de comités comportent exactement deux femmes ?
Combien de comités comportent au moins un homme ?
Nadia et Karim refusent de siéger ensemble. Combien de comités respectent ce souhait ?
Le comité doit maintenant avoir un président, les trois autres membres ayant le même rôle. Combien de comités peut-on former ? Comparer avec la question 1.
Voir le corrigé
Un comité est une partie de 4 personnes parmi 16 : C164=2416×15×14×13=1820.
On choisit 2 femmes parmi 10 et 2 hommes parmi 6, puis on multiplie : C102×C62=45×15=675.
Le contraire est « aucun homme », soit 4 femmes : C104=210. Donc 1820−210=1610 comités.
Les comités qui contiennent Nadia et Karim sont formés en choisissant les 2 autres membres parmi les 14 restants : C142=91. Il reste 1820−91=1729 comités.
On choisit le président (16 façons), puis les 3 autres membres parmi les 15 restants : 16×C153=16×455=7280. C'est 4×1820 : chaque comité de la question 1 donne 4 comités avec président, selon celui de ses 4 membres qui préside.
Exercice 11 : Points sur un cercle, segments, triangles et diagonales
Moyen
On place 11 points distincts sur un cercle ; trois points d'un cercle ne sont jamais alignés. A est l'un de ces points.
Combien de segments joignent deux de ces points ?
Combien de triangles ont leurs trois sommets parmi ces points ? Combien d'entre eux ont A pour sommet ?
Les 11 points sont les sommets d'un polygone convexe. Combien a-t-il de diagonales ?
Montrer qu'un polygone convexe à n côtés, n≥4, a quatre fois plus de diagonales que de côtés si et seulement si n=11.
Voir le corrigé
Un segment est déterminé par la paire de ses extrémités, sans ordre : C112=55.
Trois points non alignés déterminent un triangle, et l'ordre des sommets ne compte pas : C113=611×10×9=165 triangles. Avec A pour sommet, on choisit les deux autres sommets parmi 10 : C102=45.
Parmi les 55 segments, 11 sont des côtés du polygone et les autres sont des diagonales : 55−11=44.
Le même raisonnement donne, pour n sommets, Cn2−n=2n(n−1)−n=2n(n−3) diagonales. Pour n≥4 :2n(n−3)=4n⟺n−3=8⟺n=11,
en divisant par n=0.
Les équivalences prouvent les deux sens. Contrôle : 44=4×11.
Tirages dans une urne : exercices corrigés
Le mode de tirage décide du bon outil de dénombrement : tirage simultané, parties et Cnp ; successif sans remise, arrangements et Anp ; successif avec remise, listes et np. Les tirages qui vérifient une condition se comptent avec le même modèle que l'ensemble des tirages.
Exercice 12 : Une urne, trois façons de tirer trois boules
Moyen
Une urne contient 7 boules numérotées : 4 rouges et 3 bleues. On tire 3 boules.
Partie A : tirage simultané
Combien y a-t-il de tirages possibles ?
Combien de tirages donnent exactement deux boules rouges ?
Combien de tirages donnent au moins une boule bleue ?
Partie B : tirages successifs sans remise
Combien y a-t-il de tirages possibles ?
Combien de tirages donnent exactement deux boules rouges ?
Combien de tirages donnent une boule rouge puis deux boules bleues, dans cet ordre ?
Partie C : tirages successifs avec remise
Combien y a-t-il de tirages possibles ?
Combien de tirages donnent trois boules de la même couleur ?
Combien de tirages donnent exactement deux boules rouges ?
Voir le corrigé
Un tirage simultané est une partie de 3 boules parmi 7 : C73=35.
On choisit 2 rouges parmi 4 et 1 bleue parmi 3 : C42×C31=6×3=18.
Le contraire est « trois rouges » : C43=4. Donc 35−4=31 tirages.
Un tirage est un arrangement de 3 boules parmi 7 : A73=7×6×5=210.
On choisit le rang de la bleue (3 façons), les deux rouges dans l'ordre (A42=12), puis la bleue (3) : 3×12×3=108. Contrôle : chaque tirage simultané de la question 2 se range de 3!=6 façons, et 6×18=108.
L'ordre des couleurs est imposé : 4×3×2=24 tirages (4 rouges possibles, puis 3 bleues, puis 2).
Un tirage est une liste de 3 boules avec répétition : 73=343.
Trois rouges : 43=64 ; trois bleues : 33=27. Les deux cas sont disjoints : 64+27=91.
Rang de la bleue : 3 façons ; chaque rouge : 4 choix ; la bleue : 3 choix. Soit 3×42×3=144 tirages.
Trouver l’erreur dans une copie de dénombrement
Avant de corriger un calcul, on se demande quel objet il compte et si chaque objet cherché est compté une fois et une seule.
Exercice 13 : Trouver l’erreur, au moins une fille dans un groupe
Moyen
Un atelier de théâtre compte 7 filles et 8 garçons. On choisit 3 élèves pour une saynète, sans leur attribuer de rôle, et l'on cherche le nombre de groupes qui comportent au moins une fille. Voici la copie d'un élève :
« Je choisis d'abord une fille : 7 façons. Je complète avec 2 élèves quelconques parmi les 14 restants : C142=91 façons. Il y a donc 7×91=637 groupes. »
Sans chercher la bonne réponse, montrer que ce résultat est impossible.
Expliquer l'erreur de raisonnement.
Calculer le bon nombre de groupes.
Retrouver le nombre 637 en comptant les groupes selon leur nombre de filles.
Voir le corrigé
Il n'y a que C153=615×14×13=455 groupes de 3 élèves en tout : on ne peut pas en trouver 637 qui vérifient une condition.
La méthode compte des couples (fille désignée, groupe), pas des groupes. Un groupe de deux filles est obtenu deux fois, selon la fille choisie en premier, et un groupe de trois filles trois fois.
Le contraire de « au moins une fille » est « trois garçons » : C83=56. Il y a 455−56=399 groupes.
Une fille : C71×C82=7×28=196 ; deux filles : C72×C81=21×8=168 ; trois filles : C73=35. On retrouve 196+168+35=399. La copie compte chaque groupe autant de fois qu'il a de filles : 196+2×168+3×35=637.
Binôme de Newton et relation de Pascal : exercices
Le terme général de (a+b)n dans la formule du binôme de Newton est Cnkan−kbk, pour k de 0 à n ; on trouve k par l'exposant voulu. Une identité sur les Cnp se prouve par le calcul, par récurrence avec la relation de Pascal, ou en comptant de deux façons un même ensemble.
Exercice 14 : Binôme de Newton, coefficient d’un terme et calcul exact
Moyen
Soit x un réel non nul.
Écrire le terme général du développement de (2x−x1)8.
Déterminer le terme constant de ce développement.
Déterminer le coefficient de x4. Le développement contient-il un terme en x5 ?
À l'aide de la formule du binôme, calculer la valeur exacte de 1,025.
Voir le corrigé
Avec a=2x,b=−x1 et n=8, le terme de rang k,0≤k≤8, est
C8k(2x)8−k(−x1)k=(−1)kC8k28−kx8−2k.
Le terme est constant si 8−2k=0, soit k=4 :(−1)4C8424=70×16=1120.
8−2k=4 donne k=2 : le coefficient vaut C82×26=28×64=1792. Un terme en x5 exigerait 8−2k=5, soit k=23, qui n'est pas entier : il n'y en a pas.
1,025=(1+0,02)5 avec la ligne 5 du triangle de Pascal, 1, 5, 10, 10, 5, 1 :
1,025=1+5×0,02+10×0,0004+10×0,000008+5×0,00000016+0,0000000032=1,1040808032.
Exercice 15 : Relation de Pascal et identités par récurrence
Difficile
Montrer que pour tout entier n≥2,Cn2+Cn+12=n2.
Un groupe compte n filles et n garçons, n≥2. En comptant de deux façons les paires d'élèves du groupe, montrer que C2n2=2Cn2+n2.
Soit p un entier naturel. Montrer par récurrence que, pour tout entier n≥p,Cpp+Cp+1p+⋯+Cnp=Cn+1p+1.
En déduire, pour n≥2, la somme C22+C32+⋯+Cn2, puis la vérifier pour n=5.
Indication
Question 3 : dans l'hérédité, isoler le dernier terme Cn+1p de la somme et utiliser la relation de Pascal Cm+1q=Cmq−1+Cmq.
Voir le corrigé
Pour n≥2,Cn2=2n(n−1) et Cn+12=2(n+1)n. Leur somme vaut 2n[(n−1)+(n+1)]=22n2=n2.
Le groupe a 2n élèves : il y a C2n2 paires. On les classe en trois catégories disjointes : deux filles (Cn2), deux garçons (Cn2), une fille et un garçon (n×n par le principe multiplicatif). Donc C2n2=2Cn2+n2. Contrôle par le calcul : n(2n−1)=n(n−1)+n2.
Initialisation : pour n=p, la somme se réduit à Cpp=1, et Cp+1p+1=1.
Hérédité : supposons Cpp+⋯+Cnp=Cn+1p+1 pour un entier n≥p. Alors
Cpp+⋯+Cnp+Cn+1p=Cn+1p+1+Cn+1p=Cn+2p+1,
par la relation de Pascal Cm+1q=Cmq−1+Cmq avec m=n+1 et q=p+1, qui demande 1≤p+1≤n+1 : c'est vrai car p≤n.
Conclusion : l'égalité est vraie pour tout entier n≥p.
Avec p=2 :C22+C32+⋯+Cn2=Cn+13. Pour n=5 :1+3+6+10=20 et C63=66×5×4=20.
Exercice 16 : Couples de parties emboîtées et puissances de 3
Difficile
Soit n≥1 un entier et E un ensemble à n éléments. On note K l'ensemble des couples (A;B) de parties de E telles que A⊂B.
Écrire les éléments de K lorsque E={u;v}.
À un couple (A;B) de K, on associe l'application φ de E dans {1;2;3} définie par φ(x)=1 si x∈A,φ(x)=2 si x∈B∖A,φ(x)=3 si x∈/B. Montrer que cette correspondance est une bijection, puis calculer card(K).
En comptant les couples de K selon le nombre k d'éléments de B, montrer que ∑k=0nCnk2k=3n. Retrouver ce résultat avec la formule du binôme.
Combien y a-t-il de couples (A;B) de parties de E tels que A∪B=E ?
Indication
Question 2 : partant d'une application ψ de E dans {1;2;3}, reconstruire A et B à partir des éléments qui ont pour image 1, ou bien 1 ou 2.
Voir le corrigé
B=∅ donne (∅;∅) ;B={u} donne (∅;{u}) et ({u};{u}) ;B={v} donne (∅;{v}) et ({v};{v}) ;B=E donne (∅;E),({u};E),({v};E) et (E;E). Soit 9 couples.
Pour x∈E, un seul des trois cas « x∈A », « x∈B∖A », « x∈/B » se produit, car A⊂B :φ est bien une application. Réciproquement, soit ψ:E→{1;2;3}. Le seul couple possible est A={x/ψ(x)=1} et B={x/ψ(x)∈{1;2}} ; il vérifie A⊂B, et son application associée est ψ. Toute application a donc exactement un antécédent : la correspondance est bijective, et card(K)=3n, nombre d'applications de E dans {1;2;3}. Pour n=2, on retrouve 32=9.
On choisit B à k éléments (Cnk façons), puis A partie quelconque de B (2k façons). Les cas k=0, …, n sont disjoints, donc card(K)=∑k=0nCnk2k, et cette somme vaut 3n d'après la question 2. Par le binôme, avec a=1 et b=2 :∑k=0nCnk1n−k2k=(1+2)n=3n.
Si A∪B=E, chaque élément x de E est dans un seul des trois ensembles disjoints A∖B,B∖A,A∩B. Comme à la question 2, on associe au couple l'application qui vaut 1, 2 ou 3 selon le cas ; c'est une bijection, de réciproque ψ↦(A;B) avec A={x/ψ(x)∈{1;3}} et B={x/ψ(x)∈{2;3}}. Il y a donc 3n tels couples. Autre lecture : A∪B=E équivaut à B⊂A, et (A;B)↦(B;A) est une bijection de l'ensemble de ces couples sur K.
Questions flash avant le devoir
Sans calculatrice, une seule bonne réponse par question.
Question 1 : Mot de passe aux lettres distinctes
Flash
Un mot de passe est formé de 5 lettres distinctes, prises parmi les 12 lettres d'un clavier réduit, dans un ordre précis. Le nombre de mots de passe est :
C125
A125
125
5!
Voir le corrigé
Réponse B : l'ordre compte et les lettres sont distinctes, c'est un arrangement sans répétition. A oublie l'ordre, C permet la répétition, D ne range que 5 lettres déjà choisies.
Question 2 : Symétrie des combinaisons
Flash
Pour tout entier n≥1,Cnn−1 est égal à :
1
n−1
n!
n
Voir le corrigé
Réponse D : par symétrie, Cnn−1=Cn1=n. Choisir n−1 éléments revient à choisir celui que l'on écarte.
Question 3 : Nombre de parties d’un ensemble
Flash
Un ensemble E a 5 éléments. Le nombre de parties de E, la partie vide et E comprises, est :
32
25
10
120
Voir le corrigé
Réponse A : 25=32, chaque élément étant dans la partie ou non. B est 52, C est C52 seulement, D est 5!.
Question 4 : Coefficient dans un développement
Flash
Le coefficient de x2 dans le développement de (1+x)7 est :
7
14
21
35
Voir le corrigé
Réponse C : le terme en x2 est C72x2, et C72=27×6=21. B confond avec 2×7, D est C73.
Problème de synthèse type devoir surveillé
Ce problème associe le dénombrement au raisonnement par récurrence du chapitre de logique et au calcul avec les radicaux. Sujet d'entraînement de type devoir surveillé, écrit pour cette page.
Problème : digicode, jetons numérotés et binôme de Newton
Type devoir
Sujet d'entraînement de type devoir surveillé. Durée conseillée : 1 h. Barème sur 20 points. Calculatrice non autorisée.
Partie A : un digicode (6 points)
Le clavier d'un digicode porte 8 touches : les lettres A, B, C et les chiffres 1, 2, 3, 4, 5. Un code est une suite de 5 touches ; une même touche peut être utilisée plusieurs fois.
(1 point) Combien de codes peut-on former ?
(1,5 point) Combien de codes sont formés de 5 touches distinctes ?
(2 points) Combien de codes comportent exactement deux lettres ?
(1,5 point) Combien de codes comportent au moins une lettre ?
Partie B : jetons numérotés (7,5 points)
Un sac contient 11 jetons numérotés de 1 à 11. On tire simultanément 4 jetons.
(1 point) Combien y a-t-il de tirages ?
(1,5 point) Combien de tirages contiennent exactement deux numéros pairs ?
(1,5 point) Combien de tirages contiennent au moins un multiple de 4 ?
(1,5 point) Combien de tirages ont 9 pour plus grand numéro ?
(2 points) On tire maintenant les 4 jetons successivement et sans remise. Combien y a-t-il de tirages ? Combien d'entre eux font sortir les numéros dans l'ordre croissant ? Justifier.
Partie C : binôme de Newton et récurrence (6,5 points)
(1,5 point) Développer (1+3)4 à l'aide de la formule du binôme, puis calculer (1+3)4+(1−3)4.
(2,5 points) Montrer que pour tout entier n≥1, le nombre un=(1+3)n+(1−3)n est égal à la somme des 2Cnk3k/2 pour k pair, 0≤k≤n. En déduire que un est un entier pair.
(2,5 points) Montrer par récurrence que pour tout entier n≥1 :1×1!+2×2!+⋯+n×n!=(n+1)!−1.
Indication
Question 3 : choisir d'abord les deux places des lettres. Question 11 : comparer les termes de rang k des deux développements, sachant que (−3)k=(−1)k(3)k.
Voir le corrigé
Un code est une liste de 5 touches avec répétition : 85=32768 codes.
Touches distinctes et ordre compté : A85=8×7×6×5×4=6720 codes.
On choisit les 2 places des lettres parmi 5 (C52=10 façons), une lettre pour chacune de ces places (32=9) et un chiffre pour chacune des 3 autres (53=125) : 10×9×125=11250 codes.
Le contraire est « aucune lettre » : 55=3125 codes formés de chiffres seulement. Donc 32768−3125=29643 codes.
Un tirage simultané est une partie de 4 jetons parmi 11 : C114=2411×10×9×8=330.
Il y a 5 numéros pairs (2, 4, 6, 8, 10) et 6 impairs : C52×C62=10×15=150 tirages.
Les multiples de 4 sont 4 et 8. Le contraire, « aucun multiple de 4 », compte C94=126 tirages. Donc 330−126=204.
Le jeton 9 est tiré et les 3 autres numéros sont pris parmi 1, …, 8 : C83=56 tirages.
Les tirages successifs sans remise sont des arrangements : A114=11×10×9×8=7920. Les 4 numéros d'un tirage ordonné forment une partie, et chaque partie de 4 numéros ne sort dans l'ordre croissant que d'une seule façon parmi ses 4!=24 ordres. Il y a donc autant de tirages croissants que de parties : 330, et 7920=24×330.
Avec la ligne 4 du triangle, 1, 4, 6, 4, 1 :
(1+3)4=1+43+6×3+4×33+9=28+163.
En remplaçant 3 par −3,(1−3)4=28−163, et la somme vaut 56.
Par la formule du binôme,
un=k=0∑nCnk(3)k+k=0∑nCnk(−3)k=k=0∑nCnkck(3)k,
où ck=1+(−1)k, puisque (−3)k=(−1)k(3)k. Pour k impair, ck=0 ; pour k pair, ck=2 et (3)k=3k/2, où 2k est un entier naturel. Donc un est la somme des 2Cnk3k/2 pour k pair. Chaque terme est le double d'un entier naturel : un est un entier pair. Pour n=4, on retrouve u4=2(1+6×3+9)=56.
On raisonne par récurrence sur n≥1.
Initialisation : pour n=1,1×1!=1 et 2!−1=1.
Hérédité : on note Sn la somme du membre de gauche ; supposons Sn=(n+1)!−1 pour un entier n≥1. Alors
Sn+1 s'obtient en ajoutant (n+1)(n+1)! à Sn :Sn+1=(n+1)!−1+(n+1)(n+1)!=(n+2)(n+1)!−1=(n+2)!−1.
Conclusion : l'égalité est vraie pour tout entier n≥1.
Barème indicatif : partie A, 1 + 1,5 + 2 + 1,5 = 6 points ; partie B, 1 + 1,5 + 1,5 + 1,5 + 2 = 7,5 points ; partie C, 1,5 + 2,5 + 2,5 = 6,5 points ; total 20.