Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 03 - Ensembles finis. Problèmes de dénombrement

Dans ce chapitre, nous allons nous focaliser sur les ensembles finis et étudier plusieurs méthodes afin de calculer leurs nombres d'éléments.

Pour finir, nous utiliserons certains de ces résultats afin d'obtenir la célèbre formule du binôme de Newton.

Notion de cardinal

Cette première partie sera consacrée à l'étude de la notion de cardinal, qui n'est ni plus ni moins que le nombre d'éléments d'un ensemble.

Cardinaux finis

Commençons par définir rigoureusement la notion d'ensemble fini même si ce concept est somme toute relativement intuitif.

Définition

Un ensemble E est dit fini s’il existe un entier naturel n et une application bijective de E vers l’ensemble { 1 , 2 , 3 , . . . , n } .

Ce nombre n est alors appelé cardinal de E, et est souvent noté card ( E ) ou | E | .

[Note]

Dans la suite nous privilégierons la notation card ( E ) car elle est plus explicite.

Pour un ensemble fini, le cardinal n'est donc rien d'autre que son nombre d'éléments.

En pratique, la bijection précédente est réalisée en attribuant successivement un numéro à chacun des éléments de l'ensemble E. Le cardinal est alors le dernier entier utilisé. Cette attribution de numéros n’est ni plus ni moins qu’un décompte des éléments.

Example 1.1. Des ensembles finis

L’ensemble de tous les campus SUPINFO International University est fini et son cardinal est égal à 35.

L’ensemble des cartes d’un jeu de tarot est fini et son cardinal est égal à 78.


Cardinaux transfinis

Intéressons nous maintenant aux cas des ensembles qui ne sont pas finis.

[Note]

Cette sous-partie est plus une partie de culture générale, car dans la suite de ce chapitre nous ne considèrerons que des ensembles finis. Mais il est bon quand même d'avoir quelques notions concernant l'infini.

Définition

Si un ensemble n’est pas fini on dit qu’il admet un cardinal infini, ou encore un cardinal transfini.

Il existe plusieurs cardinaux transfinis différents, ce qui signifie moralement qu'il existe des ensembles infinis de "plusieurs tailles".

Le premier cardinal transfini est celui de et des ensembles qui sont bijection avec lui.

Notation et définition

Le cardinal de l’ensemble des entiers naturels est noté 0 .

Tout ensemble en bijection avec l’ensemble des entiers naturels est dit dénombrable.

Le résultat suivant peut surprendre, l'humain ayant une intuition relativement mauvaise à propos de l'infini.

Théorème

Les ensembles et sont dénombrables.

[Note]

Ce résultat signifie en particulier qu'il y a autant d'entiers relatifs que d'entiers naturels, alors que l'on pourrait naïvement penser qu'il y en a le "double", puisque dans il y a les entiers négatifs et les positifs.

Même remarque à propos des rationnels, ceux-ci étant constitués d'un quotient de deux entiers, il est intuitif d'imaginer qu'il y a plus de rationnels que d'entiers naturels. Intuitif mais faux.

Démonstration

Montrons que et sont en bijection.

Soit f l'application définie par

f : n f ( n ) = { n 2 s i   n  est pair ( n + 1 2 ) s i   n  est impair

Montrons tout d'abord que f est injective. Pour cela, considérons deux entiers n et m tels que f ( n ) = f ( m ) . Pour des raisons évidentes de signe, n et m doivent avoir la même parité. S'ils sont tous les deux pairs l'égalité précédente devient n 2 = m 2 et donc n = m . S'ils sont tous les deux impairs cette même égalité se réécrit - ( n + 1 2 ) = - ( m + 1 2 ) , et donc là aussi n = m . L'injectivité de f est donc prouvée.

Montrons maintenant que f est surjective. Soit n . On vérifie facilement que si n 0 , on n = f ( 2 n ) , et que si n < 0 , on a n = f ( - 2 n - 1 ) . Tout élément de a donc un antécédent par f, ce qui prouve que f est surjective.

Puisque f est à la fois injective et surjective, elle est bijective.

Nous laissons au lecteur le soin de prouver la dénombrabilité de . La question est cependant plus délicate.

Il n'est par contre pas possible d'établir une bijection entre l'ensemble des entiers naturels et celui des nombres réels ou complexes.

Théorème

Les ensembles et ne sont pas dénombrables. Ils sont cependant en bijection l'un avec l'autre.

[Note]

Nous admettrons ce théorème, sa preuve sortant du cadre de ce cours. Le lecteur curieux pourra quand même réfléchir à la question.

Terminons cette sous-partie par quelques considérations sur le cardinal de .

Définition

Le cardinal de l’ensemble des nombres réels est noté 2 0 .

Ce cardinal est appelé puissance du continu.

[Note]

En fait 2 0 est plus qu'une notation, on peut lui donner précisément du sens mathématique.

[Note]

L'hypothèse du continu, formulée par Georg Cantor (1845-1918), stipule qu'il n'existe pas d'ensemble dont le cardinal est compris (au sens strict) entre celui de l'ensemble des entiers naturels et celui de l'ensemble des nombres réels.

Cette affirmation est en fait indécidable, c'est-à-dire qu'au vue de la construction usuelle de on ne peut affirmer qu'elle est vraie ou non. Ce dernier résultat fut démontré par Paul J. Cohen (1934-2007), faisant suite aux travaux de Kurt Gödel (1906-1978).

On évoque là des choses réellement délicates.

Propriétés générales sur les cardinaux

Nous allons ici énoncer divers résultats généraux concernant les cardinaux d'ensembles finis.

Formule de Poincaré

La formule suivante porte le nom d'Henri Poincaré (1854-1912) même si elle est en fait due à Abraham de Moivre (1667-1754). On désigne également ce résultat sous l'appellation principe d'inclusion-exclusion.

Formule de Poincaré (cas particuliers)

Soient A et B des ensembles finis.

On a

c a r d ( A B ) = c a r d ( A ) + c a r d ( B ) c a r d ( A B )

Soient A, B et C des ensembles finis.

On a

c a r d ( A B C ) = c a r d ( A ) + c a r d ( B ) + c a r d ( C ) c a r d ( A B ) c a r d ( A C ) c a r d ( B C ) + c a r d ( A B C )

Démonstration

Faisons un diagramme dans le cas de deux ensembles :

En additionnant card ( A ) et card ( B ) il est clair que l'on compte deux fois card ( A B ) . Il faut donc le retrancher une fois pour obtenir card ( A B ) .

L'exemple qui vient permettra de bien fixer les idées, même si ce résultat est relativement simple.

Example 1.2. Application de la formule de Poincaré avec trois ensembles

Dans une promotion de 36 étudiants, 22 maîtrisent le C++, 22 le C# et 18 le Java.

De plus, 10 étudiants maîtrisent à la fois le C++ et le C#, 9 maîtrisent à la fois le C# et le Java, et 11 à la fois le C++ et le Java.

Combien d’étudiants maîtrisent les trois langages de programmation ?

Soit A l’ensemble des étudiants qui maîtrisent le C++, B l’ensemble de ceux qui maîtrisent le C# et C l’ensemble de ceux qui maîtrisent le Java.

On cherche à calculer card ( A B C ) .

Or les hypothèses signifient que card ( A B ) =36, card ( A ) =22, card ( B ) =22, card ( C ) =18, card ( A B ) =10, card ( B C ) =9, card ( A C ) =11.

On utilise alors la formule de Poincaré avec trois ensembles

c a r d ( A B C ) = c a r d ( A ) + c a r d ( B ) + c a r d ( C ) c a r d ( A B ) c a r d ( A C ) c a r d ( B C ) + c a r d ( A B C )

On en déduit facilement que card ( A B C ) =4.


Il est temps de présenter cette formule sous sa forme la plus générale.

Formule de Poincaré (cas général)

Soient A 1 , A 2 ,..., A n des ensembles finis.

On a

c a r d ( i = 1 n A i ) = j = 1 n ( ( 1 ) j 1 I { 1,2 , . . . , n } c a r d ( I ) = j c a r d ( k I A k ) )

Autre formulation

c a r d ( i = 1 n A i ) = j = 1 n ( ( 1 ) j 1 1 i 1 < i 2 < . . . < i j n c a r d ( A i 1 A i 2 . . . A i j ) )
[Note]

Il ne faut pas se laisser impressioner par l'écriture de cette formule. Les cas n = 2 et n = 3 ont déjà été explicités et sont très simples. Quand n > 2 ce n’est pas conceptuellement plus difficile mais juste plus technique.

[Note]

Nous verrons des applications intéressantes de cette formule lors des séances d’exercices.

Cardinal du complémentaire

Le petit résultat qui suit n'est certes pas fondamental mais il se révèle assez utile en pratique.

Propriété

Soit E un ensemble fini et A un sous-ensemble de E.

On a

c a r d ( C E ( A ) ) = c a r d ( E ) c a r d ( A )
[Note]

L'utilité de cette formule provient du fait qu'il est parfois plus simple de déterminer le cardinal du complémentaire d’un sous-ensemble que celui du sous-ensemble lui même.

Démonstration

Il suffit d'appliquer la formule de poincaré aux deux ensembles A et B = C E ( A ) . On a clairement A B = E et A B = . Le résultat en découle.

Principe multiplicatif

La propriété suivante nous permettra de réduire une situation de dénombrement à des situations "plus petites" et donc sans doute plus simple à évaluer.

Propriété

Supposons qu’une expérience puisse se décomposer en p sous-expériences ayant respectivement n 1 , n 2 ,..., n p résultats possibles.

Le nombre total de résultats possibles de l’expérience globale est alors

n = i = 1 p n i = n 1 × n 2 × . . . × n p
[Note]

À la place du mot "expérience" on aurait pu utiliser le mot "situation", et à la place de "sous-expérience" le mot "étapes".

Voici une petite application concrète de ce résultat. Nous l'utiliserons également intensivement dans la seconde partie pour démontrer nos formules de dénombrement.

Example 1.3. Application du principe multiplicatif

Combien de menus peut-on composer si on a le choix entre 3 entrées, 5 plats et 4 desserts ?

On a ici 3 sous-expériences : le choix de l’entrée, puis le choix du plat et enfin le choix du dessert.

D’après le principe multiplicatif on aura donc 3 × 5 × 4 menus possibles, c’est-à-dire 60.


Calculs classiques de dénombrement

Nous allons dans cette partie nous focaliser sur quelques problèmes classiques de dénombrement et étudier leurs résolutions.

Contexte

Les situations auxquelles nous allons nous intéresser sont génériques en ce sens qu’elles se retrouvent dans de multiples contextes différents.

Ce qui les distingue en particulier est la présence ou l’absence d’une notion d’ordre dans leur description. Nous allons vite revenir sur ce point fondamental.

Pour expliciter les concepts, nous allons successivement résoudre les cinq problèmes suivants :

  1. Combien de numéros de téléphone à 8 chiffres peut-on former ?

  2. Quel est le nombre de mots comportant 5 lettres distinctes ? (sans se préoccuper du sens des mots)

  3. De combien de façons peut-on placer un groupe de 5 personnes sur un banc ?

  4. Quel est le nombre d’anagrammes du mot "RATTRAPAGE" ?

  5. Au poker combien de mains existe-t-il ? (une main étant un tirage de 5 cartes)

La notion d'ordre évoquée précédemment concerne la structure des éléments constituant l'ensemble à dénombrer.

Par exemple, deux numéros de téléphones avec les mêmes chiffres mais dans un ordre différent ne sont pas les mêmes. Idem pour deux mots avec les mêmes lettres mais pas dans le même ordre. Dans les quatre premiers de ces problèmes l'ordre importe donc. Ce n'est pas le cas pour le dernier puisque la position des cartes dans la main ne change pas la valeur de celle-ci.

Terminons cette sous-partie par un rappel sur la fonction factorielle, elle nous sera constamment utile dans nos calculs. Pour un entier naturel n, il s'agit du produit des entiers inférieurs ou égaux à n.

Définition

La factorielle d'un entier naturel non nul n est notée n! et est définie par

n ! = n × ( n - 1 ) × . . . × 2 × 1

Par convention, on pose également 0 ! = 1 .

Arrangements

Commençons par la définition générale d'un arrangement.

Définition

Soit E un ensemble fini de cardinal n.

Un arrangement de p éléments de E est une suite ordonnée de p éléments de E.

Il est fondamental de bien comprendre que dans la notion d’arrangement l’ordre des éléments importe. Ainsi deux arrangements de p éléments de E sont différents s’ils ne comportent pas les mêmes éléments, ou s’ils les contiennent mais dans un ordre différent.

Selon que l’on puisse ou non prendre plusieurs fois le même élément dans un arrangement, on distinguera :

  • Les arrangements avec répétitions

  • Les arrangements sans répétitions

Arrangements avec répétitions

Définition

Soit E un ensemble fini de cardinal n.

Un arrangement avec répétitions de p éléments de E est un arrangement de p éléments de E non nécessairement distincts.

On utilise également le terme de p-liste d'éléments de E.

Voici la formule exprimant le nombre d'arrangements avec répétitions dans un ensemble fini.

Nombre d’arrangements avec répétitions

Soit E un ensemble fini de cardinal n.

Le nombre d’arrangements avec répétitions de p éléments de E est égal à n p .

Démonstration

Il faut donc constituer une suite ordonnée de p éléments de E.

Pour le premier élément on a n choix possibles.

Pour le second on a aussi n choix possibles car les répétitions sont autorisées.

Et ainsi de suite.

D’après le principe multiplicatif, on a donc un nombre de possibilités égal à n × n × . . . × n = n p .

Nous pouvons maintenant répondre à la première des cinq questions énoncées dans la sous partie 2.1.

Example 1.4. Arrangements avec répétitions

Combien de numéros de téléphone à 8 chiffres peut-on former ?

Il s'agit clairement d'une situation d'arrangements avec répétitions puisque l'ordre des chiffres importe et qu'un numéro de téléphone peut comporter plusieurs fois le même chiffre.

Avec les notations précédentes, l'ensemble E est constitué des chiffres utilisables pour composer un numéro de téléphone, i.e. E = { 0 , 1 , . . . , 9 } , et on a alors n = card ( E ) = 10 .

On s'intéresse aux arangements avec répétitions de p = 8 éléments de E.

D'après le résultat ci-dessus, il y en a 10 8 .


Arrangements sans répétitions

Définition

Soit E un ensemble fini de cardinal n.

Un arrangement sans répétitions de p éléments de E est un arrangement de p éléments de E tous distincts.

[Note]

Dans un tel cas de figure on a nécessairement p n puisque les répétitions sont interdites.

Voici la formule exprimant le nombre d'arrangements sans répétitions dans un ensemble fini.

Nombre d’arrangements sans répétitions

Soit E un ensemble fini de cardinal n.

Le nombre d’arrangements sans répétitions de p éléments de E se note A n p et est égal à

A n p = n × ( n 1 ) × . . . × ( n p + 1 ) = n ! ( n p ) !

Démonstration

Il faut donc constituer une suite ordonnée de p éléments de E.

Pour le premier élément on a n choix possibles.

Pour le second on a cette fois n - 1 choix possibles car les répétitions ne sont pas autorisées.

Et ainsi de suite.

D’après le principe multiplicatif, on a donc un nombre de possibilités égal à n × ( n - 1 ) × . . . × ( n - p + 1 ) .

égalité des deux expressions ?

Nous pouvons maintenant répondre à la deuxième des cinq questions énoncées dans la sous partie 2.1.

Example 1.5. Arrangements sans répétitions

Quel est le nombre de mots comportant 5 lettres distinctes ? (sans se préoccuper du sens des mots)

Il s'agit clairement d'une situation d'arrangements sans répétitions puisque l'ordre des lettres importe et que l'on requiert qu'elles soient distinctes.

Avec les notations précédentes, l'ensemble E est constitué des lettres de l'alphabet, i.e. E = { a , b , . . . , z } , et on a alors n = card ( E ) = 26 .

On s'intéresse aux arangements sans répétitions de p = 5 éléments de E.

D'après le résultat ci-dessus, il y en a

A 26 5 = 26 × 25 × 24 × 23 × 22 = 7893600

Permutations

La notion de permutation va elle concerner tous les éléments d'un ensemble.

Définition

Soit E un ensemble fini de cardinal n.

Une permutation de E est une suite ordonnée de tous les éléments de E.

[Note]

Autrement dit, une permutation de E est un arrangement des n éléments de E.

Comme dans le cas des arrangements, l’ordre des éléments importe dans une permutation. Deux permutations de E sont ainsi différentes uniquement si l’ordre des éléments n’est pas le même dans chacune d’elles.

Selon que les éléments de l’ensemble que l’on permute soient tous différents ou pas, on distinguera :

  • Les permutations sans répétitions

  • Les permutations avec répétitions

[Note]

Un ensemble dont tous les éléments ne sont pas distincts n'est pas stricto sensu un ensemble tel qu'on l'a défini dans le chapitre 2. On devrait plus exactement parler de multi-ensemble.

Par soucis de simplicité, nous ne ferons pas cette distinction et nous n'utiliserons que le terme d'ensemble. Que le lecteur nous pardonne cette imprécision.

Permutations sans répétitions

Définition

Soit E un ensemble fini de cardinal n dont tous les éléments sont distincts.

Une permutation de E est alors dite une permutation sans répétitions.

Voici la formule exprimant le nombre de permutations sans répétitions d'un ensemble fini.

Nombre de permutations sans répétitions

Soit E un ensemble fini de cardinal n dont tous les éléments sont distincts.

Le nombre de permutations sans répétitions de E est égal à n!.

Démonstration

Une permutation sans répétitions n’est rien d’autre qu’un arrangement de n éléments d’un ensemble comportant n éléments. D'après le résultat de la sous-partie 2.2.2, le nombre de permutations sans répétitions vaut donc n × ( n - 1 ) × . . . × ( n - p + 1 ) avec p = n , c'est-à-dire n × ( n - 1 ) × . . . × ( n - n + 1 ) =n!. Q.E.D.

Nous pouvons maintenant répondre à la troisième des cinq questions énoncées dans la sous partie 2.1.

Example 1.6. Permutations sans répétitions

De combien de façons peut-on placer un groupe de 5 personnes sur un banc ?

Il s'agit clairement d'une situation de permutations sans répétitions puisque l'ordre des personnes importe et que l'on souhaite qu'elles soient toutes sur le banc.

Avec les notations précédentes, l'ensemble E est constitué de ces 5 personnes et on a alors n = card ( E ) = 5 .

D'après le résultat ci-dessus, le nombre cherché est 5 ! = 120 .


Permutations avec répétitions

Définition

Soit E un ensemble fini de cardinal n dont tous les éléments ne sont pas distincts.

Une permutation de E est alors dite une permutation avec répétitions.

Voici la formule exprimant le nombre de permutations avec répétitions d'un ensemble fini.

Nombre de permutations avec répétitions

Soit E un ensemble fini de cardinal n dont tous les éléments ne sont pas distincts.

On suppose qu'il y a r éléments distincts, et que le premier élément est présent k 1 fois, le second k 2 fois, etc. On a donc k 1 + k 2 + . . . + k r = n .

Le nombre de permutations avec répétitions de E est égal à

n ! k 1 ! × k 2 ! × . . . × k r !

Démonstration

Si tous les éléments de E étaient distincts il y aurait n! permutations.

Comme le premier élément est présent k 1 fois, il faut diviser ce nombre par k 1 !.

De même comme le second élément est présent k 2 fois, il faut le diviser par k 2 !.

Et ainsi de suite.

D’ou un nombre de permutations avec répétitions égal à

n ! k 1 ! × k 2 ! × . . . × k r !

Nous pouvons maintenant répondre à la quatrième des cinq questions énoncées dans la sous partie 2.1.

Example 1.7. Permutations avec répétitions

Quel est le nombre d’anagrammes du mot "RATTRAPAGE" ?

Il s'agit clairement d'une situation de permutations avec répétitions puisque l'ordre des lettres importe et qu'elles ne sont pas toutes différentes.

Avec les notations précédentes, l'ensemble E est constitué des lettres R, A, T, P, G et E, chacune d'elles apparaissant autant de fois que leur occurrence dans le mot "RATTRAPAGE". On a donc E = { R , R , A , A , A , T , T , P , G , E } , n = card ( E ) = 10 , r = 6 , k 1 =2, k 2 =3, k 3 =2, k 4 =1, k 5 =1, et k 6 =1.

D'après le résultat ci-dessus, le nombre cherché est

10 ! 2 ! × 3 ! × 2 ! = 151200

Combinaisons

Le concept de combinaison diffère des précédents principalement par l'absence de notion d'ordre.

Définition

Soit E un ensemble fini de cardinal n.

Une combinaison de p éléments de E est un sous-ensemble de p éléments de E.

[Note]

Dans un tel cas de figure on a donc nécessairement p n .

Il est fondamental de bien comprendre que dans la notion de combinaison l’ordre des éléments n’importe pas. Ainsi deux combinaisons de p éléments de E sont différentes uniquement si elles ne comportent pas les mêmes éléments.

La formule suivante donne

Nombre de combinaisons

Soit E un ensemble fini de cardinal n.

Le nombre de combinaisons de p éléments de E se note ( n p ) (ou parfois C n p ) et est égal à

( n p ) = n ! p ! ( n p ) !
[Note]

La première notation est la notation anglo-saxonne, la plus utilisée aujourd’hui, et la seconde la notation française, de plus en plus délaissée.

Démonstration

Pour chaque sous-ensemble de p éléments de E, il y a p! façons d’ordonner ses p éléments. Il s’agit en effet du nombre de permutations sans répétitions d’un ensemble de p éléments.

Le nombre d'arrangements sans répétitions de p éléments de E est donc égal au nombre de sous-ensemble de p éléments de E multiplié par p!. Ainsi

A n p = p ! × ( n p )

D'où

( n p ) = A n p p !

Q.E.D.

Nous pouvons maintenant répondre à la cinquième et dernière des questions énoncées dans la sous partie 2.1.

Example 1.8. Combinaisons

Au poker combien de mains existe-t-il ? (une main étant un tirage de 5 cartes)

Avec les notations précédentes, l'ensemble E est constitué des cartes du jeu de poker et on a alors n = card ( E ) = 52 .

Il s'agit clairement d'une situation de combinaisons puisqu'une main est en fait un sous-ensemble de p = 5 éléments de E. Il n'y a en effet pas de notion d'ordre des cartes dans la main.

D'après le résultat ci-dessus, le nombre cherché est

( 52 5 ) = 2598960

[Note]

On peut aussi définir la notion de combinaison avec répétitions mais ses applications sont assez rares et la formule de dénombrement difficile à obtenir. Nous laisserons donc ce concept de côté.

Terminons cette sous-partie par un peu de vocabulaire.

Définition

Les quantités ( n p ) pour n et 0 p n sont appelées coefficients binomiaux.

[Note]

Le choix de ce terme prendra tout sens lors de la troisième partie.

Synthèse

Récapitulons un peu ce que l'on a vu dans les sous-parties précédentes en présentant les différentes questions que l'on doit se poser lorsque l'on est confronté à un problème de dénombrement. Cela nous permettra de savoir choisir le concept à utiliser en fonction de la situation.

  1. L’ordre des éléments est-il important ?

    • Si oui il s’agit d’arrangements ou de permutations.

    • Si non il s’agit de combinaisons.

  2. Si l’ordre importe, est-ce que tous les éléments sont utilisés ?

    • Si non il s’agit d’arrangements.

    • Si oui il s’agit de permutations.

  3. Les répétitions sont-elles ou non autorisées ?

Nous pouvons représenter par un arbre de décision ces différentes alternatives.

Figure 1.1. Savoir choisir entre arrangement, permutation et combinaison

Savoir choisir entre arrangement, permutation et combinaison

Si un problème ne correspond à aucunes des situations précédentes, il faudra le résoudre en utilisant des techniques plus générales, comme la formule de Poincaré ou le principe multiplicatif.

Formule du binôme de Newton

Le but de cette partie n’est pas de présenter de nouveaux résultats de dénombrement mais plutôt une formule de calcul algébrique. Elle n'est cependant pas hors-sujet par rapport au reste du chapitre, car elle repose sur les coefficients binomiaux définis à la partie précédente. De plus, les preuves proposées seront de nature combinatoire.

Compléments sur les coefficients binomiaux

Nous allons présenter ici deux petites égalités vérifiées par les coefficients binomiaux.

La première est une relation dite de symétrie.

Propriété de symétrie

Soient n et 0 p n .

On a

( n p ) = ( n n - p )

Démonstration

Considérons un ensemble fini E de cardinal n.

Si A est un sous-ensemble de p éléments de E, d'après l'égalité du paragraphe 1.3.2 on a card ( C E ( A ) ) = n - p .

A tout sous-ensemble de p éléments de E on peut donc associer un unique sous-ensemble de n - p éléments de E, son complémentaire.

Le nombre de sous-ensembles de p éléments de E est donc égal au nombre de sous-ensembles de n - p éléments de E. Q.E.D.

La formule suivante porte le nom du mathématicien français Blaise Pascal (1623-1662), même si elle fut énoncée et démontrée plusieurs siècles avant lui.

Relation de Pascal

Soient n et 1 p n - 1 .

On a

( n p ) = ( n - 1 p - 1 ) + ( n - 1 p )

Démonstration

Considérons un ensemble fini E de cardinal n et x un élément quelconque de E.

Il est évident qu’un sous ensemble de p éléments de E contient ou ne contient pas x :

  • Le nombre de ceux qui contiennent x est égal à ( n - 1 p - 1 ) . En effet, si un sous-ensemble de p éléments de E contient x, pour le constituer il ne reste plus qu'à choisir p - 1 éléments dans l'ensemble E privé de x, c'est-à-dire dans un ensemble à n - 1 éléments.

  • Le nombre de ceux qui ne contiennent pas x est égal à ( n - 1 p ) . En effet, si un sous-ensemble de p éléments de E ne contient pas x, pour le constituer il reste encore à choisir p éléments dans l'ensemble E privé de x, c'est-à-dire dans un ensemble à n - 1 éléments.

Le nombre de sous ensemble de p éléments de E est donc égal à la somme des deux quantités ci-dessus. Q.E.D.

Triangle de Pascal

La relation de Pascal permet de construire facilement un tableau contenant la valeur des coefficients binomiaux. On le nomme triangle de Pascal :

La première colonne correspond à p = 0 . Elle ne contient que des 1 car

( n 0 ) = n ! 0 ! ( n 0 ) ! = n ! n ! = 1

La diagonale correspond à p = n . Elle ne contient aussi que des 1 car

( n n ) = n ! n ! ( n n ) ! = n ! n ! = 1

Les autres valeurs se calculent grâce à la relation de Pascal, la valeur d'une case étant égale à la somme des valeurs des deux cases situées au dessus d'elle.

[Note]

Rappelons que par convention 0 ! = 1 .

Il n'y a pas de valeurs au-dessus de la diagonale car les coefficients binomiaux ne sont définis que pour 0 p n , ce qui pour une ligne donnée n correspond aux colonnes p d'indices inférieurs à n.

Formule du binôme de Newton

La formule du binôme, attribuée à Isaac Newton (1643-1727), permet de développer des expressions de la forme ( x + y ) n pour tout entier naturel n. En cela elle généralise la célèbre identité remarquable ( x + y ) 2 .

Binôme de Newton

Soient x et y des nombres réels et n un entier naturel.

On a

( x + y ) n = k = 0 n ( n k ) x k y n k

Démonstration

Nous ne donnerons que les points importants de la preuve, le lecteur n'aura pas de mal à reconstituer les détails.

Si l'on développe le produit ( x + y ) n , chaque terme de la somme obtenue sera de la forme

x x . . . x y . . . y = x k y n - k

Pour k fixé, il y aura autant de termes de ce type que de façons de choisir k des produits de l’expression initiale pour obtenir x k , c'est-à-dire ( n k ) . A noter que le terme y n - k apparaît de lui même, puisque les produits comportent n facteurs et que lorsque l'on ne choisit pas x on choisit nécessairement y.

La valeur de ( x + y ) n est donc égale à la somme des termes ( n k ) x k y n - k , pour 0 k n . Q.E.D.

[Note]

On aurait pu également effectuer une preuve par récurrence. Plus simple intellectuellement mais plus calculatoire.

A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels