Title 7. Coeficientes binomiales y principio de inclusión y exclusión.pdf ✅

1 Coeficientes binomiales y principio de inclusión y exclusión Diseñado por: David Díaz Coeficientes binomiales: Los coeficientes binomiales serán realmente fórmulas que podremos utilizar para nuevas demostraciones o ejercicios. Veamos algunas de ellas: (i) ( n 0 ) = ( n n ) = 1 (ii) ( n k ) = ( n n − k ) (iii) ( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) Estas son bastante sencillas de demostrar, aunque las puede demostrar de forma algebraica, lo mejor es que haga demostraciones combinatorias, es decir, planteando una situación de conteo que represente la igualdad. Demostración de (i): ( n 0 ) = n 0− 0! = 1 = n! n! = n n− n! = ( n n ) Pero no es la mejor manera en esta materia. La mejor sería plantear una situación de conteo: Por ejemplo, ( n 0 ) es la cantidad de maneras en las que puedo escoger ningún elemento de un grupo de n elementos, como solo hay una manera y la misma es “escoger ninguno”, entonces ( n 0 ) = 1 ( n n ) es la cantidad de maneras en las que puedo escoger n elementos de un grupo de n elementos, solo habrá una manera y la misma es “escogerlos todos”, entonces ( n n ) = 1 Luego, 1 = 1 y; por lo tanto, ( n 0 ) = ( n n ) Lo cual es una forma de demostrar que tiene mayor sentido con lo que hemos aprendido, que es conteo. Demostración de (ii) Algebraicamente: ( n k ) = n k− k! = n k− (n − k)! k! (n − k)! = n! k! (n − k)! = n (n−k)− k! k! (n − k)! = n (n−k)− (n − k)! = ( n n − k ) Combinatoriamente: ( n k ) es la cantidad de maneras de escoger k elementos de un conjunto de n elementos, que se puede representar como la cantidad de maneras que hay de poner a la izquierda k elementos de los n. (1,2,3,4,5, ... , n − 1, n)
2 Coeficientes binomiales y principio de inclusión y exclusión Diseñado por: David Díaz (1,4,3,2, ... ,8) | (5,6, n − 3, ... ,9) ( n n − k ) es la cantidad de maneras de escoger n − k elementos de un conjunto de n elementos, que será la cantidad de maneras que hay de poner a la derecha n − k elementos de los n. Cada vez que escojo k de los n a la izquierda, estoy escogiendo n − k a la derecha. En donde claramente se ve que habrá la misma cantidad de maneras de poner k a la izquierda que poner n − k a la derecha. Luego, ( n k ) = ( n n − k ) Demostración de (iii): Ya se hizo en una clase anterior. Utilidad de las propiedades Estas 3 propiedades nos ayudan a usar una propiedad llamada el triángulo de pascal: Triángulo de Pascal Vea que el triángulo de pascal indica que todas las esquinas del triángulo son 1, y vea que en equivalente todas las esquinas valen 1 también. Luego, gracias a la propiedad (iii) podemos saber que la suma de dos elementos internos del triángulo consigues el que está justo abajo. Vea que la propiedad iii indica: ( n k ) = ( n − 1 k ) + ( n − 1 k − 1 ) Que en el ejemplo del triángulo sería ( 4 3 ) = ( 3 3 ) + ( 3 2 ) Así con cualquiera. k n − k 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 ( 0 0 ) ( 1 0 ) ( 1 1 ) ( 2 0 ) ( 2 1 ) ( 2 2 ) ( 3 0 ) ( 3 1 ) ( 3 2 ) ( 3 3 ) ( 4 0 ) ( 4 1 ) ( 4 2 ) ( 4 3 ) ( 4 4 ) ( 5 0 ) ( 5 1 ) ( 5 2 ) ( 5 3 ) ( 5 4 ) ( 5 5 ) + + + +
3 Coeficientes binomiales y principio de inclusión y exclusión Diseñado por: David Díaz Ejercicio: Demuestre combinatoriamente ( n m ) ( m k ) = ( n k ) ( n − k m − k ) RESPUESTA: ( n m ) ( m k ) = ( n k ) ( n − k m − k ) Del lado izquierdo ( n m ) cuenta la cantidad de maneras de escoger m elementos de n elementos y luego ( m k ) cuenta de cuántas maneras se pueden escoger k elementos de los m ya escogidos. O sea, que el lado izquierdo cuenta de cuántas maneras se pueden escoger k elementos de m elementos escogidos de n. De la parte derecha, ( n k ) cuenta la cantidad de maneras que hay de escoger k elementos directamente de los n elementos y luego ( n − k m − k ) cuenta la cantidad de maneras que hay de escoger m − k elementos de los n − k posibles. Veamos una representación gráfica para que se note que son iguales: Parte izquierda Parte derecha Note que habíamos probado que ( m k ) = ( m m − k ), por eso a la izquierda estoy contando los k elementos de m, que es lo mismo que contar los m − k elementos de los m. Ahora bien, en la parte derecha elige directamente los k elementos de n, pero luego escoge los m − k elementos de los n − k elementos. La razón de que sean los n − k elementos es porque en la parte izquierda los m − k no incluían ningún elemento del conjunto de tamaño k. (1,2,3,4,5, ... , n − 1, n) (4,7,1, ... , n, 5) (4,1, n, . . ,5) (7,6,3, ... , n − 1) n m k (1,2,3,4,5, ... , n − 1, n) (4,1, n, . . ,5) (7,6,3, ... , n − 1) k m − k m − k Sin incluir ningún elemento de k n
4 Coeficientes binomiales y principio de inclusión y exclusión Diseñado por: David Díaz Ejercicio: Demuestre combinatoriamente ( n m ) = n m ( n − 1 m − 1 ) RESPUESTA: La parte izquierda cuenta ( n m ) que es la cantidad de maneras de escoger m elementos de un conjunto de n elementos. La parte derecha debería contar lo mismo. La parte derecha se puede interpretar como n ( n − 1 m − 1 ) m Así, primero escojo un elemento de todos los n posibles, tengo n formas de hacerlo. Luego, ( n − 1 m − 1 ), escojo los otros m − 1 elementos que necesito para completar los m elementos, los voy a escoger de n − 1 elementos porque no quiero que el primer elemento se repita. El problema es que se podrían repetir casos, por ejemplo: 1 (2,3,4,5,6, ... , m) = 2 (1,3,4,5,6, ... , m − 1) = 3 (2,1,4,5,6, ... , m − 1) Note que los casos equivalentes surgen de cambiar el primero por cualquiera de los de adentro, eso significa que habrán m repeticiones que no quiero contar, por eso la cuenta sería n ( n − 1 m − 1 ) m Representación gráfica Parte izquierda Parte derecha (1,2,3,4,5, ... , n − 1, n) (1,6,8, ... , n − 2) n m (1,2,3,4,5, ... , n − 1, n) 1 (6,8, ... , n − 2) m − 1 n