Principios combinatorios

En la demostración de resultados en combinatoria, se suelen reconocer y utilizar varias reglas 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 emplean para demostrar que dos conjuntos tienen el mismo número de elementos . El principio del palomar se utiliza con frecuencia para comprobar la existencia de algo o para determinar el número mínimo o máximo de algo en un contexto discreto .

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

La regla de la suma es un principio intuitivo que establece que si hay a resultados posibles para un evento (o maneras de hacer algo) y b resultados posibles para otro evento (o maneras de hacer otra cosa), y los dos eventos no pueden ocurrir simultáneamente (o las dos cosas no pueden hacerse al mismo tiempo), entonces hay a + b resultados posibles en total para los eventos (o maneras posibles de hacer una de las cosas). De forma más formal, 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 a maneras de hacer algo y b maneras de hacer otra cosa, entonces hay a  · b maneras de hacer ambas cosas. 

El principio de inclusión-exclusión relaciona el tamaño de la unión de varios conjuntos, el tamaño de cada conjunto y el tamaño de cada posible intersección de los conjuntos. El ejemplo más sencillo se da 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 de A y B , menos el número de elementos en su intersección.

En general, según este principio, si A ₁ , …, A _n son conjuntos finitos, entonces

${\displaystyle {\begin{aligned}\left|\bigcup _{i=1}^{n}A_{i}\right|&{}=\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}}}$

La regla de la división establece que hay n/d maneras de hacer una tarea si se puede hacer utilizando un procedimiento que se puede llevar a cabo de n maneras, y para cada manera w , exactamente d de las n maneras corresponden a la manera 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 doble conteo es una técnica que iguala dos expresiones que cuentan el tamaño de un conjunto de dos maneras diferentes.

El principio del palomar establece que si se colocan a elementos en b cajas, donde a > b , entonces una de las cajas contiene más de un elemento. Este principio permite, por ejemplo, demostrar la existencia de un elemento en un conjunto con propiedades específicas.

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

Las funciones generadoras son series de potencias formales cuyos coeficientes corresponden a los términos de una sucesión dada. Esta nueva representación de la sucesión abre nuevos métodos para encontrar identidades y formas cerradas relacionadas con ciertas sucesiones. La función generadora (ordinaria) de una sucesión 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 función de los términos precedentes. Las relaciones de recurrencia pueden revelar propiedades previamente desconocidas de una secuencia, pero generalmente se prefieren las expresiones analíticas para los términos de la misma.

• van Lint, JH ; Wilson, RM (2001). Un curso de combinatoria (2.ª  ed.). Cambridge University Press. ISBN 0-521-00601-5.