Principios combinatorios

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.

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

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 ${\displaystyle A_{1},\dots ,A_{n}}$ son conjuntos finitos, entonces

${\displaystyle {\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}}}$

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

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.

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

El principio de casillas establece que si cada artículo ${\displaystyle n}$ se coloca en una de las cajas ${\displaystyle m}$, donde ${\displaystyle 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.

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

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

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

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.

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

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.