Principios combinatoriosAl 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 sumaLa 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 productoLa regla del producto es otro principio intuitivo que establece que si hay formas de hacer algo y formas de hacer otra cosa, entonces hay formas de hacer ambas cosas. Principio de inclusión-exclusiónEl 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 son conjuntos finitos, entonces Regla de la divisiónAfirma que hay formas de hacer una tarea si se puede hacer mediante un procedimiento que se puede realizar de formas, y para todas las formas , exactamente de las formas corresponden a la forma . Prueba BiyectivaLas 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 dobleEl conteo doble es una técnica que equipara dos expresiones que cuentan el tamaño de un conjunto de dos maneras. Principio de casillasEl principio de casillas establece que si cada artículo se coloca en una de las cajas , donde , 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 distinguidoEl método del elemento distinguido destaca un "elemento distinguido" de un conjunto para probar algún resultado. Función generadoraLas 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 an es Relación de recurrenciaUna 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
Enlaces externosEsta 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. |