30 connectés 3741 membres
Recherche :
Historique des modifications de ce cours:
Dernière version du 05.08.2008 18h15
1 Mise en place d'une base essentielle : les entiers naturels 1.1 Une relation d'équivalence entre ensembles finis 1.1.1 Les entiers naturels 1.1.2 Addition des entiers naturels 1.1.3 Multiplication des entiers naturels 1.1.4 Multiplication de plusieurs entiers naturels 1.1.5 "Principe de multiplication" 2 Réunion et intersection 3 Applications d'un ensemble fini vers un autre 4 Nombre d'injections d'un ensemble fini ''dans'' un autre 5 Nombre de bijections d'un ensemble fini dans un autre (de même cardinal) 6 Nombre de parties à p éléments dans un ensemble à n éléments 7 Nombre de parties d'un ensemble fini 7.1 Relation entre les coefficients binômiaux et le nombre de parties d'un ensemble 7.2 Formule du binôme de Newton 7.3 Remarque 7.4 Une propriété intéressante des coefficients binômiaux ; triangle de Pascal 8 Formule du multinôme de Newton
Nous allons mettre au point quelques méthodes pour compter des objets : éléments d'un ensemble défini d'une certaine façon. Mise en garde : il est bon, pour profiter intégralement de ce cours, d'avoir vu au moins un cours élémentaire sur les Ensembles puis les Relations, et souhaitable d'être initié à la Logique élémentaire (Ce n'est pas bien long).
On considérera dans cette leçon des ensembles finis, c'est-à-dire dont on peut épuiser les élémens en les comptant. On les notera (aucun élément), (un élément), (deux éléments),...
On peut définir une relation eq (équipotence) entre ensembles finis : s'il existe une bijection de sur , c'est-à-dire une application telle que tout élément de ait une et une seule élément dans , et tout élément de ait un et un seul antécédent dans . Les Anglo-Saxons désignent une bijection par "one-to-one mapping", ce qui est tout-à-fait éclairant. Il est clair que si l'on peut se faire correspondre les éléments des deux ensembles un-à-un et dans les deux sens, ces ensembles ont même nombre d'éléments. Le nombre d'éléments d'un ensemble sera appelé cardinal de cet ensemble : Cette relation est une relation d'équivalence, en effet :
Les classes d'équivalence seront appelées entiers naturels. Ainsi, la classe de est appelée 0, La classe de sera appelée 1, La classe de sera appelée 2,... L'ensemble des classes obtenu sera appelé (ensemble des entiers naturels). Lui par contre est un ensemble infini.
Nous définirons l'addition des entiers naturels de la façon suivante : Si et sont disjoints (), alors on posera Exemple On aura par exemple On aura ainsi initié l'écriture On retiendra le principe à l'origine de l'addition dans :
Soient deux ensembles finis On définira le produit des entiers naturels comme le cardinal de leur produit cartésien : Si , on aura Exemple Si , alors les éléments de peuvent être rangés dans un tableau rectangulaire :
Il y a bien couples en tout dans . Remarque On peut définir la multiplication de manière alternative, et cela nous servira dans certains cas : (lire ou penser : "n fois p = p + p +...+ p avec n termes")
On peut définir un triplet comme la donnée d'un premier objet, d'un second et d'un troisième ; on le note . Si sont trois ensembles finis, l'ensemble des triplets , où , est le produit cartésien : Le nombre d'éléments de est, on le voit en classant les triplets en ordre, le produit des cardinaux de : Si , cela donne et cela se généralise en et en
Je distribue des feuilles documentaires à une classe de 25 élèves. Etant donné que je donne 3 feuilles à chaque élève, combien de feuilles ont été distribuées en tout ? Le principe consiste à dire : Tout élève reçoit 3 feuilles. Il y a 25 élèves. Donc il y a en tout feuilles. Exemple 1) J'ai un jeu de cartes courant de 32 cartes. On tire simultanément deux cartes. Combien y a-t-il de tirages où l'on obtient un roi et une dame ? Combien y a-t-il de tirages où l'on obtient une figure (roi, dame ou valet) et une carte qui n'est pas une figure ?) Solution : (1) Parmi mes deux cartes, il y a un roi. Il y a 4 possibilités de tirer un roi. Or à chaque fois que j'obtiens un roi, je peux tirer aussi l'une des quatre dames, j'ai donc 4 possibilités de tirer une dame. En tout, cela fait tirages où l'on obtient un roi et une dame. Attention, on a considéré un tirage comme un couple , où est un roi et est une dame. Pourtant les cartes ont été tirées simultanément; il n'y a pas de "premier" ou de "deuxième" au sens temporel (tiré avant, tiré après). C'est simplement la nature : roi ou dame, qui détermine le couple (qui est défini comme élément de ). 2) Si l'on considérait un tirage où l'on tire une première carte puis une seconde, et où l'on tient lieu de l'ordre des résultats, c'est différent : la première carte tirée est l'une des 8 cartes de l'ensemble , la seconde l'une des 4 cartes de genre différent (dame si c'est un roi, roi si c'est une dame). Cela donne possibilités en tout. C'est difficile à imaginer, mais on peut lister les tirages différents : R de carreau, D de carreau R de carreau, D de coeur R de carreau, D de pique R de carreau, D de trèfle R de coeur, D de carreau R de coeur, D de coeur R de coeur, D de pique R de coeur, D de trèfle R de pique, D de carreau R de pique, D de coeur R de pique, D de pique R de pique, D de trèfle R de trèfle, D de carreau R de trèfle, D de coeur R de trèfle, D de pique R de trèfle, D de trèfle Ce qui fait 16 tirages différents, auxquels il y a à ajouter les 16 tirages où les dames sont tirées en premier et les rois en second.
Soient deux ensembles quelconques. Alors on a dans le cas général : Preuve On peut écrire , ce qui définit comme réunion de deux ensembles disjoints : et . En effet, si , soit il appartient à , soit il appartient à sans appartenir à , c'est-à-dire . On peut donc écrire D'autre part, on peut écrire , où et sont disjoints (l'un contient des élément qui ne sont pas dans , l'autre des éléments qui y sont) On a donc En tout, en éliminant dans les deux égalités trouvées, on obtient : Exemple simple Dans une classe de 30 élèves, il y a 14 anglicistes, 8 germanistes, et deux élèves étudient à la fois l'anglais et l'allemand. Combien d'élèves étudient au moins l'une de ces deux langues ? Combien n'étudient aucune de ces deux langues ? Solution : Soit la classe, les ensembles des anglicistes et de germanistes. Le nombre d'élèves étudiant au moins l'une de ces deux langues est soit 14 + 8 - 2 = 20. Le nombre d'élèves n'étudiant aucune de ces deux langues est Exercice Montrer que pour trois ensembles quelconques, on a
Soit , où sont des ensembles finis. On note l'ensemble des applications de vers . (lire : puissance ) Le nombre d'applications de vers est : En effet, Supposons que . Appelons les éléments de : Définir une application , c'est tout simplement choisir dans , dans cet ordre. Ce qui revient à définir un p-uplet Comme , . Ce qui veut dire qu'il y a applications différentes de dans . Exemple J'ai 10 chemises et une commode à 4 tiroirs. Combien ai-je de façons possibles de ranger mes chemises dans cette commode ? Solution : Chaque chemise va dans un et un seul tiroir. Un rangement est donc une application de l'ensemble des chemises vers l'ensemble des tiroirs. Il y a donc façons de ranger les dix chemises dans quatre tiroirs. (attention, aucune chemise ne reste à l'extérieur de la commode à l'issue d'un rangement !)
Soient deux ensembles, avec Le nombre d'injections de dans est le produit de facteurs On le note et on l'appelle souvent nombre d'arrangements de objets pris dans un ensemble de objets. Définition Si , on pose (factorielle ) On posera aussi et Cette définition garantit qu'on aura toujours Alors, on peut exprimer autrement Preuve Soit Pour définir une injection , il suffit de définir les éléments de , Pour définir il y a choix possibles. A chacun de ces choix, on peut faire correspondre choix possibles pour , puisque l'on doit avoir . Le principe de multiplication nous indique qu'il y a donc manières de définir En continuant jusqu'au bout, on trouve que le nombre de manières de définir est , soit (vérifier que cela fait bien facteurs). Exemples 1) 0≠1≠1 ; 2! = 2 ; 3! = 6 ; 4! = 24 ; 5! = 120 ... 2) (se rappeler : "4 facteurs") ou 3) Quel est le nombre de jeux possibles au tiercé lorsqu'il y a 23 chevaux au départ (on n'admet pas d'ex aequo) ? Un "jeu" possible au tiercé est la donnée d'un premier cheval, d'un deuxième et d'un troisième dans cet ordre. Cela revient bien à définir une injection de dans l'ensemble des chevaux. En effet, chaque rang d'arrivée, 1,2 ou 3 correspond à un et un seul cheval, et deux rangs différents correspondent à deux chevaux différents (donc injection)... Le nombre de jeux possibles, ou d'arrivées a priori possibles, est donc
Soient deux ensembles finis tels que Alors toutes les injections de dans sont automatiquement surjectives. En effet, les éléments de ont images distinctes dans , ce qui remplit totalement . Le nombre de bijections de dans n'est donc rien d'autre que le produit des entiers . Le cas où ne change rien à ce résultat. On retiendra : Le nombre de bijections de dans un ensemble de même cardinal est On dit aussi que le nombre de permutations de objets est . Exemples 1) On organise un banquet avec 20 convives, et 20 places qui leur sont réservées. Combien y a-t-il de manières de placer les convives ? Solution : un "placement" des convives est une bijection de (ensemble des convives) dans (ensemble des places). Il y a donc 20! manières de les placer de façons différentes, ce qui donne le nombre astronomique de 2 432 902 008 176 640 000 (plus de 2 milliards et milliards !) 2) Même question, mais on n'a que 9 convives et une table ronde dans une salle ronde ou presque... Cette fois, si l'on faisait tourner tous les convives d'une place sur leur droite, par exemple, ils ne s'apercevraient pas de la différence, parce que la seule chose qui aurait pu compter est leur disposition par rapport aux autres convives. On peut donc placer, disons le premier convive arrivé, n'importe où, puis placer les 8 autres par rapport à lui. On a donc une bijection d'un ensemble de 8 personnes sur un ensemble de 8 places, donc 8! possibilités, soit 40 320. 3) Même question, mais on veut que M. X soit à côté de Mlle Y. Solution : on place M. X n'importe où, puis on place Mlle Y à côté de lui (2 possibilités), puis on place les 7 autres convives. D'après le principe de multiplication, cela fait possibilités, soit 10 080. 4) Même question, mais on veut que M. X soit à côté de Mlle Y, et Mme Z à côté d'aucun d'eux ! Solution : On place M. X, puis Mlle Y à côté de lui, puis Mme Z dans les 9-4=5 places "possibles", et enfin les 6 autres convives dans les 6 places restantes. Cela fait possibilités.
Si , le nombre de parties à éléments dans un ensemble à éléments est le quotient d'un produit de facteurs par un autre produit de facteurs : soit ou Au lieu de , certains notent On appelle aussi ce nombre "nombre de combinaisons de p objets pris dans un ensemble de n éléments". Preuve Comment définir une partie à éléments dans un ensemble à éléments ? On peut considérer une injection de dans , parce que cette injection définit éléments de , mais dans un certain ordre : un 1er, un 2e, ..., un p-ième. Le nombre d'injections est donc trop grand pour dénombrer les parties à éléments. Car une même partie de correspondra à injections différentes, obtenues en changeant de toutes les manières possibles l'ordre des images de 1,2,...,p. Donc le nombre de parties à éléments n'est autre que . Exemples 1. On appelle "main" un ensemble de 6 cartes prises dans un jeu de 32 cartes. Le nombre de mains est 2. Quel est le nombre de "mains" contenant un roi, deux valets et 3 cartes qui ne sont pas des figures (figure= roi, dame ou valet) ? On utilise le principe de multiplication : nombre de manières d'obtenir un roi : 4 ; nombre de manières d'obtenir 2 valets sur les 4 existants : ; nombre de manières de choisir 3 cartes qui ne sont pas des figures : . Donc le nombre cherché est .
On peut raisonner par récurrence. Le nombre de parties de l'ensemble vide est 1 : la seule partie de l'ensemble vide est l'ensemble vide lui-même. Maintenant, si je considère un ensemble contenant éléments, et si j'appelle le nombre de ses parties, soit l'ensemble à éléments obtenu en adjoignant à un élément , les parties de sont de deux sortes : soit elles contiennent , soit elles ne le contiennent pas. Si elles ne le contiennent pas, ce ne sont autres que les parties de , et il y en a . Si elles le contiennent, elles sont toutes de forme , avec , donc il y en a aussi . En tout, il y a parties dans On peut écrire et il est aisé de prouver par récurrence que .
La somme de tous les vaut nécessairement le nombre de parties d'un ensemble à éléments :
Pour tout , ce qu'on écrit plus économiquement ou Preuve On veut développer le produit de facteurs Il est prévisible qu'en développant, on obtiendra une somme de termes tous produits de facteurs, par exemple On va les rassembler et additionner les facteurs égaux entre eux, c'est-à-dire contenant le même nombre de facteurs . On peut considérer chaque terme comme le remplissage d'un système de "cases" par des et des : Le nombre de termes contenant facteurs et facteurs est le nombre de choix de cases parmi . C'est donc . Le terme en aura donc pour coefficient , ce qui prouve la formule.
On retrouve une formule écrite plus haut pour le nombre de parties d'un ensemble à éléments : soit
Calculons la somme Calculons aussi Si nous dressions un tableau cartésien de valeurs de où les colonnes figurent les valeurs de et les lignes celles de ,
... nous aurions l'agréable surprise (grâce à la propriété des précédente) de voir que chaque terme du tableau est la somme de celui situé au-dessus de lui et du voisin de gauche de ce dernier. Ce tableau s'appelle triangle de Pascal, en l'honneur du penseur du XVIIe siècle Blaise Pascal. Exemples On peut donc écrire sans effort ou
Elle généralise la formule du binôme de Newton. Pour , (avec ) La preuve est une récurrence sur . On sait que la formule est vraie pour et tout , car elle n'est alors autre que la formule du binôme de Newton : Supposons que cette formule est vraie pour donné et tout ; alors Par hypothèse, ceci vaut qui n'est autre que On peut renommer , et la formule est prouvée. Exemples simples : 1) Développement de : En effet, 2) Coefficient de dans le développement de : Le terme en question est Le coefficient de est donc
Dernière mise à jour: le 05.08.2008 à 19:15 Licence: Libre de partager, modifier - Devoir de citer la source - Pas d'utilisation commerciale Daskoo.org, partage de cours
