5.2: Aplicaciones de Inclusión y Exclusión
- Page ID
- 112562
5.2.1: Multiconjuntos con números restringidos de elementos
Ejercicio\(235\)
¿De cuántas maneras podemos distribuir manzanas\(k\) idénticas a\(n\) los niños para que ningún niño obtenga más de cuatro manzanas? Compara tu resultado con tu resultado en Problema 197. (Pista).
5.2.2: El problema de Ménage
\(\rightarrow\) Exercise \(236\)
Un grupo de parejas\(n\) casadas acude a una sesión de discusión grupal donde todas se sientan alrededor de una mesa redonda. ¿De cuántas maneras pueden sentarse para que ninguna persona esté al lado de su cónyuge? (Tenga en cuenta que dos personas del mismo sexo pueden sentarse una al lado de la otra). (Pista).
\(\rightarrow \; *\) Exercise \(237\)
Un grupo de parejas\(n\) casadas acude a una sesión de discusión grupal donde todas se sientan alrededor de una mesa redonda. ¿De cuántas maneras pueden sentarse para que ninguna persona esté al lado de su cónyuge o de una persona del mismo sexo? A este problema se le llama problema ménage. (Pista).
5.2.3: Contar sobre las funciones
\(\bullet\) Exercise \(238\)
Dada una función\(f\) desde el conjunto\(k\) -element\(K\) hasta el conjunto\(n\) -element\([n]\), decimos que\(f\) está en el conjunto\(A_i\) si\(f(x) \neq i\) para cada\(x\) en\(K\). ¿A cuántos de estos conjuntos pertenece una función onto? ¿Cuál es el número de funciones de un conjunto\(k\) -element a un conjunto\(n\) -element?
\(\rightarrow\) Exercise \(239\)
Encuentra una fórmula para el número Stirling (del segundo tipo)\(S(k, n)\). (Pista).
Ejercicio\(240\)
Si rodamos un dado ocho veces, obtenemos una secuencia de\(8\) números, el número de puntos en la parte superior en el primer rollo, el número en el segundo rollo, y así sucesivamente.
a. ¿Cuál es el número de formas de enrollar el dado ocho veces para que cada uno de los números uno al seis aparezca al menos una vez en nuestra secuencia? Para obtener una respuesta numérica, es probable que necesite un paquete de álgebra informática.
b. ¿Cuál es la probabilidad de que obtengamos una secuencia en la que aparezcan los seis números entre uno y seis? Para obtener una respuesta numérica, es probable que necesite un paquete de álgebra de computadora, una calculadora programable o una hoja de cálculo.
c. ¿Cuántas veces tenemos que rodar el dado para tener probabilidad al menos la mitad de que los seis números aparezcan en nuestra secuencia? Para responder a esta pregunta, es probable que necesite un paquete de álgebra de computadora, una calculadora programable o una hoja de cálculo.
5.2.4: El polinomio cromático de una gráfica
Definimos una gráfica para que consista en conjunto\(V\) de elementos llamados vértices y un conjunto\(E\) de elementos llamados bordes de tal manera que cada borde se une a dos vértices. Una coloración de una gráfica por los elementos de un conjunto\(C\) (de colores) es una asignación de un elemento de\(C\) a cada vértice de la gráfica; es decir, una función desde el conjunto\(V\) de vértices de la gráfica a\(C\). Una coloración se llama apropiada si por cada borde que une dos vértices distintos 1, los dos vértices que une tienen colores diferentes. Es posible que hayas oído hablar del famoso teorema de cuatro colores de la teoría gráfica que dice si una gráfica puede ser dibujada en el plano para que no se crucen dos bordes (aunque puedan tocar en un vértice), entonces la gráfica tiene una coloración adecuada con cuatro colores. Aquí nos interesa un problema diferente, aunque relacionado: a saber, ¿de cuántas maneras podemos colorear adecuadamente una gráfica (independientemente de si se puede dibujar en el plano o no) usando\(k\) o menos colores? Cuando estudiamos árboles, nos limitamos a las gráficas conectadas. (Recordemos que una gráfica está conectada si, por cada par de vértices, hay un paseo entre ellos). Aquí, las gráficas desconectadas también serán importantes para nosotros. Dado un gráfico que podría o no estar conectado, particionamos sus vértices en bloques llamados componentes conectados de la siguiente manera. Por cada vértice\(v\) ponemos todos los vértices conectados a él por un paseo en un bloque juntos. Claramente, cada vértice está en al menos un bloque, porque el vértice\(v\) está conectado al vértice\(v\) por el paseo trivial que consiste en el vértice único\(v\) y sin bordes. Para tener una partición, cada vértice debe estar en uno y solo un bloque. Para probar que hemos definido una partición, supongamos que el vértice\(v\) está en los bloques\(B_1\) y\(B_2\). Entonces\(B_1\) está el conjunto de todos los vértices conectados por caminatas a algún vértice\(v_1\) y\(B_2\) es el conjunto de todos los vértices conectados por caminatas a algún vértice\(v_2\).
\(\cdot\) Exercise \(241\)
(Relevante en el Apéndice C así como en esta sección.) \(B_1 = B_2\)Demuéstralo. Ya que\(B_1 = B_2\), estos dos conjuntos son el mismo bloque, y así todos los bloques que contienen\(v\) son idénticos, así\(v\) es en un solo bloque. Así tenemos una partición del conjunto de vértices, y los bloques de la partición son los componentes conectados de la gráfica. Observe que los componentes conectados dependen del conjunto de aristas de la gráfica. Si tenemos una gráfica en el conjunto de vértices\(V\) con conjunto de bordes\(E\) y otra gráfica en el conjunto de vértices\(V\) con conjunto de bordes\(E'\), entonces estas dos gráficas podrían tener diferentes componentes conectados. Es tradicional utilizar la letra griega\(γ\) (gamma) 2 para representar el número de componentes conectados de una gráfica; en particular,\(γ(V, E)\) representa el número de componentes conectados de la gráfica con conjunto de vértices\(V\) y conjunto de bordes\(E\). Vamos a mostrar cómo se puede usar el principio de inclusión y exclusión para calcular el número de formas de colorear un gráfico correctamente usando colores de un conjunto\(C\) de\(c\) colores.
\(\cdot\) Exercise \(242\)
Supongamos que tenemos una gráfica\(G\) con conjunto de vértices\(V\) y conjunto de bordes\(E\). Supongamos que\(F\) es un subconjunto de\(E\). Supongamos que tenemos un conjunto\(C\) de\(c\) colores con los que colorear los vértices.
a. en términos de\(γ(V, F)\), ¿de cuántas maneras podemos colorear los vértices de\(G\) para que cada borde en\(F\) conecte dos vértices del mismo color? (Pista).
b. Dada una coloración de\(G\), para cada borde\(e\) en\(E\), consideremos la propiedad de que los extremos de\(e\) están coloreados del mismo color. Llamemos a esta propiedad “propiedad”\(e\). De esta manera cada conjunto de propiedades puede pensarse como un subconjunto de\(E\). ¿Qué conjunto de propiedades tiene una coloración adecuada?
c. Encontrar una fórmula (que puede implicar sumar sobre todos los subconjuntos\(F\) del conjunto de bordes de la gráfica y usar el número\(γ(V, F)\) de componentes conectados de la gráfica con conjunto de vértices\(V\) y conjunto de bordes\(F\)) para el número de colorantes adecuados de\(G\) usar colores en el conjunto\(C\). (Pista).
La fórmula que encontraste en Problema 242c es una fórmula que involucra poderes de\(c\), y por lo tanto es una función polinómica de\(c\). Así se le llama el “polinomio cromático de la gráfica”\(G\). Como nos gusta pensar que los polinomios tienen una variable\(x\) y nos gusta pensar que representan\(c\) alguna constante, la gente suele usar\(x\) como notación para el número de colores que estamos usando para colorear\(G\). Frecuentemente las personas usarán\(χG(x)\) para representar la cantidad de formas de colorear\(G\) con\(x\) colores, y llamar\(χG(x)\) al polinomio cromático de\(G\).