¿De cuántas formas se pueden enviar 5 letras en 4 casillas para letras?

Question

La respuesta a la pregunta según mi libro de texto es $4^5$ formas, pero ¿no podría también ser como $5$ formas de colocar las letras en la primera caja de letras, $4$ formas de hacer lo mismo en la segunda caja de letras (porque ya colocaste una letra en la primera caja de letras, por lo que quedan $4$ letras) y así sucesivamente hasta la caja de letras $4^{th}$. Entonces el número total de formas es $5 \times 4 \times 3 \times 2=120$. ¿Dónde me equivoqué?

Answer 1

---

La idea más simple es la que utiliza el libro de texto, y no es considerar los buzones uno por uno, sino considerar las cartas una por una. Para la primera carta, tenemos 4 opciones de dónde colocarla. La colocación de la segunda es independiente de la primera, también tenemos 4 opciones. Y así sucesivamente para las 5 letras diferentes, obteniendo $4^5$.

Ahora, ¿qué pasaría si quisiéramos seguir tu línea de pensamiento y considerar cómo llenamos los buzones? Bueno, la solución resultante es mucho más complicada, pero aún válida, como te mostraré.

Así, para el primer buzón tenemos la opción de colocar 0, 1, 2, 3, 4, 5 letras, y de qué manera. Luego, pasamos al segundo buzón y nos hacemos la misma pregunta sobre las letras restantes.

Vamos a generalizar a $l$ letras y $m$ buzones. Denotemos $f(l,m)$ como el número de formas de colocar $l$ letras en $m$ buzones. Primero, debemos elegir cuántas y qué letras colocar en el primer buzón. ¿Cómo se hace esto? Sabemos que $l \choose k$ es la forma de elegir $k$ letras entre $l$ letras. Una vez que elegimos $k$ letras para colocar en el buzón, luego tenemos que colocar las $l-k$ letras restantes en los $m-1$ buzones restantes, lo que requiere encontrar el valor $f(l-k,m-1$).

Sabiendo que necesitamos hacer esto para todos los valores posibles de $k$ desde $0$ hasta $l$, obtenemos la siguiente recurrencia:

$$f(l,m)= {\sum_{k=0}^l } {{l}\choose {k} }\times f(l-k,m-1)$$ Dado que esta es una fórmula recursiva, especificamos un caso base $f(0,m)=1$, lo que significa que hay 1 forma de no poner ninguna letra en ningún número de buzones, y $f(l,1)$ significa que si tenemos $l$ letras y solo queda un buzón, estamos obligados a colocarlas todas en ese buzón.

Resolver esto para $f(5,4)$ te dará la respuesta que deseas. Hemos terminado. Pero, si tienes curiosidad, ¿por qué es diferente de la respuesta del libro de texto?

Bueno, podemos intentar usar la función generadora para demostrar que esta respuesta, por complicada que sea, es igual a la respuesta del libro de texto.

Dejemos que $F_m(l)$ denote ahora $f(l,m)$. Nuestra recurrencia es

$$F_m(l)= {\sum_{k=0}^l } {{l}\choose {k} }\times F_{m-1}(l-k)$$

Si imaginamos $F_m$ y $F_{m-1}$ como secuencias, reconocemos que la expresión anterior es la convolución binomial de las secuencias $F_{m-1}$ y $1,1,1,1,1...$

Entonces, dejemos que $g_m(x)$ denote la función generadora exponencial de $F_m$, y sabemos que $e^x$ representa la secuencia de $1's$. La recurrencia anterior, expresada en funciones generadoras, es entonces: $$g_m(x)=e^x \times g_{m-1}(x)$$

Al resolver eso, obtenemos $$g_m(x)=e^x \times e^x \times e^x... =e^{mx}$$

$e^{mx}$ es la función generadora de la secuencia $m^0, m^1,m^2.....$

Entonces, la secuencia representada por $g_m(x)=e^{mx}$ es $F_m(l)=m^l$. Por lo tanto, $$f(l,m)=m^l$$ y la solución de $f(5,4)=4^5$

Si no entendiste estas complicaciones, está bien. En general, la recurrencia es una respuesta aceptada. La moraleja aquí es tener cuidado con cómo comienzas a contar y cambiar de perspectiva (letras o buzones) cuando surjan complicaciones. Además, asegúrate siempre de cubrir TODOS los escenarios posibles (diferentes formas de colocar el mismo número de letras en una caja) y nunca cuentes un escenario más de una vez.

Answer 2

Formulación simple:

5 letras pero 4 casillas de letras

la primera letra se puede colocar en cualquiera de las 4 casillas

la segunda letra se puede colocar en cualquiera de las 4 casillas

la tercera letra se puede colocar en cualquiera de las 4 casillas

la cuarta letra se puede colocar en cualquiera de las 4 casillas

la quinta letra se puede colocar en cualquiera de las 4 casillas

4 opciones para cada letra, 5 letras, $4^5$ posibilidades.

EDICIÓN

y no podemos hacer 5 para la primera, etc. hay 32 opciones para las combinaciones de letras que podrían colocarse ahí.

Answer 3

En Rosen, Kenneth, et. al., Manual de Matemáticas Discretas y Combinatorias, sección 2.3.3, puedes leer que si se deben colocar $k$ objetos distintos en $n$ contenedores, con cualquier cantidad de objetos en cada contenedor, la cantidad de formas diferentes de hacer esto es $n^k$. Literalmente, "aplica la regla del producto al número de opciones de contenedor posibles para cada objeto". En nuestra pregunta, los contenedores son las 4 cajas de cartas y los objetos son los 5 sobres, por lo tanto, $4^5$ es una respuesta válida al problema, según su formulación simple.