﻿ Bijective_proof : définition de Bijective_proof et synonymes de Bijective_proof (anglais)

Publicité ▼

## définition - Bijective_proof

voir la définition de Wikipedia

Wikipedia

# Bijective proof

In combinatorics, bijective proof is a proof technique that finds a bijective function f : AB between two finite sets A and B, thus proving that they have the same number of elements, |A| = |B|. One place the technique is useful is where we wish to know the size of A, but can find no direct way of counting its elements. Then establishing a bijection from A to some B solves the problem in the case when B is more easily countable. Another useful feature of the technique is that the nature of the bijection itself often provides powerful insights into each or both of the sets.

## Basic examples

### Proving the symmetry of the binomial coefficients

The symmetry of the binomial coefficients states that

${n \choose k} = {n \choose n-k}.$

This means there are exactly as many combinations of k in a set of n as there are combinations of n − k in a set of n.

#### The bijective proof

More abstractly and generally, we note that the two quantities asserted to be equal count the subsets of size k and n − k, respectively, of any n-element set S. There is a simple bijection between the two families Fk and Fn − k of subsets of S: it associates every k-element subset with its complement, which contains precisely the remaining n − k elements of S. Since Fk and Fn − k have the same number of elements, the corresponding binomial coefficients must be equal.

### Pascal's triangle recurrence relation

${n \choose k} = {n-1 \choose k-1} + {n-1 \choose k}\text{ for }1 \le k \le n - 1.$

#### The bijective proof

Proof. We count the number of ways to choose k elements from an n-set. Again, by definition, the left hand side of the equation is the number of ways to choose k from n. Since 1 ≤ kn − 1, we can pick a fixed element e from the n-set so that the remaining subset is not empty. For each k-set, if e is chosen, there are

${n-1 \choose k-1}$

ways to choose the remaining k − 1 elements among the remaining n − 1 choices; otherwise, there are

${n-1 \choose k}$

ways to choose the remaining k elements among the remaining n − 1 choices. Thus, there are

${n-1 \choose k-1} + {n-1 \choose k}$

ways to choose k elements depending on whether e is included in each selection, as in the right hand side expression. $\Box$

## Other examples

Problems that admit combinatorial proofs are not limited to binomial coefficient identities. As the complexity of the problem increases, a combinatorial proof can become very sophisticated. This technique is particularly useful in areas of discrete mathematics such as combinatorics, graph theory, and number theory.

The most classical examples of bijective proofs in combinatorics include:

Publicité ▼

Contenu de sensagent

• définitions
• synonymes
• antonymes
• encyclopédie

• definition
• synonym

Publicité ▼

dictionnaire et traducteur pour sites web

Alexandria

Une fenêtre (pop-into) d'information (contenu principal de Sensagent) est invoquée un double-clic sur n'importe quel mot de votre page web. LA fenêtre fournit des explications et des traductions contextuelles, c'est-à-dire sans obliger votre visiteur à quitter votre page web !

Essayer ici, télécharger le code;

Solution commerce électronique

Augmenter le contenu de votre site

Ajouter de nouveaux contenus Add à votre site depuis Sensagent par XML.

Parcourir les produits et les annonces

Obtenir des informations en XML pour filtrer le meilleur contenu.

Indexer des images et définir des méta-données

Fixer la signification de chaque méta-donnée (multilingue).

Renseignements suite à un email de description de votre projet.

Jeux de lettres

Les jeux de lettre français sont :
○   Anagrammes
○   jokers, mots-croisés
○   Lettris
○   Boggle.

Lettris

Lettris est un jeu de lettres gravitationnelles proche de Tetris. Chaque lettre qui apparaît descend ; il faut placer les lettres de telle manière que des mots se forment (gauche, droit, haut et bas) et que de la place soit libérée.

boggle

Il s'agit en 3 minutes de trouver le plus grand nombre de mots possibles de trois lettres et plus dans une grille de 16 lettres. Il est aussi possible de jouer avec la grille de 25 cases. Les lettres doivent être adjacentes et les mots les plus longs sont les meilleurs. Participer au concours et enregistrer votre nom dans la liste de meilleurs joueurs ! Jouer

Dictionnaire de la langue française
Principales Références

La plupart des définitions du français sont proposées par SenseGates et comportent un approfondissement avec Littré et plusieurs auteurs techniques spécialisés.
Le dictionnaire des synonymes est surtout dérivé du dictionnaire intégral (TID).
L'encyclopédie française bénéficie de la licence Wikipedia (GNU).

Changer la langue cible pour obtenir des traductions.
Astuce: parcourir les champs sémantiques du dictionnaire analogique en plusieurs langues pour mieux apprendre avec sensagent.

7428 visiteurs en ligne

calculé en 0,047s

Je voudrais signaler :
section :
une faute d'orthographe ou de grammaire
un contenu abusif (raciste, pornographique, diffamatoire)
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 6, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}