A la hora de demostrar resultados en combinatoria se reconocen y utilizan comúnmente 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 utilizan para demostrar que dos conjuntos tienen el mismo número de elementos . El principio del palomar a menudo determina la existencia de algo o se utiliza 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 de elementos distinguidos . Las funciones generadoras y las relaciones de recurrencia son herramientas poderosas que se pueden utilizar 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 posibles resultados para un evento (o maneras de hacer algo) y b posibles resultados para otro evento (o maneras de hacer otra cosa), y los dos eventos no pueden ocurrir a la vez (o las dos cosas no pueden hacerse a la vez), entonces hay a + b posibles resultados totales para los eventos (o maneras posibles 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 a formas de hacer algo y b formas de hacer otra cosa, entonces hay a · b formas 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 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.
En general, según este principio, si A 1 , …, A n son conjuntos finitos, entonces
La regla de división establece que hay n/d maneras de hacer una tarea si se puede hacer usando un procedimiento que puede llevarse a cabo de n maneras, y para cada manera w , exactamente d de las n maneras corresponden a la manera w .
Las pruebas biyectivas demuestran que dos conjuntos tienen el mismo número de elementos encontrando una función biyectiva (correspondencia biyectiva) de un conjunto al otro.
El conteo doble es una técnica que iguala dos expresiones que cuentan el tamaño de un conjunto de dos maneras.
El principio del palomar establece que si se colocan elementos a en una de las b cajas, donde a > b , entonces una de las cajas contiene más de un elemento. Con este principio se puede, por ejemplo, demostrar la existencia de algún elemento en un conjunto con algunas propiedades específicas.
El método de elementos distinguidos selecciona un "elemento distinguido" de un conjunto para demostrar algún resultado.
Las funciones generadoras pueden considerarse como polinomios con una cantidad infinita de términos cuyos coeficientes corresponden a términos de una sucesión. Esta nueva representación de la sucesión abre nuevos métodos para encontrar identidades y formas cerradas pertenecientes a ciertas sucesiones. La función generadora (ordinaria) de una sucesión a n es
Una relación de recurrencia define cada término de una secuencia en términos de los términos anteriores. Las relaciones de recurrencia pueden dar lugar a propiedades de una secuencia desconocidas hasta el momento, pero, en general, se prefieren expresiones de forma cerrada para los términos de una secuencia.
