¿Número de formas de seleccionar n letras de una palabra?

Question

Me encontré con la siguiente pregunta:

"¿De cuántas formas podemos seleccionar 4 letras de la palabra MISSISSIPPI?"

Esta pregunta se puede resolver considerando las diferentes posibilidades de la siguiente manera y sumando los números:

Formas de seleccionar {(4 iguales)+(3 iguales y 1 diferente)+(2 iguales y 2 diferentes)+(4 diferentes)}

Pero directamente fui a hacer el 11C4 y obtuve un número marginalmente MAYOR. ¿Qué he hecho mal? ¿Por qué debo enfocar así todas las preguntas de palabras y letras?

Edición: Siento mucho no haber mirado antes otras preguntas relacionadas con el mismo tema, pero me alegro de haber posteado de nuevo porque he recibido respuestas distintas a las relacionadas con la función generadora, que es un poco demasiado avanzada para estudiantes de mi nivel; el método de las estrellas y las barras, como sugiere Shagnik se puede entender mucho mejor.

¡Por favor, ayuda! Muchas gracias de antemano :) Saludos.

Answer 1

Determinaremos el $4$ cartas elegidas mediante la formulación de cuatro preguntas:

1. ¿Cuántas íes hay?
2. ¿Cuántas M hay?
3. ¿Cuántas P hay?
4. ¿Cuántas eses hay?

Representaremos las respuestas a estas preguntas mediante $x_I, x_M, x_P$ y $x_S$ respectivamente*. ¿Qué condiciones tenemos sobre estas variables?

Ya que tenemos $4$ letras en total, debemos tener $x_I + x_M + x_P + x_S = 4$ . Además, como cada variable cuenta algo, debe ser un número entero no negativo. Es decir, $x_I, x_M, x_P, x_S \in \mathbb{Z}_{\ge 0}$ .**

---

Estrellas y barras

Ahora bien, existe un método general, a menudo llamado argumento de las "estrellas y las barras", para contar el número de formas de escribir un número como una suma de números más pequeños. En general, supongamos que queremos escribir un número entero no negativo $n$ como una suma de $k$ enteros no negativos; es decir $$ n = y_1 + y_2 + ... + y_k, $$ donde $y_1, y_2, ..., y_k \in \mathbb{Z}_{\ge 0}$ .

Dibujaremos cada una de estas sumas utilizando estrellas y barras; habrá $n$ estrellas, y $k-1$ barras que dividen los sumandos separados. $y_1$ será el número de estrellas antes de la primera barra, $y_2$ será el número de estrellas entre la primera y la segunda barra, y así sucesivamente, hasta obtener $y_k$ para ser el número de estrellas después de la última ( $k-1$ st) bar. Por ejemplo, la suma $8 = 3 + 0 + 4 + 1$ se vería como $$ \underbrace{* * *}_{y_1 = 3} | \underbrace{}_{y_2 = 0} | \underbrace{* * * *}_{y_3 = 4} | \underbrace{*}_{y_4 = 1} \; .$$

Una cosa importante a tener en cuenta es que estamos contando pedido sumas, por lo que el orden de los sumandos es importante. Por ejemplo, la suma $8 = 4 + 3 + 1 + 0$ tiene el diagrama diferente $$ \underbrace{* * * *}_{y_1 = 4} | \underbrace{* * *}_{y_2 = 3} | \underbrace{*}_{y_3 = 1} | \underbrace{}_{y_4 = 0} \; ,$$ que se contará como una solución distinta.

¿Cómo nos ayuda esto a contar el número de sumas? Pues bien, observa que cada diagrama de este tipo es simplemente una permutación de $n$ estrellas y $k-1$ bares. Además, cada una de estas permutaciones corresponde a una suma diferente. Por lo tanto, sólo tenemos que contar estas permutaciones de símbolos.

Ahora hay un total de $n+k-1$ símbolos en una línea. Si elegimos $k-1$ de esos símbolos sean barras, eso determina el diagrama, ya que el resto de símbolos deben ser estrellas. Por lo tanto, el número de sumas es $$\binom{n+k-1}{k-1}.$$ Tenga en cuenta que esto es igual a $\binom{n+k-1}{n}$ ya que en su lugar podríamos elegir qué $n$ los símbolos son estrellas.

---

"Bajando a Mississippi"

Volviendo al problema que nos ocupa, esto significa que el número de soluciones a $x_I + x_M + x_P + x_S = 4$ es $\binom{7}{3} = 35$ .

Sin embargo, aunque cada conjunto de $4$ letras corresponde a una suma de este tipo, no toda suma proviene de una elección válida de letras. Nuestra última restricción procede de la ley de conservación de la masa, adaptada a los juegos de palabras matemáticos. No podemos seleccionar más copias de una letra de las que aparecen en la palabra "MISSISSIPPI".

Esto significa que, junto con nuestra suposición de no negatividad, también debemos tener $x_I \le 4, x_M \le 1, x_P \le 2$ y $x_S \le 4$ .

Ahora, tenga en cuenta que como sólo estamos seleccionando $4$ letras en total, nunca podremos tener $x_I \ge 5$ o $x_S \ge 5$ Por lo tanto, podemos ignorar esos requisitos. Esto deja sólo las condiciones $x_M \le 1$ y $x_P \le 2$ .

Otra observación muy útil es que no podemos violar ambas condiciones al mismo tiempo. De hecho, si tuviéramos ambas $x_M \ge 2$ y $x_P \ge 3$ entonces $x_I + x_M + x_P + x_S \ge 5$ . Por lo tanto, desde el $35$ soluciones a la suma que hemos contado antes, podemos restar las soluciones con $x_M \ge 2$ y las soluciones con $x_P \ge 3$ . Como ninguna solución satisface ambos límites, cada solución mala se resta exactamente una vez, como debe ser.

Entonces, ¿cuántas soluciones tiene $x_M \ge 2$ ? Bueno, una buena manera de contarlas es introducir una nueva variable, poniendo $z_M = x_M - 2$ . Entonces tenemos $x_I + z_M + x_P + x_S = x_I + x_M + x_P + x_S - 2 = 4 - 2 = 2$ con $x_I, z_M, x_P, x_S \in \mathbb{Z}_{\ge 0}$ . Dado que ahora sólo requerimos que todas nuestras variables sean no negativas, en lugar de que una sea al menos $2$ Hemos reducido esto a la configuración de las estrellas y las barras. Utilizando la fórmula, hay $\binom{2 + 3}{3} = \binom{5}{3}= 10$ de estas soluciones.

¿Qué pasa con $x_P \ge 3$ ? Esta vez hemos puesto $z_P = x_P - 3$ . Un argumento similar muestra que hay $\binom{1+3}{3} = \binom{4}{3} = 4$ soluciones en este caso.

De ahí que la respuesta final, es decir, el número de selecciones de $4$ cartas de "MISSISSIPPI", es $$ \binom{7}{3} - \binom{5}{3} - \binom{4}{3} = 35 - 10 - 4 = 21. $$

---

Observaciones finales

Para terminar, permítanme comentar que esto no es mucho más corto que el análisis del caso que sugirió en su pregunta (de hecho, sospecharía que es así como debía resolver el problema). Sin embargo, siempre es bueno conocer diferentes soluciones, y con una palabra más larga esto puede haber resultado un atajo.

Dicho esto, con una palabra más larga, podrían haber surgido varias complicaciones más. En este caso hemos tenido suerte porque sólo había dos tipos de soluciones malas, y ninguna solución era mala en ambos sentidos. En general, esta corrección habría implicado el Principio de Inclusión-Exclusión, que aportaría un nivel de dificultad añadido.

La mejor manera de resolver estos problemas en general es utilizar funciones generadoras ordinarias (o exponenciales si se trata de permutaciones), como se sugiere en la respuesta de @Beta. Estas son un poco más avanzadas, pero muy potentes e increíblemente interesantes, y es de esperar que las encuentres en algún curso de combinatoria más adelante.

---

Notas a pie de página

*¿Por qué ordenar las variables de esta manera? En honor a Tyrion, por supuesto.

**Algunos llaman a este conjunto los naturales, denotados $\mathbb{N}$ pero prefiero que mis naturales empiecen por $1$ .

Answer 2

Una pregunta muy interesante.

Existe una fórmula general bastante "sencilla" (no verdadera) si utilizamos la función generadora exponencial.

Dejemos que $n_i$ sea el número de veces que el $i$ La letra se repite - el orden en que ponemos las letras no importa, por supuesto. En tu ejemplo, si ponemos la palabra MISSISSIPPI tenemos dos P, cuatro I, una M, cuatro S, por lo que obtenemos

$$(n_1, ..., n_{11}) = (1,4,4,4,4,4,4,4,2,2,4)$$

Ahora dejemos que $A_{\ell}$ sea el número de palabras de longitud $\ell$ y $k$ sea el número de letras distintas.

Reclamo $$\sum_\ell \frac{A_{\ell}}{\ell!} x^\ell = \prod_{i=1}^k \sum_{j=0}^{n_i} \frac{x^i}{i!}$$

en su ejemplo esto es $$\sum_{\ell} \frac{A_{\ell}}{\ell!} x^\ell = (1+x)^1\left(1+x + \frac{x^2}{2}\right)^1\left(1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24}\right)^2$$

ya que tienes $1$ carta que aparece una vez, $1$ letra que aparece dos veces, y $2$ las letras aparecen cuatro veces.

Por lo tanto, si quieres saber el número de esas palabras con una longitud determinada, puedes extraer ese coeficiente (probablemente con un ordenador).

En este caso obtenemos

$$(1+x)^1\left(1+x + \frac{x^2}{2}\right)^1\left(1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24}\right)^2 = $$

$$ = \frac{x^{11}}{1152}+\frac{11 x^{10}}{1152}+\frac{17 x^9}{288}+\frac{149 x^8}{576}+\frac{31 x^7}{36}+\frac{161 x^6}{72}+\frac{55 x^5}{12}+\frac{22 x^4}{3}+\frac{53 x^3}{6}+\frac{15 x^2}{2}+4 x+1$$

por lo que la respuesta es, extrayendo el coeficiente en $x^4$ (porque quieres 4 palabras con letras)

$$\frac{22}{3} \cdot 4! = 176$$