Principios combinatorios

Al probar los resultados en combinatoria, se reconocen y utilizan comúnmente varias reglas combinatorias o principios combinatorios útiles.

La regla de la suma, la regla del producto y el principio de inclusión-exclusión se utilizan a menudo con fines enumerativos. Las pruebas biyectivas se utilizan para demostrar que dos conjuntos tienen el mismo número de elementos. El principio de casillero a menudo determina la existencia de algo o se usa para determinar el número mínimo o máximo de algo en un contexto discreto.

Muchas identidades combinatorias surgen de métodos de conteo doble o del método del elemento distinguido. La generación de funciones y relaciones de recurrencia son herramientas poderosas que pueden usarse para manipular secuencias y pueden describir, si no resolver, muchas situaciones combinatorias.

Regla de la suma

La regla de la suma es un principio intuitivo que establece que si hay posibles resultados para un evento (o formas de hacer algo) y posibles resultados para otro evento (o formas de hacer otra cosa), y los dos eventos no pueden ocurrir a la vez ( o las dos cosas no se pueden hacer ambas), entonces hay un total de posibles resultados para los eventos (o posibles formas totales de hacer una de las cosas). Más formalmente, la suma de los tamaños de dos conjuntos disjuntos es igual al tamaño de su unión.

Regla del producto

La regla del producto es otro principio intuitivo que establece que si hay $a$ formas de hacer algo y $b$ formas de hacer otra cosa, entonces hay $a\cdot b$ formas de hacer ambas cosas.

Principio de inclusión-exclusión

Inclusión-exclusión ilustrada para tres conjuntos

El principio de inclusión-exclusión relaciona el tamaño de la unión de múltiples conjuntos, el tamaño de cada conjunto y el tamaño de cada posible intersección de los conjuntos. El ejemplo más pequeño es cuando hay dos conjuntos: el número de elementos en la unión de A y B es igual a la suma del número de elementos en A y B, menos el número de elementos en su intersección.

Generalmente, de acuerdo con este principio, si $A_{1},\dots ,A_{n}$ son conjuntos finitos, entonces

${\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \cdots \ +\left(-1\right)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|.\end{aligned}}$

Regla de la división

Afirma que hay $n/d$ formas de hacer una tarea si se puede hacer mediante un procedimiento que se puede realizar de $n$ formas, y para todas las formas $w$, exactamente $d$ de las $n$ formas corresponden a la forma $w$.

Prueba Biyectiva

Las demostraciones biyectivas prueban que dos conjuntos tienen el mismo número de elementos al encontrar una función biyectiva (correspondencia uno a uno) de un conjunto al otro.

Cuenta doble

El conteo doble es una técnica que equipara dos expresiones que cuentan el tamaño de un conjunto de dos maneras.

Principio de casillas

El principio de casillas establece que si cada artículo $n$ se coloca en una de las cajas $m$, donde $n>m$, entonces una de las cajas contiene más de un artículo. Usando este se puede, por ejemplo, demostrar la existencia de algún elemento en un conjunto con algunas propiedades específicas.

Método de elemento distinguido

El método del elemento distinguido destaca un "elemento distinguido" de un conjunto para probar algún resultado.

Función generadora

Las funciones generadoras se pueden considerar como polinomios con infinitos términos cuyos coeficientes corresponden a los términos de una secuencia. Esta nueva representación de la secuencia abre nuevos métodos para encontrar identidades y formas cerradas pertenecientes a ciertas secuencias. La función generadora (ordinaria) de una secuencia a_n es

$G(a_{n};x)=\sum _{n=0}^{\infty }a_{n}x^{n}.$

Relación de recurrencia

Una relación de recurrencia define cada término de una secuencia en términos de los términos precedentes. Las relaciones de recurrencia pueden conducir a propiedades previamente desconocidas de una secuencia, pero generalmente son más deseables las expresiones de forma cerrada para los términos de una secuencia.

Referencias

• J. H. van Lint and R. M. Wilson (2001), A Course in Combinatorics (Paperback), 2nd edition, Cambridge University Press. ISBN 0-521-00601-5

Enlaces externos

Esta obra contiene una traducción derivada de «Combinatorial principles» de la Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.

• Datos: Q3850844