Tiêu đề 5. Particiones y tipos de particiones.pdf ✅

1 Particiones y tipos particiones Diseñado por: David Díaz Práctica: Ejercicio: ¿Cuál es el coeficiente de a 3bc en el desarrollo de (a + b + c) 5 ? Generalice el resultado anterior para obtener una fórmula para el coeficiente de a1 m1a2 m2a3 m3 ... ak mk en el desarrollo de (a1 + a2 + ⋯ + ak ) n RESPUESTA: Como todo, tenemos que hacer el esquema del problema: (a + b + c) 5 = (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c) Para poder saber el coeficiente de un producto, en este caso a 3bc, tendríamos que buscar de cuántas maneras puedo hallar ese producto en la distributiva. (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c) Esta es una de las maneras de lograrlo, tras la multiplicación de a por a por a por b por c. Este caso lo podríamos esquematizar de la siguiente manera: (aaabc) Otra forma podría ser: (a + b + c)(a + b + c)(a + b + c)(a + b + c)(a + b + c) El cual se podría esquematizar como: (abaac) Note que para hallar el resto de casos simplemente debo buscar la manera de permutar el multiconjunto (a 3 , b, c) El cual se puede permutar de la siguiente manera: ( 5 3,1,1 ) = 5! 3! 1! 1! = 5(4)(3)(2)(1) 3(2)(1)(1)(1) = 5(4) = 20 (a + b + c) 5 = 20a 3bc Generalice el resultado anterior para obtener una fórmula para el coeficiente de a1 m1a2 m2a3 m3 ... ak mk en el desarrollo de (a1 + a2 + ⋯ + ak ) n RESPUESTA: ( n m1, m2, m3, ... mk ) a1 m1a2 m2a3 m3 ... ak mk
2 Particiones y tipos particiones Diseñado por: David Díaz
3 Particiones y tipos particiones Diseñado por: David Díaz Particiones: Una partición es una colección de subconjuntos de A no vacíos disjuntos dos a dos, cuya unión es A. A cada uno de los elementos de la colección se le llama bloque. Por ejemplo, las particiones del conjunto (a, b, c) son: • a|b|c • ab|c • a|bc • ac|b • abc Entonces, diríamos que las particiones de un conjunto de tamaño 3 resultan por ser 5; es decir, B3 = 5 siendo Bk el número de Bell que indica la cantidad de particiones que tiene un conjunto de tamaño 3. Lamentablemente no existe hasta la fecha una fórmula cerrada para la cantidad de particiones de un conjunto de tamaño n, pero sí que contamos con una definición recursiva: Bn+1 = ∑( n i )Bi n i=0 De este modo, a partir de la primera partición, podemos hallar todas las demás: Se entiende que B0 = 1, luego B1 = ∑( 0 i )Bi 0 i=0 = ( 0 0 )B0 = 1 ( a 0 ) = 1 Luego, B2 = ∑( 1 i ) Bi 1 i=0 = ( 1 0 )B0 + ( 1 1 )B1 = (1)(1) + 1(1) = 2 De la misma forma podríamos deducir cualquier cantidad de particiones que queramos. Ahora, ¿por qué funciona esta fórmula recursiva? Calcular la cantidad de particiones que hay en un conjunto de tamaño 3, por ejemplo, sería exactamente igual que calcular las particiones de tamaño del grupo de tamaño 0 sumado con las particiones del grupo de tamaño 1 y sumado con las particiones del grupo de tamaño 2. Se entiende que estos grupos son disjuntos, por lo tanto, se puede aplicar el principio del pastor.
4 Particiones y tipos particiones Diseñado por: David Díaz Sin embargo, hay que considerar que los conjuntos de tamaño 2, por ejemplo, se podrían escoger de diferentes maneras, puedo escoger el subconjunto (a, c) y a ese conjunto buscarle las particiones, pero también lo podría hacer con el subconjunto (b, c). Entonces, mi misión se divide en dos pasos. Para cada grupo debo hallar sus particiones 1. Elijo los elementos del grupo. 2. Le calculo las particiones a esos elementos. Son dos pasos, así que por principio fundamental será la multiplicación de los mismos. Entonces, por cada grupo debo hacer ambos pasos: Para el grupo de tamaño 0 ( 2 0 ) B0 Primero calculo de cuántas maneras puedo escoger 0 elementos de los 2 posibles y luego a ellos las calculo las particiones. Como esto debe ocurrir para cada grupo, resultaría en lo siguiente: B3 = ( 2 0 )B0 + ( 2 1 )B1 + ( 2 2 )B2 = ∑( 2 i )Bi 2 i=0 B3 = 1 + 2 + 2 = 5 Ahora bien, veamos que representa cada número para que se entienda mejor el ejemplo: • B3 = a|bc, b|ac, abc, a|b|c, ab|c ( 2 0 )B0 = 1, representa: abc ( 2 1 )B1 = 2, representa: a|bc b|ac ( 2 2 )B2 = 2, representa: a|b|c ab|c Y así estaríamos calculado todas las particiones de un conjunto de tamaño 3. k-particiones de n Como acabamos de ver, no todas las particiones tienen el mismo tamaño (los mismos bloques), una k-partición de un conjunto de tamaño n se conoce como una partición de un conjunto de tamaño n en k bloques. Una partición que tenga un solo elemento por bloque se le conoce como la partición más fina, mientras que la que tenga todos los elementos en un solo bloque se le denomina la más gruesa. Existe un número, llamado el número de Stirling de Segunda Especie que calcula la cantidad de k-particiones de un conjunto de tamaño n.