1.5: Estrellas y barras

Template:MathJaxLevin

¡Investiga!

Supongamos que tienes algún número de cubos de Rubik idénticos para distribuir a tus amigos. Imagina que comienzas con una sola fila de los cubos.

1. Encuentra el número de diferentes formas en las que puedes distribuir los cubos proporcionados:
   1. Tienes 3 cubos para dar a 2 personas.
   2. Tienes 4 cubos para dar a 2 personas.
   3. Tienes 5 cubos para dar a 2 personas.
   4. Tienes 3 cubos para dar a 3 personas.
   5. Tienes 4 cubos para dar a 3 personas.
   6. Tienes 5 cubos para dar a 3 personas.
2. Haz una conjetura sobre cuántas formas diferentes podrías distribuir 7 cubos a 4 personas. Explique.
3. ¿Y si cada persona tuviera que obtener al menos un cubo? ¿Cómo cambiarían tus respuestas?

Considere el siguiente problema de conteo:

Tienes 7 galletas para regalar a 4 niños. ¿De cuántas maneras puedes hacer esto?

Tómate un momento para pensar en cómo podrías resolver este problema. Puedes asumir que es aceptable darle a un niño no galletas. Además, las cookies son todas idénticas y el orden en que des las cookies no importa.

Antes de resolver el problema, aquí hay una respuesta incorrecta: Podrías adivinar que la respuesta debería ser\(4^7\) porque para cada una de las 7 cookies, hay 4 opciones de niños a las que puedes darle la galleta. Esto es razonable, pero incorrecto. Para ver por qué, considere algunos resultados posibles: podríamos asignar las primeras seis galletas al niño A, y la séptima galleta al niño B. Otro resultado asignaría la primera galleta al niño B y las seis galletas restantes al niño A. Ambos resultados se incluyen en la\(4^7\) respuesta. Pero para nuestro problema de conteo, ambos resultados son realmente los mismos: el niño A recibe seis galletas y el chico B recibe una galleta.

¿Cómo se ven realmente los resultados? ¿Cómo podemos representarlos? Un enfoque sería escribir un resultado como una cadena de cuatro números como este:

\ begin {ecuación*} 3112,\ end {ecuación*}

que representan el resultado en el que el primer niño recibe 3 galletas, el segundo y tercer niño cada uno recibe 1 galleta, y el cuarto niño recibe 2 galletas. Representada de esta manera, importa el orden en que ocurren los números. 1312 es un resultado diferente, porque el primer niño recibe una cookie en lugar de 3. Cada número en la cadena puede ser cualquier número entero entre 0 y 7. Pero la respuesta no es\(7^4\text{.}\) Necesitamos que la suma de los números sea 7.

Otra forma en que podríamos representar los resultados es escribir una cadena de siete letras:

\ begin {ecuación*}\ mbox {ABAADCD},\ end {ecuación*}

lo que representa que la primera galleta va al niño A, la segunda galleta va al niño B, la tercera y cuarta galletas van al niño A, y así sucesivamente. De hecho, este resultado es idéntico al anterior: obtiene 3 cookies, B y C obtienen 1 cada una y D obtiene 2. Cada una de las siete letras de la cadena puede ser cualquiera de las 4 letras posibles (una por cada niño), pero el número de tales cadenas no es\(4^7\text{,}\) porque aquí el orden no importa. De hecho, otra forma de escribir el mismo resultado es

\ begin {ecuación*}\ mbox {AAABCDD}. \ end {ecuación*}

Esta será la representación preferida del resultado. Dado que podemos escribir las cartas en cualquier orden, también podríamos escribirlas en orden alfabético para fines de conteo. Entonces escribiremos primero todas las A, luego todas las B, y así sucesivamente.

Ahora piensa en cómo podrías especificar tal resultado. Todo lo que realmente tenemos que hacer es decir cuándo cambiar de una letra a la siguiente. En cuanto a las cookies, tenemos que decir después de cuántas galletas dejamos de darle galletas al primer niño y comenzamos a darle galletas al segundo chico. Y luego ¿después de cuántos cambiamos al tercer chico? Y después de cuántos cambiamos a la cuarta? Entonces otra forma más de representar un resultado es así:

\ begin {ecuación*} ***|*|*|**\ fin {ecuación*}

Tres galletas van al primer chico, luego cambiamos y le damos una galleta al segundo chico, luego cambiamos, una al tercer chico, cambiamos, dos al cuarto chico. Observe que necesitamos 7 estrellas y 3 barras, una estrella por cada galleta y una barra por cada cambio entre niños, así que una barra menos que los niños (no necesitamos cambiar después del último niño, ya terminamos).

¿Por qué hemos hecho todo esto? Simple: para contar la cantidad de formas de distribuir 7 cookies a 4 niños, todo lo que necesitamos hacer es contar cuántas estrellas y gráficos de barras hay. Pero un gráfico de estrellas y barras es solo una cadena de símbolos, algunas estrellas y algunas barras. Si en lugar de estrellas y barras usaríamos 0's y 1's, solo sería un poco de cadena. Sabemos contarlos.

Antes de que nos emocionemos demasiado, debemos asegurarnos de que realmente cualquier cadena de (en nuestro caso) 7 estrellas y 3 barras corresponda a una forma diferente de distribuir las cookies a los niños. En particular, considere una cadena como esta:

\ begin {ecuación*} |***||****\ end {ecuación*}

¿Eso corresponde a una distribución de cookies? Sí. Representa la distribución en la que kid A obtiene 0 galletas (porque cambiamos a kid B antes que cualquier estrella), kid B obtiene tres galletas (tres estrellas antes de la siguiente barra), kid C obtiene 0 galletas (sin estrellas antes de la siguiente barra) y kid D obtiene las 4 galletas restantes. No importa cómo se arreglan las estrellas y las barras, podemos distribuir las cookies de esa manera. También, dada cualquier forma de distribuir las cookies, podemos representarlo con un gráfico de estrellas y barras. Por ejemplo, la distribución en la que kid A obtiene 6 galletas y kid B obtiene 1 cookie tiene la siguiente tabla:

\ begin {ecuación*} ******|*||\ end {ecuación*}

Después de todo ese trabajo finalmente estamos listos para contar. Cada forma de distribuir las cookies corresponde a un gráfico de estrellas y barras con 7 estrellas y 3 barras. Entonces hay 10 símbolos, y debemos elegir 3 de ellos para que sean barras. Así:

\ begin {equation*}\ mbox {Hay} {10\ elige 3}\ mbox {formas de distribuir 7 cookies a 4 niños.} \ end {ecuación*}

Mientras estamos en ello, también podemos responder una pregunta relacionada: ¿cuántas formas hay de distribuir 7 galletas a 4 niños para que cada niño obtenga al menos una galleta? ¿Qué se puede decir de los gráficos de estrellas y barras correspondientes? Los gráficos deben comenzar y terminar con al menos una estrella (para que los niños A y D) obtengan galletas, y además no pueden quedar dos barras adyacentes (para que los niños B y C no se salten). Una forma de asegurar esto es solo colocar barras en los espacios entre las estrellas. Con 7 estrellas, hay 6 manchas entre las estrellas, por lo que debemos elegir 3 de esas 6 manchas para rellenar con barras. Así, hay\({6 \choose 3}\) formas de distribuir 7 galletas a 4 niños dando al menos una galleta a cada niño.

Otra forma (y más general) de abordar este problema modificado es darle primero a cada niño una cookie. Ahora las 3 cookies restantes se pueden distribuir a los 4 niños sin restricciones. Entonces tenemos 3 estrellas y 3 barras para un total de 6 símbolos, 3 de los cuales deben ser barras. Entonces nuevamente vemos que hay\({6 \choose 3}\) formas de distribuir las cookies.

Las estrellas y barras se pueden utilizar en problemas de conteo que no sean niños y galletas. Aquí hay algunos ejemplos:

Ejemplo\(\PageIndex{1}\)

Tu cadena de pizza matemática favorita ofrece 10 coberturas. ¿Cuántas pizzas puedes hacer si te permiten 6 coberturas? El orden de los toppings no importa pero ahora se te permiten repeticiones. Entonces una posible pizza es triple salchicha, piña doble y cebolla.

Solución

Obtenemos 6 coberturas (contando posibles repeticiones). Representa cada uno de estos coberturas como una estrella. Piensa en bajar el menú uno a la vez: primero ves anchoas, y saltas al siguiente, salchicha. Dices que sí a la salchicha 3 veces (usa 3 estrellas), luego cambia al siguiente topping de la lista. Sigues saltando hasta llegar a la piña, a lo que dices que sí dos veces. Otro interruptor y estás en las cebollas. Dices que sí una vez. Entonces sigues cambiando hasta llegar al último topping, sin volver a decir que sí (ya has dicho que sí 6 veces. Hay 10 coberturas para elegir, por lo que debemos cambiar de considerar una topping a la siguiente 9 veces. Estas son las barras.

Ahora que estamos seguros de que tenemos el número correcto de estrellas y barras, respondemos a la pregunta simplemente: hay 6 estrellas y 9 barras, entonces 15 símbolos. Tenemos que escoger 9 de ellos para ser bares, así que hay número de pizzas posible es

\ begin {ecuación*} {15\ elige 9}. \ end {ecuación*}

Ejemplo\(\PageIndex{2}\)

¿Cuántos números de teléfono de 7 dígitos hay en los que los dígitos no van en aumento? Es decir, cada dígito es menor o igual al anterior.

Solución

Tenemos que decidir sobre 7 dígitos así usaremos 7 estrellas. Las barras representarán un cambio de cada número posible de un solo dígito hacia abajo el siguiente más pequeño. Entonces el número de teléfono 866-5221 está representado por el gráfico de estrellas y barras

\ begin {ecuation*} |*||**|*|||**|*|\ end {equation*}
Hay 10 opciones para cada dígito (0-9) así que debemos cambiar entre opciones 9 veces. Tenemos 7 estrellas y 9 barras, por lo que el número total de números de teléfono es

\ begin {ecuación*} {16\ elige 9}. \ end {ecuación*}

Ejemplo\(\PageIndex{3}\)

¿Cuántas soluciones enteras hay para la ecuación?

\ begin {ecuación*} x_1 + x_2 + x_3 + x_4 + x_5 = 13. \ end {ecuación*}

(Una solución entera a una ecuación es una solución en la que lo desconocido debe tener un valor entero.)

1. donde\(x_i \ge 0\) para cada\(x_i\text{?}\)
2. donde\(x_i > 0\) para cada\(x_i\text{?}\)
3. donde\(x_i \ge 2\) para cada\(x_i\text{?}\)

Solución

Este problema es como dar 13 galletas a 5 niños. Tenemos que decir cuántas de las 13 unidades van a cada una de las 5 variables. En otras palabras, tenemos 13 estrellas y 4 barras (las barras son como los signos “+” en la ecuación).

1. Si\(x_i\) puede ser 0 o mayor, estamos en el caso estándar sin restricciones. Así que 13 estrellas y 4 barras se pueden organizar de\({17 \choose 4}\) maneras.
2. Ahora cada variable debe ser al menos 1. Entonces dale una unidad a cada variable para satisfacer esa restricción. Ahora quedan 8 estrellas, y todavía 4 barras, por lo que el número de soluciones es\({12 \choose 4}\text{.}\)
3. Ahora cada variable debe ser 2 o mayor. Entonces, antes de cualquier conteo, dale a cada variable 2 unidades. Ahora tenemos 3 estrellas restantes y 4 barras, así que hay\({7 \choose 4}\) soluciones.

Counting with Functions

Many of the counting problems in this section might at first appear to be examples of counting functions. After all, when we try to count the number of ways to distribute cookies to kids, we are assigning each cookie to a kid, just like you assign elements of the domain of a function to elements in the codomain. However, the number of ways to assign 7 cookies to 4 kids is \({10 \choose 7} = 120\text{,}\) while the number of functions \(f: \{1,2,3,4,5,6,7\} \to \{a,b,c,d\}\) is \(4^7 = 16384\text{.}\) What is going on here?

When we count functions, we consider the following two functions, for example, to be different:

\[f = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{a \amp b \amp c \amp c \amp c \amp c \amp c} \qquad g = \twoline{1 \amp 2 \amp 3 \amp 4\amp 5 \amp 6 \amp 7}{b \amp a \amp c \amp c \amp c \amp c \amp c}.\]

But these two functions would correspond to the same cookie distribution: kids \(a\) and \(b\) each get one cookie, kid \(c\) gets the rest (and none for kid \(d\)).

The point: elements of the domain are distinguished, cookies are indistinguishable. This is analogous to the distinction between permutations (like counting functions) and combinations (not).

Contributors and Attributions

• Template:ContribLevin