En el campo matemático de la combinatoria enumerativa , las identidades a veces se establecen mediante argumentos que se basan en señalar un "elemento distinguido" de un conjunto.
Definición
Dejar ser una familia de subconjuntos del conjunto y deja ser un elemento distinguido del conjunto . Entonces suponga que hay un predicado que relaciona un subconjunto a . Denotar ser el conjunto de subconjuntos de para cual es cierto y ser el conjunto de subconjuntos de para cual es falso, entonces y son conjuntos disjuntos, por lo que por el método de suma, las cardinalidades son aditivas [1]
Por tanto, el elemento distinguido permite una descomposición de acuerdo con un predicado que es una forma simple de un algoritmo de divide y vencerás . En combinatoria, esto permite la construcción de relaciones de recurrencia . Los ejemplos se encuentran en la siguiente sección.
Ejemplos de
- El coeficiente binomial es el número de subconjuntos de tamaño- k de un conjunto de tamaño- n . Una identidad básica, una de cuyas consecuencias es que los coeficientes binomiales son precisamente los números que aparecen en el triángulo de Pascal, establece que:
- Prueba: En un conjunto de tamaño- ( n + 1), elija un elemento distinguido. El conjunto de todas reducción de tamaño k subconjuntos contiene: (1) todos los reducción de tamaño k subconjuntos que hacen contienen el elemento distinguido, y (2) todos los reducción de tamaño k subconjuntos que no contiene el elemento distinguido. Si un tamaño- k subconjunto de un tamaño- ( n conjunto + 1) no contiene el elemento distinguido, a continuación, su otro k - 1 elementos se eligen de entre los otros n elementos de nuestro tamaño- ( n conjunto + 1). Por tanto, el número de formas de elegirlas es . Si un subconjunto de tamaño- k no contiene el elemento distinguido, entonces todos sus k miembros se eligen entre los otros n elementos "no distinguidos". Por tanto, el número de formas de elegirlas es .
- El número de subconjuntos de cualquier conjunto de tamaño n es 2 n .
- Prueba: utilizamos la inducción matemática . La base para la inducción es la verdad de esta proposición en el caso n = 0. El conjunto vacío tiene 0 miembros y 1 subconjunto, y 2 0 = 1. La hipótesis de inducción es la proposición en el caso n ; lo usamos para probar el caso n + 1. En un conjunto de tamaño- ( n + 1), elija un elemento distinguido. Cada subconjunto contiene el elemento distinguido o no. Si un subconjunto contiene el elemento distinguido, entonces sus elementos restantes se eligen entre los otros n elementos. Según la hipótesis de inducción, el número de formas de hacerlo es 2 n . Si un subconjunto no contiene el elemento distinguido, entonces es un subconjunto del conjunto de todos los elementos no distinguidos. Según la hipótesis de inducción, el número de tales subconjuntos es 2 n . Finalmente, la lista completa de subconjuntos de nuestro conjunto size- ( n + 1) contiene 2 n + 2 n = 2 n +1 elementos.
- Sea B n el n- ésimo número de Bell , es decir, el número de particiones de un conjunto de n miembros. Sea C n el número total de "partes" (o "bloques", como suelen llamarlos los combinatorios) entre todas las particiones de ese conjunto. Por ejemplo, las particiones del conjunto de tamaño 3 { a , b , c } pueden escribirse así:
- Vemos 5 particiones, que contienen 10 bloques, por lo que B 3 = 5 y C 3 = 10. Una identidad establece:
- Prueba: En un conjunto de tamaño- ( n + 1), elija un elemento distinguido. En cada partición de nuestro conjunto size- ( n + 1), el elemento distinguido es un "singleton", es decir, el conjunto que contiene sólo el elemento distinguido es uno de los bloques, o el elemento distinguido pertenece a un bloque más grande. Si el elemento distinguido es un singleton, la eliminación del elemento distinguido deja una partición del conjunto que contiene los n elementos no distinguidos. Hay B n formas de hacerlo. Si el elemento distinguido pertenece a un bloque más grande, entonces su eliminación deja un bloque en una partición del conjunto que contiene los n elementos no distinguidos. Hay C n bloques de este tipo.
Ver también
Referencias
- ↑ Petkovšek, Marko; Tomaž Pisanski (noviembre de 2002). "Interpretación combinatoria de números de Stirling y Lah sin firmar" (PDF) . Serie de preimpresiones de la Universidad de Ljubljana . 40 (837): 1–6 . Consultado el 12 de julio de 2013 .