Demostració biyectiva

En combinatòria, una demostració biyectiva és una tècnica de demostració utilisada per a provar que dos conjunts tenen el mateix número d'elements, o que els conjunts de dos classes combinatòries tenen el mateix tamany, per mig de la descripció d'una biyección entre un conjunt i l'atre (és dir, una correspondència d'un a un entre els conjunts). Esta tècnica pot ser útil per a trobar una fòrmula per al número d'elements de certs conjunts, biyectándolos en uns atres més fàcils de contar. Ademés, la naturalea de la biyección en sí mateixa proporciona informació valiosa sobre un o abdós conjunts.

Eixemples

Simetria dels coeficients binomiales

La simetria dels coeficients binomiales afirma que

$(\binom{n}{k}) = (\binom{n}{n - k})$ .

En atres paraules, que hi ha tantes combinacions de $k$ elements com de $n - k$ elements d'entre $n$ .

Demostració biyectiva

$(\binom{n}{k})$ és, per definició, el número de subconjunts de $k$ elements d'un conjunt de $n$ . Llavors, tenim que biyectar els següents dos conjunts: els subconjunts de $k$ elements d'un de $n$ i els subconjunts de $n - k$ elements d'un de $n$ . Esta biyección és senzilla: és el complementari. Un subconjunt de $k$ elements es pot entendre com una elecció de $k$ elements d'entre els $n$ possibles. Ara, donat un d'estos subconjunts (una elecció) podem definir un subconjunt de $n - k$ elements elegint els $n - k$ elements que no estaven elegits. Recíprocamente, donada una elecció de $n - k$ elements podem definir una atra de $k$ elegint els que no hagen segut elegits. Per tant, tenim una biyección entre els subconjunts de $k$ elements d'un de $n$ i els subconjunts de $n - k$ elements d'un de $n$ . Per les propietats de les biyecciones, açò vol dir que abdós conjunts tenen el mateix número d'elements i, per definició, que $(\binom{n}{k}) = (\binom{n}{n - k}) ◻$

Igualtat de la suma de coeficients binomiales de ranc parell en els de ranc impar

Es tracta de la següent relació, vàlida per a $n \geq 1$ :

$\sum_{0 ⩽ 2 k ⩽ n} (\binom{n}{2 k}) = \sum_{0 ⩽ 2 k + 1 ⩽ n} (\binom{n}{2 k + 1})$

Demostració biyectiva

La primera suma és el número de parts d'un conjunt $A$ (en $n$ elements) en un número parell d'elements. La segona és el número de parts en un número d'elements impar. Fixant un element $a \in A$ tenim la següent biyección entre parts pares i impars: donada una part, li afegim l'element $a$ si no ho tenia i li'l llevem si ya ho tenia. Aixina, donada una partix parell obtenim una impar i viceversa. Per tant, tenim una biyección entre les parts pares i impartixes, per lo que hi ha el mateix número d'unes que de les atres, lo que és equivalent a l'enunciat. $◻$

Atres eixemples

A continuació es presenten alguns eixemples clàssics de demostracions biyectivas de l'anàlisis combinatori:

Molts resultats sobre els coeficients binomiales utilisen demostracions combinatòries, com la famosa barres i estreles.
Els múltiples recontes que conduïxen als números de Catalan s'obtenen per mig de biyecciones.
El còdic de Prüfer, una biyección que permet demostrar la fòrmula de Cayley sobre arbres etiquetats.
La correspondència de Robinson-Schensted, biyección que permet demostrar la fòrmula de Burnside per al grup simètric.
La conjugació de taules de Young permet obtindre una demostració de la fòrmula per a les particions d'un sancer.
La demostració per biyección del teorema del número pentagonal.

Bibliografia

Mazur, David E. (2010), Combinatorics / A Guided Tour, The Mathematical Association of America, p. 28. ISBN 978-0-88385-762-5.
Loehr, Nicholas A. (2011), Bijective Combinatorics. ISBN 978-1439848845.

Este artícul conté una traducció derivada de «Demostración biyectiva» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.