Chargement du chapitre…
33 exercices de difficulté croissante, à chercher avant de regarder le corrigé.
33 exercices, difficulté croissante de ★ (application directe) à ★★★★ (défi). Les corrigés détaillés sont dans le PDF — cherchez d'abord, le corrigé ensuite : c'est là que ça progresse.
Cardinal d'un ensemble fini, bijection et cardinal, comparaison des cardinaux
Pour chacun des ensembles suivants, exhiber une bijection explicite entre un ensemble de la forme (ou un ensemble dont le cardinal est connu) et l'ensemble étudié, démontrer que c'est une bijection, puis en déduire le cardinal. Dans les questions (c), (d) et (e), désigne un entier naturel fixé, avec en (d) et (e).
a. L'ensemble des entiers naturels qui s'écrivent avec exactement deux chiffres.
b. L'ensemble des multiples de appartenant à .
c. .
d. L'ensemble des entiers impairs de .
e. . On utilisera l'application et la formule du cours donnant le nombre de parties à deux éléments d'un ensemble à éléments. Contrôler le résultat pour en écrivant tous les éléments de .
Cardinal d'un ensemble fini, bijection et cardinal, comparaison des cardinauxListes, nombre d'applications et nombre de parties d'un ensemble fini
Soit un ensemble fini de cardinal . On fixe un élément . Dans les questions 1 à 3, on ne calcule aucun coefficient binomial : tout se déduit de bijections. On admet pour tout ensemble fini , sauf à la question 4, où l'on redémontre ce résultat.
Montrer que l'application , (complémentaire dans ) est une bijection, et qu'elle envoie sur pour tout . En déduire, sans calcul, que .
On note l'ensemble des parties de qui contiennent . Montrer que est une bijection de sur , et en déduire .
Pour deux parties et de , on appelle différence symétrique de et la partie
formée des éléments qui appartiennent à exactement l'une des deux. On pose pour .
a. Montrer que si , et si .
b. Montrer que et que échange les parties de cardinal pair et les parties de cardinal impair.
c. En déduire que a autant de parties de cardinal pair que de parties de cardinal impair, et que ce nombre vaut . Contrôler pour .
On note l'ensemble des applications de dans . À toute partie de on associe sa fonction indicatrice , qui vaut sur et ailleurs. Montrer que est injective, puis qu'elle est bijective, et retrouver .
Un étudiant propose, pour la question 2, l'application , . Pourquoi n'est-ce pas une bijection ? Qu'est-ce qu'il faut vérifier, en général, avant d'écrire « par bijection, les deux ensembles ont le même cardinal » ? Que donne malgré tout cette application, si l'on compte ses antécédents ?
Principe additif : réunion disjointe, partition, complémentaire, réunion de deux ensemblesFormule du crible (inclusion-exclusion)
Dans chaque question, nommer les ensembles que l'on compte et le principe employé (principe additif, passage au complémentaire, formule du crible à deux ensembles).
a. Un code est une suite de chiffres, de à . Combien de codes contiennent au moins une fois le chiffre ?
b. Démontrer, en n'utilisant que la définition d'un multiple, qu'un entier est à la fois multiple de et multiple de si et seulement s'il est multiple de . En déduire le nombre d'entiers de qui sont multiples de ou de .
c. Combien d'entiers de ne sont multiples ni de ni de ?
d. Un mot de lettres est une suite de lettres de l'alphabet usuel, qui en compte , sans souci de sens. On considère les voyelles , , , , , . Combien de mots de lettres commencent par une voyelle ou finissent par une voyelle ? On fera le calcul de deux façons : par la formule du crible, puis par passage au complémentaire.
Principe multiplicatif : produit cartésien, choix successifs, lemme des bergers
a. Un restaurant propose entrées, plats et desserts, tous différents.
b. On admet que tout entier s'écrit de façon unique comme produit de nombres premiers (aux ordres des facteurs près), et que les diviseurs positifs de sont exactement les entiers avec , et (ces deux résultats sont démontrés dans le chapitre « Arithmétique dans Z »). On remarque que .
c. On remplit une grille d'une ligne de cases avec des lettres de l'alphabet ( lettres), de sorte que deux cases voisines ne portent jamais la même lettre (les cases et peuvent porter la même lettre).
Principe multiplicatif : produit cartésien, choix successifs, lemme des bergersCardinal d'un ensemble fini, bijection et cardinal, comparaison des cardinaux
Pour une application et un élément , on appelle fibre de l'ensemble de ses antécédents.
Le lemme. Soient et deux ensembles finis, un entier, et une application surjective telle que chaque élément de a exactement antécédents. Démontrer que
On montrera que les fibres , pour , forment une partition de .
Les parties à deux éléments. Soit un ensemble à éléments. On note l'ensemble des couples tels que .
a. Calculer .
b. En appliquant le lemme à l'application , , retrouver . Contrôler pour .
Le cube de dimension . Soit . On appelle sommets les éléments de , et l'on dit que deux sommets et sont voisins s'ils diffèrent en exactement une coordonnée : il existe un unique indice tel que . Une arête est une partie de formée de deux sommets voisins.
a. Combien un sommet a-t-il de voisins ? Combien y a-t-il de couples de sommets voisins ?
b. En déduire, par le lemme des bergers, que le nombre d'arêtes vaut .
c. Contrôler pour , (on reconnaîtra un carré) et (on reconnaîtra un cube).
Listes, nombre d'applications et nombre de parties d'un ensemble fini
Dans chaque question, rédiger la bijection avec un ensemble de listes, puis conclure. Dans les questions 1 à 3, et sont deux entiers supérieurs ou égaux à , et .
Combien y a-t-il d'applications de dans ?
Combien d'applications vérifient ?
On suppose . Combien d'applications de dans prennent toutes leurs valeurs dans ?
Soit . Un mot binaire de longueur est une liste de éléments de . Combien de mots binaires de longueur ont leur première et leur dernière lettre égales ? Contrôler pour .
Soit un ensemble à éléments. Une relation binaire sur est, par définition, une partie de (l'ensemble des couples tels que est en relation avec ). Combien y a-t-il de relations binaires sur ? Contrôler pour .
Combien y a-t-il d'applications de dans ?
Listes, nombre d'applications et nombre de parties d'un ensemble finiFormule du binôme de Newton et sommes de coefficients binomiauxCardinal d'un ensemble fini, bijection et cardinal, comparaison des cardinaux
On veut démontrer de trois façons que, pour tout ensemble fini de cardinal ,
Par récurrence sur . Démontrer la propriété en distinguant, dans un ensemble à éléments, les parties qui contiennent un élément fixé et celles qui ne le contiennent pas.
Par une bijection avec des listes. On numérote les éléments de : , avec . À une partie de , on associe la liste définie par si et sinon. Montrer que l'on obtient une bijection et conclure. Interpréter la liste comme une application de dans .
Par le binôme. En classant les parties de selon leur cardinal, exprimer comme une somme de coefficients binomiaux, puis conclure par la formule du binôme de Newton.
Applications. Dans cette question, .
a. Combien a-t-il de parties de cardinal au moins ?
b. Combien a-t-il de parties qui contiennent ou ? On fera le calcul par passage au complémentaire, puis par la formule du crible.
Comparer ce que chacune des trois démonstrations apprend, au-delà du résultat.
Rédiger un dénombrement : choisir le modèle, ordre ou pas ordre, ne pas compter deux foisArrangements et nombre d'injectionsCombinaisons, parties à p éléments, coefficients binomiauxListes, nombre d'applications et nombre de parties d'un ensemble fini
Une association compte membres. Dans chacune des quatre situations suivantes, on demande : quel est l'objet compté (liste, liste sans répétition, partie, partie dont un élément est distingué), quel modèle du cours s'applique et pourquoi, puis le nombre de possibilités.
a. On élit un bureau formé d'un président, d'un secrétaire et d'un trésorier, qui sont trois personnes distinctes.
b. On désigne une délégation de trois personnes, sans rôle particulier, pour représenter l'association à un congrès.
c. On attribue trois prix différents : le prix de l'accueil, le prix de la logistique et le prix de la communication. Une même personne peut recevoir plusieurs prix.
d. On choisit une délégation de trois personnes et, parmi elles, un porte-parole. Faire le calcul de deux façons, selon que l'on choisit d'abord la délégation ou d'abord le porte-parole, et vérifier que les deux résultats concordent.
e. Démontrer, par le lemme des bergers, la relation entre les réponses aux questions (a) et (b). Trouver de même une relation entre les réponses aux questions (a) et (d).
Arrangements et nombre d'injections
Dans chaque question, on demande d'abord d'identifier l'objet compté : une liste d'éléments deux à deux distincts (un arrangement) ou une injection entre deux ensembles que l'on nommera. On conclut ensuite par la formule du cours, en écrivant le calcul.
(a) Une course réunit coureurs, et il n'y a jamais d'ex aequo. Combien de podiums (un premier, un deuxième, un troisième) sont possibles ?
(b) Combien y a-t-il d'injections de dans ? Comparer au nombre de toutes les applications de dans .
(c) Un cadenas s'ouvre avec un code de chiffres, de à . Combien de codes ont leurs quatre chiffres deux à deux distincts ?
(d) Combien y a-t-il d'injections de dans ? Donner deux justifications : l'une par la formule du cours, l'autre par le principe des tiroirs.
(e) De combien de façons peut-on asseoir personnes sur chaises numérotées, chaque chaise recevant au plus une personne ? Retrouver le résultat par un second calcul, en choisissant d'abord les chaises occupées.
Permutations, factorielle, anagrammes et mots à lettres répétéesPrincipe multiplicatif : produit cartésien, choix successifs, lemme des bergersPrincipe additif : réunion disjointe, partition, complémentaire, réunion de deux ensembles
Huit personnes, parmi lesquelles Alice et Bruno, se placent en rang pour une photo. On appelle alignement l'ordre des huit personnes de gauche à droite, c'est-à-dire une liste dans laquelle chacune des huit personnes apparaît exactement une fois.
Combien y a-t-il d'alignements ?
Combien d'alignements placent Alice et Bruno côte à côte ? On justifiera la méthode du « bloc » par une bijection, puis on contrôlera le résultat par un second calcul.
Combien d'alignements placent Alice et Bruno à des places non voisines ?
Combien d'alignements placent Alice à gauche de Bruno, voisins ou non ? On utilisera l'application qui échange les places d'Alice et de Bruno.
Les huit personnes s'assoient maintenant autour d'une table ronde à huit places, et l'on ne distingue pas les places : deux dispositions ne diffèrent que si au moins une personne n'a pas le même voisin de droite. Une disposition circulaire est donc, par définition, la donnée pour chaque personne de son voisin de droite. À tout alignement , on associe la disposition circulaire obtenue en asseyant , puis à la droite de , à la droite de , et ainsi de suite jusqu'à , qui a lui-même pour voisin de droite.
a. Montrer que chaque disposition circulaire est obtenue à partir d'exactement alignements.
b. En déduire le nombre de dispositions circulaires, et contrôler la méthode sur le cas de personnes.
Permutations, factorielle, anagrammes et mots à lettres répétées
On appelle anagramme d'un mot tout mot obtenu en changeant l'ordre de ses lettres, qu'il figure ou non dans le dictionnaire ; le mot lui-même est l'une de ses anagrammes. Ainsi les anagrammes de AAB sont AAB, ABA et BAA.
On considère un mot de lettres dans lequel figurent lettres différentes , la lettre apparaissant fois, avec . On veut démontrer que le nombre d'anagrammes de ce mot est
a. Première démonstration. On distingue les exemplaires d'une même lettre en les numérotant (pour ANANAS : ). Appliquer le lemme des bergers à l'application qui efface les numéros.
b. Seconde démonstration. Construire une anagramme en choisissant successivement les positions de chaque lettre.
Combien d'anagrammes ont les mots ANANAS, ENSEMBLE et MISSISSIPPI ? Pour ANANAS, faire le calcul par les deux méthodes.
On s'intéresse aux anagrammes du mot ENSEMBLE.
a. Combien d'entre elles ne présentent pas les trois E consécutifs (c'est-à-dire ne contiennent pas le bloc EEE) ?
b. Combien d'entre elles ne présentent aucun E à côté d'un autre E ?
c. Expliquer pourquoi les réponses à a et b sont différentes, et interpréter leur différence.
Combinaisons, parties à p éléments, coefficients binomiaux
Calculer les coefficients binomiaux suivants, en détaillant le calcul ( désigne un entier, avec pour e et pour f).
a.
b.
c.
d.
e.
f.
Soit . Un polygone convexe à côtés a sommets ; on appelle diagonale tout segment qui joint deux sommets non consécutifs. Montrer de deux façons que le polygone a diagonales : en retirant les côtés de l'ensemble des segments qui joignent deux sommets, puis par le lemme des bergers. Contrôler pour .
Soit . On se donne points du plan, trois d'entre eux n'étant jamais alignés. Combien de triangles ont leurs trois sommets parmi ces points ? Donner la valeur pour , et dire à quoi sert l'hypothèse d'alignement.
On appelle main de cartes un ensemble de cartes distinctes d'un jeu de cartes, l'ordre dans lequel on les reçoit ne comptant pas. Combien y a-t-il de mains ?
Combinaisons, parties à p éléments, coefficients binomiauxPrincipe additif : réunion disjointe, partition, complémentaire, réunion de deux ensemblesPrincipe multiplicatif : produit cartésien, choix successifs, lemme des bergers
Un laboratoire compte doctorantes, parmi lesquelles Claire, et doctorants, parmi lesquels David. On forme un comité de personnes choisies parmi ces jeunes chercheurs ; un comité est un ensemble de personnes, sans rôle particulier, sauf en (e).
(a) Combien de comités peut-on former ?
(b) Combien de comités comportent exactement doctorantes ?
(c) Combien de comités comportent au moins un doctorant ?
(d) Claire et David refusent de siéger ensemble. Combien de comités respectent ce refus ?
(e) On forme maintenant un comité de personnes et l'on désigne, parmi ses membres, un président. Combien y a-t-il de possibilités ? Faire le calcul de deux façons, selon que l'on choisit d'abord le comité ou d'abord le président.
(f) Contrôle de cohérence : classer les comités de la question (a) selon leur nombre de doctorantes, calculer le nombre de comités pour chaque valeur de , et vérifier que le total redonne le résultat de (a). Retrouver de même le résultat de (c).
Symétrie, formule de Pascal, triangle de Pascal, formule du pivot
On rappelle la convention du cours : si ou .
À l'aide de la formule de Pascal , construire les lignes à du triangle de Pascal, c'est-à-dire le tableau des pour .
Soient et un entier tel que . Démontrer la formule de Pascal :
a. par le calcul, à partir de l'expression de par des factorielles (on traitera à part les cas et ) ;
b. par un argument de parties : dans un ensemble à éléments, on fixe un élément et l'on classe les parties à éléments selon qu'elles contiennent ou non.
Lire sur le tableau de la question 1, puis justifier :
a. la symétrie de chaque ligne ;
b. la somme des termes de chaque ligne ;
c. la colonne .
Montrer que, pour tout entier , :
a. par le calcul ;
b. par la formule de Pascal, puis en lisant l'identité sur le tableau.
a. Calculer la somme alternée pour , en lisant le tableau.
b. Démontrer que pour tout , sans utiliser la formule du binôme : on écrira chaque terme à l'aide de la formule de Pascal et l'on reconnaîtra une somme télescopique.
c. Que vaut cette somme pour ? À quel endroit la démonstration de b utilise-t-elle ?
Symétrie, formule de Pascal, triangle de Pascal, formule du pivotFormule du binôme de Newton et sommes de coefficients binomiaux
Soient et un entier tel que . On veut démontrer la formule du pivot
a. La démontrer par le calcul, à partir des factorielles.
b. La démontrer en comptant de deux façons les comités de personnes, choisies dans un ensemble de personnes, munis d'un président choisi parmi les membres du comité.
c. Que deviennent les deux membres pour ?
En déduire que, pour tout ,
a. Démontrer que, pour tout et tout entier tel que ,
b. En déduire que, pour tout ,
Contrôler les deux sommes des questions 2 et 3 pour , en les calculant directement à partir de la ligne du triangle de Pascal.
Symétrie, formule de Pascal, triangle de Pascal, formule du pivotDouble comptage, preuves combinatoires d'identités, formule de Vandermonde
Dans tout l'exercice, désigne un entier naturel. On rappelle la convention si , et la formule de Pascal , valable pour et .
Soit . Démontrer que
en écrivant chaque terme comme une différence à l'aide de la formule de Pascal, puis en reconnaissant une somme télescopique.
Redémontrer la même identité par un argument combinatoire : on classera les parties à éléments de selon leur plus grand élément.
Lire l'identité sur le triangle de Pascal : quelles cases additionne-t-on, et où se trouve le résultat ? Illustrer avec et .
Applications. Soit .
a. Retrouver .
b. Montrer que .
c. En déduire que , et contrôler pour .
Calculer, pour , la somme , et contrôler le résultat pour .
Formule du binôme de Newton et sommes de coefficients binomiaux
On rappelle la formule du binôme de Newton : pour tous réels , et tout entier ,
Développer et réduire :
a. ;
b. .
Déterminer le coefficient de dans le développement de .
Pour , on développe en une somme de puissances de . Déterminer le terme constant, c'est-à-dire le terme qui ne dépend pas de .
Montrer, sans calculatrice, que est un entier, et le calculer.
Formule du binôme de Newton et sommes de coefficients binomiaux
Soit . On utilise la formule du binôme sous la forme
Calculer chacune des sommes suivantes ; à la question c, l'indice parcourt les entiers pairs, puis les entiers impairs, de . Pour chacune, dire quels , et quel exposant on reconnaît, préciser les valeurs de pour lesquelles le résultat est valable, et contrôler le résultat sur une petite valeur de .
a.
b. ()
c. et ()
d.
e. ()
f.
Formule du binôme de Newton et sommes de coefficients binomiaux
Soient un réel et un entier.
a. Démontrer, à l'aide de la formule du binôme, l'inégalité de Bernoulli : .
b. Démontrer de même que, si , on a .
En déduire que pour tout , puis que
Que peut-on en conclure sur la suite ?
Montrer que , sans calculatrice.
On suppose maintenant .
a. Expliquer pourquoi la preuve de la question 1.a ne s'applique plus.
b. Démontrer par récurrence sur que l'inégalité reste vraie.
c. Montrer, par un exemple, que l'inégalité peut être fausse si . Où l'hypothèse a-t-elle servi dans la récurrence ?
Formule du binôme de Newton et sommes de coefficients binomiaux
Dans tout l'exercice, désigne un entier naturel. On dit qu'un entier est multiple de l'entier s'il existe un entier tel que . On n'utilisera que cette définition, la formule du binôme et le fait que les coefficients binomiaux sont des entiers.
Montrer que est un multiple de . On pourra écrire .
Montrer que est un multiple de . Qu'en déduit-on sur le chiffre des unités de ?
Calculer , puis montrer que l'écriture décimale de se termine par les deux chiffres et , dans cet ordre.
Montrer que est un entier pair.
Montrer que est un multiple de . On pourra écrire et .
Vérifier les résultats des questions 1, 2, 4 et 5 pour , , .
Formule du crible (inclusion-exclusion)Principe additif : réunion disjointe, partition, complémentaire, réunion de deux ensembles
On note , et , , les ensembles des éléments de qui sont multiples de , de et de respectivement. On rappelle que le nombre de multiples d'un entier dans est .
Soient et deux entiers naturels non nuls pour lesquels il existe deux entiers relatifs et tels que . Montrer qu'un entier est multiple de et de si et seulement s'il est multiple de .
En déduire, en exhibant chaque fois et , qu'un entier est multiple de et de si et seulement s'il est multiple de , puis traiter de même les couples , et .
Calculer , , , puis les cardinaux de , , et .
Combien d'éléments de sont multiples de , de ou de ?
Combien d'éléments de ne sont multiples d'aucun de ces trois nombres ?
Combien de mots de longueur , écrits avec les lettres , , , contiennent chacune des trois lettres au moins une fois ? On pourra compter d'abord les mots auxquels il manque au moins une lettre.
Formule du crible (inclusion-exclusion)Formule du binôme de Newton et sommes de coefficients binomiaux
Remarque
Selon les facs. La formule du crible à deux et trois ensembles fait partie du socle commun aux facs ; la formule pour ensembles quelconques figure dans une partie des maquettes seulement. Cet exercice la démontre de deux façons.
Soient des parties finies d'un ensemble, avec . Pour toute partie non vide de , on note
l'ensemble des éléments qui appartiennent à tous les pour . La formule du crible affirme que
Un lemme. Démontrer que, pour tout entier ,
Première preuve. Notons et, pour , .
a. Montrer que, pour toute partie non vide de , est égal au nombre d'éléments de tels que .
b. En déduire la formule du crible en calculant, pour chaque , le nombre de fois que est compté par le membre de droite, avec son signe.
Écrire la formule du crible pour , en regroupant les parties selon leur cardinal. Combien de termes comporte-t-elle ?
Seconde preuve, par récurrence sur . On admet la formule pour deux ensembles. On suppose la formule vraie pour toute famille de parties finies, et l'on considère . Appliquer la formule à deux ensembles à et , puis la formule pour ensembles à deux familles bien choisies, et conclure.
Application. Combien d'entiers de ne sont multiples d'aucun des nombres , , , ? On admettra qu'un entier est multiple de plusieurs nombres premiers distincts si et seulement s'il est multiple de leur produit (chapitre « Arithmétique dans Z »).
Surjections, partitions d'un ensemble, nombres de Stirling de seconde espèce, dérangementsFormule du crible (inclusion-exclusion)
Remarque
Selon les facs. Le dénombrement des surjections figure dans une partie des maquettes seulement. Les questions 1 et 2 n'utilisent que le passage au complémentaire et le crible à trois ensembles, qui font partie du socle commun ; la question 3 utilise le crible pour ensembles (exercice 22).
Soit un entier. Pour , on note le nombre d'applications surjectives de sur .
Montrer que , en passant au complémentaire.
Montrer que , à l'aide de la formule du crible.
Soit . Pour , on note l'ensemble des applications de dans qui ne prennent pas la valeur . Montrer que
Contrôles.
a. Calculer par la formule, et retrouver le résultat sans elle.
b. Calculer par la formule, et expliquer le résultat.
c. Calculer . On distribue cadeaux distincts à enfants, chaque cadeau étant donné à un seul enfant. De combien de façons peut-on le faire de sorte que chaque enfant reçoive au moins un cadeau ? Retrouver ce nombre par un dénombrement direct.
Surjections, partitions d'un ensemble, nombres de Stirling de seconde espèce, dérangementsFormule du crible (inclusion-exclusion)
Remarque
Selon les facs. Les dérangements figurent dans une partie des maquettes seulement ; l'exercice n'utilise que la formule du crible (exercice 22) et le dénombrement des permutations.
Les personnes d'une soirée, numérotées de à , ont déposé leur manteau au vestiaire ; le manteau numéro est celui de la personne . À la sortie, le vestiaire rend un manteau à chaque personne, chaque manteau à une seule personne. Une restitution est donc une permutation : la personne reçoit le manteau . On dit que est un point fixe de si , et que est un dérangement si elle n'a aucun point fixe : personne ne récupère son propre manteau. On note le nombre de dérangements de , et l'on pose .
Déterminer , et , en énumérant pour les six permutations de .
Pour , on note l'ensemble des permutations telles que .
a. Soit une partie de à éléments, . Montrer que l'ensemble a éléments.
b. En déduire, à l'aide de la formule du crible, que pour
Calculer , et .
Soit . En classant les dérangements de selon la valeur , puis selon que ou non, démontrer que
Contrôler la relation sur les valeurs des questions 1 et 3.
Soit . Montrer que le nombre de permutations de ayant exactement points fixes est . Contrôler sur , en vérifiant que la somme de ces nombres pour allant de à vaut .
Rédiger un dénombrement : choisir le modèle, ordre ou pas ordre, ne pas compter deux foisCombinaisons, parties à p éléments, coefficients binomiauxPrincipe additif : réunion disjointe, partition, complémentaire, réunion de deux ensembles
Les quatre textes ci-dessous sont des dénombrements rédigés tels qu'on les lit sur une copie, lignes numérotées. Pour chacun, répondre aux quatre questions suivantes.
Attention : l'une des quatre copies est entièrement juste. Savoir le reconnaître, et dire pourquoi, fait partie du travail.
On rappelle qu'un jeu de cartes comporte quatre couleurs (cœur, carreau, trèfle, pique) de cartes chacune, dont un as par couleur, et qu'une main de cartes est une partie à éléments de l'ensemble des cartes.
(a) Question traitée : combien de mains de cartes d'un jeu de cartes contiennent au moins un as ?
(b) Question traitée : une association compte femmes et hommes. Combien de comités de personnes comprennent au moins une femme et au moins un homme ?
(c) Question traitée : six amis, Alix, Basile, Chloé, Dorian, Emma et Farid, se répartissent en trois binômes pour une course d'orientation. Les binômes ne portent ni nom ni numéro : une répartition est seulement la donnée de qui court avec qui. Combien y a-t-il de répartitions ?
(d) Question traitée : combien de mots de lettres, écrits avec l'alphabet de lettres et pas forcément présents dans le dictionnaire, contiennent exactement deux fois la lettre A ?
Rédiger un dénombrement : choisir le modèle, ordre ou pas ordre, ne pas compter deux foisPrincipe multiplicatif : produit cartésien, choix successifs, lemme des bergersArrangements et nombre d'injections
Les quatre textes ci-dessous sont des dénombrements rédigés tels qu'on les lit sur une copie, lignes numérotées. Pour chacun, répondre aux quatre questions suivantes.
Un entier « de chiffres » est un entier de : son chiffre des centaines n'est pas nul.
(a) Question traitée : combien d'entiers de chiffres sont pairs et ont leurs trois chiffres deux à deux distincts ?
(b) Question traitée : un club de adhérents désigne représentants, sans distinction de rôle, pour une assemblée. Combien y a-t-il de désignations possibles ?
(c) Question traitée : de combien de façons peut-on placer tours identiques sur un échiquier de cases, au plus une tour par case, de sorte que deux tours ne soient jamais sur une même ligne ni sur une même colonne ?
(d) Question traitée : combien d'entiers de chiffres ont leurs chiffres strictement croissants de gauche à droite, comme ?
Double comptage, preuves combinatoires d'identités, formule de VandermondeCombinaisons, parties à p éléments, coefficients binomiaux
Remarque
Selon les facs. La formule de Vandermonde et, plus largement, le double comptage comme méthode de démonstration sont traités en L1 dans certaines maquettes, en deuxième année dans d'autres. Ils ne demandent ici rien d'autre que les coefficients binomiaux et le principe additif.
Dans tout l'exercice, , , et sont des entiers naturels, et l'on rappelle la convention lorsque ou .
Un laboratoire compte mathématiciennes et physiciens, soit personnes. En comptant de deux façons les comités de personnes, démontrer la formule de Vandermonde :
Vérifier la formule pour , , en écrivant tous les comités.
En déduire que, pour tout ,
Contrôler l'égalité de la question 2 pour .
Seconde preuve. En développant de deux façons pour réel, retrouver la formule de Vandermonde. On admettra que deux fonctions polynomiales égales sur ont les mêmes coefficients (chapitre « Polynômes et fractions rationnelles »).
Soit .
a. À l'aide de la formule du pivot , puis de la formule de Vandermonde, démontrer que
b. Contrôler pour .
c. Retrouver cette égalité par un argument combinatoire, en comptant des comités de personnes, formés dans un laboratoire de mathématiciennes et physiciens, et dotés d'une présidente choisie parmi les mathématiciennes du comité.
Double comptage, preuves combinatoires d'identités, formule de VandermondePrincipe multiplicatif : produit cartésien, choix successifs, lemme des bergers
Remarque
Selon les facs. Le double comptage comme méthode de démonstration est enseigné en L1 dans certaines maquettes, en deuxième année dans d'autres. Il repose uniquement sur le principe additif.
On utilisera le principe du double comptage : si et sont deux ensembles finis et une partie de , alors
Dans les questions 1, 2 et 5, est un ensemble fini de cardinal .
En comptant de deux façons les couples tels que , démontrer que
De même, démontrer que
Un club de membres organise des ateliers. Chaque atelier réunit exactement membres, et chaque membre participe à exactement ateliers. Combien y a-t-il d'ateliers ? Montrer qu'une telle organisation existe.
Peut-on organiser de même un club de membres, avec des ateliers de membres, chaque membre participant à exactement ateliers ? Donner une condition nécessaire générale pour membres, des ateliers de membres et ateliers par membre.
Contrôles. Vérifier les formules des questions 1 et 2 pour en écrivant toutes les parties de . Pour , vérifier la question 1 en classant les parties selon leur cardinal, et la question 2 en classant les couples selon le cardinal de .
Principe des tiroirs et sa forme généralisée
Remarque
Selon les facs. La forme générale du principe des tiroirs (pas d'injection d'un ensemble fini dans un ensemble de cardinal strictement plus petit) est démontrée dans le chapitre « Logique, raisonnement, ensembles et applications ». La forme généralisée, utilisée en (c), figure dans certaines maquettes de L1 seulement.
On utilisera les deux formes suivantes. Soient et deux ensembles finis et une application.
Dans chaque situation, on nommera l'application utilisée, son ensemble de départ et son ensemble d'arrivée, avant d'invoquer le principe.
(a) On place cinq points dans un carré de côté , bords compris. Montrer que deux d'entre eux sont à une distance inférieure ou égale à . Peut-on remplacer par un nombre strictement plus petit ?
(b) Soit . Montrer que, parmi entiers distincts de , deux sont consécutifs. Est-ce encore vrai pour entiers distincts ?
(c) Démontrer la forme généralisée ci-dessus. En déduire que, dans un amphithéâtre de étudiants, au moins sont nés le même mois. Montrer que l'on ne peut pas remplacer par .
(d) Soit . On admet que tout entier s'écrit d'une unique façon avec et impair (on obtient en divisant par tant que c'est possible). Montrer que, parmi entiers distincts de , l'un divise un autre. Est-ce encore vrai pour entiers distincts ?
Principe des tiroirs et sa forme généraliséeListes, nombre d'applications et nombre de parties d'un ensemble fini
On se donne dix entiers deux à deux distincts de , et l'on note l'ensemble qu'ils forment. Pour une partie de , on note la somme des éléments de , avec la convention .
Combien a-t-il de parties non vides ? Montrer que, pour toute partie non vide de , on a .
En déduire qu'il existe deux parties non vides et distinctes de qui ont la même somme.
Montrer qu'il existe deux parties non vides et disjointes de qui ont la même somme.
Un exemple. Pour , exhiber deux telles parties. La démonstration des questions 2 et 3 aide-t-elle à les trouver ?
Et avec moins d'entiers ?
a. Le raisonnement des questions 1 et 2 s'applique-t-il tel quel à neuf entiers distincts de ? Que peut-on en conclure ?
b. Montrer qu'il s'applique à neuf entiers distincts de , et pas au-delà de .
c. Montrer que la conclusion de la question 3 est fausse pour les sept entiers de .
Combinaisons, parties à p éléments, coefficients binomiauxCardinal d'un ensemble fini, bijection et cardinal, comparaison des cardinaux
Remarque
Selon les facs. Les chemins dans un quadrillage et les combinaisons avec répétition (la méthode dite « des étoiles et des barres ») sont traités en L1 dans certaines maquettes, en deuxième année dans d'autres, parfois seulement en exercice. Rien ici ne sort des outils du chapitre : tout repose sur une bijection avec des mots, comptés par un coefficient binomial.
Soient et deux entiers naturels. Un chemin de à est une suite finie de points du plan telle que chaque pas soit égal à (un pas vers la droite) ou à (un pas vers le haut). Montrer que tout chemin de à a exactement pas, puis que le nombre de ces chemins est , en construisant une bijection avec un ensemble de mots. Contrôler pour , .
Soient et . On note l'ensemble des -listes telles que . On appelle mot d'étoiles et de barres un mot de longueur formé de lettres et de lettres . Construire une bijection explicite entre et l'ensemble de ces mots, et en déduire
Contrôler pour , en écrivant les solutions.
On distribue bonbons identiques à enfants. Combien y a-t-il de distributions ? Combien y en a-t-il dans lesquelles chaque enfant reçoit au moins un bonbon ?
Construire une bijection entre les chemins de à et l'ensemble , en considérant, pour chaque hauteur, le nombre de pas vers la droite effectués à cette hauteur. Retrouver ainsi le résultat de la question 2 à partir de celui de la question 1.
Un sac contient des boules de couleurs, au moins boules de chaque couleur, deux boules de même couleur étant indiscernables. De combien de façons peut-on choisir boules, plusieurs pouvant être de la même couleur ? Contrôler le résultat par une disjonction de cas selon le nombre de couleurs représentées.
Surjections, partitions d'un ensemble, nombres de Stirling de seconde espèce, dérangementsDouble comptage, preuves combinatoires d'identités, formule de VandermondePrincipe multiplicatif : produit cartésien, choix successifs, lemme des bergers
Remarque
Selon les facs. Les partitions d'un ensemble fini, les nombres de Stirling de seconde espèce et les nombres de Bell figurent dans certaines maquettes de L1, souvent en lien avec le nombre de surjections ; d'autres les réservent au cours de combinatoire de deuxième année. L'exercice n'utilise que les principes additif et multiplicatif, le lemme des bergers et les coefficients binomiaux.
Une partition d'un ensemble est un ensemble de parties de , appelées ses blocs, qui sont non vides, deux à deux disjointes, et de réunion . Les blocs ne sont pas ordonnés : une partition est un ensemble de blocs, pas une liste. Pour des entiers et , on note le nombre de partitions de en blocs (nombre de Stirling de seconde espèce), avec si .
a. Écrire toutes les partitions de , et en déduire , et .
b. Calculer et pour .
c. Montrer que pour .
d. Montrer que pour .
Soient . Montrer, à l'aide du lemme des bergers appliqué à l'application qui associe à une surjection la partition de formée de ses fibres , que le nombre de surjections de sur est . Contrôler avec , .
Soient et . En distinguant les partitions selon que est un bloc ou non, démontrer la relation
Dresser la table des pour . Le nombre de Bell est le nombre de partitions de , tous nombres de blocs confondus. Exprimer à l'aide des , et calculer .
Soient et . On convient que lorsque . En classant les applications de dans selon leur image, démontrer que
Contrôler pour , , puis pour , .
Listes, nombre d'applications et nombre de parties d'un ensemble finiFormule du binôme de Newton et sommes de coefficients binomiauxFormule du crible (inclusion-exclusion)Double comptage, preuves combinatoires d'identités, formule de Vandermonde
Remarque
Selon les facs. La seconde méthode de la question 6 utilise la formule du crible pour un nombre quelconque d'ensembles, que certaines maquettes limitent à trois ensembles, et la question 2 un double comptage. Ces deux passages sont des contrôles : le reste de l'exercice ne repose que sur des bijections et sur la formule du binôme.
Dans tout l'exercice, est un ensemble fini de cardinal , et un entier supérieur ou égal à . Chaque résultat sera contrôlé pour ou .
On note l'ensemble des couples tels que .
a. Construire une bijection de sur , et en déduire .
b. Retrouver ce résultat en classant les couples selon le cardinal de , puis en utilisant la formule du binôme.
Double comptage. Calculer de deux façons : en comptant les triplets tels que et ; puis à l'aide de la question 1.b, de la formule du pivot et de la formule du binôme.
Dénombrer les couples tels que , puis ceux tels que , en se ramenant chaque fois à la question 1 par une bijection.
Dénombrer les -listes de parties de telles que .
Dénombrer les couples tels que .
Dénombrer les -listes de parties de telles que , d'abord directement, puis par la formule du crible et la formule du binôme.
Dénombrer les -listes de parties de telles que et . Que donne le résultat pour et pour ?
On peut le travailler ensemble dès cette semaine. Une séance ciblée sur ce chapitre, et vous repartez au minimum avec une méthode.