Preuve bijective
Source: Wikipédia sous licence CC-BY-SA 3.0.
La liste des auteurs de cet article est disponible ici.

En mathématique, la preuve bijective est une technique de démonstration qui consiste à considérer une application bijective entre deux ensembles et à dénombrer chacun de ces ensembles, pour montrer que les expressions obtenues, correspondant à un même cardinal, sont égales. Dans le cas particulier où l'application bijective est l'identité d'un ensemble (En théorie des ensembles, un ensemble désigne intuitivement une collection d’objets (les éléments de l'ensemble), « une multitude qui peut être comprise comme un...), cela revient à compter le nombre (La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ».) d'éléments de l'ensemble de deux façons différentes, pour établir une égalité entre les nombres résultants. Nous pourrions appeler cette dernière méthode, le double comptage. Autrement dit, nous pouvons considérer deux ensembles X et Y et les dénombrer tous les deux, puis au moyen d'un bijection (Une fonction f: X → Y est dite bijective ou est une bijection si pour tout y dans l’ensemble d'arrivée Y il existe un et un seul x dans l’ensemble de définition...) f de X sur Y, en déduire que les résultats sont identiques; ou nous pouvons également considérer un ensemble fini (En mathématiques, un ensemble E est dit fini si et seulement si E est vide ou s'il existe un entier n et une bijection de E dans l'ensemble des n premiers entiers naturels.) X et le dénombrer par une méthode A, puis une méthode B.

En identifiant (En informatique, on appelle identifiants (également appelé parfois en anglais login) les informations permettant à une personne de s'identifier auprès d'un...) les éléments des deux ensembles équipotents, on peut toujours se ramener à un dénombrement d'un même ensemble de différentes façons.

Exemples

Par exemple, considérez le nombre de manières desquelles un comité peut être formé à partir d'un total ( Total est la qualité de ce qui est complet, sans exception. D'un point de vue comptable, un total est le résultat d'une addition, c'est-à-dire une somme. Exemple : "Le total des dettes". En physique le total...) de n personnes.

Première méthode : il y a deux possibilités pour chaque personne. À chaque fois une personne peut faire partie du comité ou ne pas en faire partie. Par conséquent il y a un total de 2 \times 2 \times \ldots \times 2 (n {\rm  fois}) = 2^n comités différents.

Deuxième méthode : le nombre de membres du comité doit être un nombre entier r compris entre 0 et n. Le nombre de manières desquelles un comité de r personnes peut être formé à partir d'un total de n personnes est C_n^r (c'est un résultat bien connu; voir le coefficient (En mathématiques un coefficient est un facteur multiplicatif qui dépend d'un certain objet, comme une variable (par exemple, les coefficients d'un...) binomial). Par conséquent le nombre total de façons est la somme des C_n^r pour r variant de 0 à n.

L'égalisation des deux expressions donne

\sum_{r=0}^n C_n^r=2^n

Un exemple de théorème (Un théorème est une proposition qui peut être mathématiquement démontrée, c'est-à-dire une assertion qui peut être établie comme vraie au travers d'un raisonnement logique...) qui est généralement démontré en utilisant une preuve bijective (En mathématique, la preuve bijective est une technique de démonstration qui consiste à considérer une application bijective entre deux ensembles et à dénombrer chacun...) est le théorème qui affirme que tout (Le tout compris comme ensemble de ce qui existe est souvent interprété comme le monde ou l'univers.) graphe (Le mot graphe possède plusieurs significations. Il est notamment employé :) contient un nombre pair de sommets du degré (Le mot degré a plusieurs significations, il est notamment employé dans les domaines suivants :) impair. Soit d(s) le degré du sommet s. Chaque arête du graphe joint exactement deux sommets, ainsi en comptant le nombre d’arêtes joignant chaque sommet, nous avons compté chaque arête exactement deux fois. Par conséquent

\sum d(s)=2a

a est le nombre d’arêtes.

La somme des degrés des sommets est donc un nombre pair, ce qui ne pourrait se produire si un nombre impair de sommets avait un degré impair.

Page générée en 0.041 seconde(s) - site hébergé chez Amen
Ce site fait l'objet d'une déclaration à la CNIL sous le numéro de dossier 1037632
Ce site est édité par Techno-Science.net - A propos - Informations légales
Partenaire: HD-Numérique