22.3: Aplicaciones
- Page ID
- 118424
Distribuir/elegir objetos indistinguibles
¿Cuántas formas hay de distribuir siete monedas entre tres niños? (Supongamos que las monedas son indistinguibles. Pero los niños son obviamente distinguibles).
Solución
Aquí hay un esquema por el cual podemos decidir cuántas monedas obtendrá cada niño. Alinea a los niños en algún orden. (No hay necesidad de contar el número de formas de hacer esto — ver el final de la solución.) También coloque las monedas en una línea:
\ begin {ecuación*}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ text {.} \ end {equation*}
Ahora toma dos Hickory Sticks™ de la mesa de merienda para actuar como divisores para dividir las monedas en tres grupos. Por ejemplo,
\ begin {ecuation*}\ mathord {\ circ}\ mathord {\ mid}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ mid}\ mathord {\ circ}\ mathord {\ circ}\ final {ecuación*}
que el primer hijo recibirá una moneda, el segundo recibirá cuatro, y el tercer hijo recibirá dos, mientras que
\ begin {ecuation*}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ mid}\ mathord {\ mid}\ end {ecuación*}
que el primer hijo obtenga las siete monedas.
Ahora volvemos a la botella roja, problema de botella azul (ver Ejemplo Trabajado 21.3.4 y Ejemplo Trabajado 22.2.2): ¿cuántos patrones de símbolos diferentes podemos obtener disponiendo dos símbolos indistinguibles y siete\(\mathord{\mid}\) símbolos indistinguibles\(\mathord{\circ}\)? Simplemente elija dos de las nueve posiciones disponibles en el patrón para colocar los\(\mathord{\mid}\) símbolos. Y así hemos llegado a la respuesta\(C(9, 2) = 36\text{.}\)
Ahora bien, ¿por qué no hay que tomar en cuenta el orden de los niños al principio? Vamos a\(c_1, c_2, c_3\) representar a los tres niños. Relativo a ese orden de los niños, el patrón de símbolos
\ begin {ecuation*}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ mid}\ mathord {\ mid}\ end {ecuación*}
que el niño\(c_1\) obtenga las siete monedas, como arriba. Pero en relación con el orden de\(c_3,c_2,c_1\text{,}\) los diferentes patrones de símbolos
\ begin {ecuation*}\ mathord {\ mid}\ mathord {\ mid}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ mathord {\ circ}\ end {ecuación*}
también significa que el niño\(c_1\) obtiene las siete monedas, que es el mismo resultado. Entonces, si permitimos que tanto los patrones de símbolos como los ordenamientos de los niños varíen, terminaremos contando en exceso.
Hay\(C(n+k-1, k-1)\) formas de distribuir objetos\(n\)\(k\) indistinguibles entre contenedores distinguibles.
- Comprobante.
-
Al igual que en el último ejemplo, usa\(n\)\(\mathord{\circ}\) símbolos para representar los objetos\(k-1\) indistinguibles y\(\mathord{\mid}\) símbolos indistinguibles para representar la división en\(k\) contenedores. Entonces, cada palabra del alfabeto\(\Sigma=\{\mathord{\circ},\mathord{\mid}\}\) que contiene exactamente\(n\)\(\mathord{\circ}\) símbolos y\(k-1\)\(\mathord{\mid}\) símbolos representa una forma única de dividir los objetos en los contenedores. La longitud de tal palabra es\(n+k-1\text{,}\) y cada una de esas palabras se puede construir eligiendo\(k-1\) posiciones para los\(\mathord{\mid}\) símbolos de las posiciones de letras\(n+k-1\) disponibles.
Tu profesor hace una discreta fiesta de matemáticas, pero solo aparecen nueve alumnos (cara triste). El profesor envía a uno de los alumnos a la tienda de la esquina para conseguir latas de soda pop para todos. El alumno decide obtener una mezcla de cuatro variedades diferentes. ¿Con cuántas mezclas posibles de variedades de refrescos puede volver el estudiante? (Supongamos que las latas son indistinguibles excepto por variedad, y que la tienda tiene disponibles más de diez latas de cada variedad).
Solución
Aquí hay un esquema mediante el cual el estudiante puede decidir cómo elegir diez latas en alguna combinación de variedades de refrescos. Hacer cuatro cajas etiquetadas por variedad de refrescos. Que el alumno elija las latas de refresco con los ojos vendados, pero haga que el empleado de la tienda coloque cada lata en la caja apropiada a medida que se eligen las latas (una suposición permisible, ya que no tiene relación con el resultado). De esta manera, podemos suponer que las latas son inicialmente indistinguibles y permanecen así hasta que se colocan en la caja correspondiente, momento en el que mágicamente se convierten en la variedad especificada por la etiqueta de la caja. El teorema anterior ahora nos dice que hay
\ begin {ecuación*} C (10+4-1, 4-1) = C (13, 3) = 286\ end {ecuación*}
formas de hacer esto.
Hay\(C(n+k-1, k-1)\) formas de elegir\(n\) objetos de entre\(k\) tipos de objetos, donde los objetos son indistinguibles excepto por tipo, y hay al menos\(n\) objetos de cada tipo disponibles.
- Idea de Prueba.
-
Apelar al Teorema\(\PageIndex{1}\) exactamente como en Ejemplo Trabajado\(\PageIndex{2}\).
Recuento de bordes en gráficas conectadas
Para\(n \ge 2\text{,}\) la gráfica completa con\(n\) vértices tiene\(C(n, 2)\) aristas.
- Comprobante.
-
Una gráfica completa no tiene bucles y exactamente un borde entre cada par de vértices. Entonces para contar los bordes solo podemos contar el número de pares de vértices, que es\(C(n, 2)\) para\(n \ge 2\text{.}\)
Resumamos lo que sabemos sobre el número de aristas en una gráfica conectada arbitraria.
- Una gráfica conectada con\(n\) vértices tiene al menos\(n - 1\) aristas (Teorema 15.3.1).
- Una gráfica conectada con\(n\) vértices es un árbol si y solo si tiene exactamente\(n - 1\) bordes (Teorema 16.3.1).
- Una gráfica simple con\(n \ge 2\) vértices está completa si y solo si tiene exactamente\(C(n, 2)\) bordes (Proposición\(\PageIndex{1}\) en la dirección hacia adelante, Declaración 4 de la Proposición 14.2.1 en la dirección inversa).
El primer hecho nos dice el número mínimo de aristas que debe tener una gráfica conectada, pero no garantiza que una gráfica con tantos bordes deba estar conectada, aunque la gráfica sea simple. Lo siguiente es algo así como una inversa a este hecho, ya que proporciona tal garantía: dice usar cuántos bordes debe tener una gráfica (simple) antes de que podamos estar seguros de que está conectada.
Si\(G = (V,E)\) es una gráfica simple tal que\(\vert V \vert = n\) y\(\vert E \vert \gt C(n-1, 2)\text{,}\) luego\(G\) se conecta.
- Idea de Prueba.
-
Considerando lo contrapositivo, supongamos que\(G\) es simple pero no conectado. En la Actividad 15.5.6, descubrimos que tal\(G\) será máxima cuando tenga exactamente dos componentes conectados, cada uno de los cuales es una gráfica completa. Entre las gráficas con esas dos características (y\(n\) vértices fijos), el mayor valor posible para\(\vert E \vert\) ocurre cuando los componentes conectados de\(G\) son un vértice aislado\(v\) y la gráfica completa\(K_{n-1}\text{,}\) en cuyo caso el número de aristas es\(C(n-1, 2)\) (Proposición \(\PageIndex{1}\)para\(K_{n-1}\)). Todas las demás gráficas simples y no conectadas tendrán entonces\(\vert E \vert \le C(n-1, 2)\text{,}\) según sea necesario para completar la prueba por contrapositivo.