Palabras de seis letras de "MONSTER"

Question

Se forma una palabra de seis letras con las letras de la palabra "MONSTER", con o sin repetición. El número de palabras que contienen exactamente tres letras diferentes es?

Intenté calcular el número posible de palabras usando Python, teniendo en cuenta las condiciones, y obtuve una respuesta de alrededor de $18900$ . Pero al pensar en ello por métodos teóricos, primero elijo $3$ cartas de $7$ en $\binom73$ maneras, y luego arregló esas $3$ en $6$ lugares en $3^6$ formas, y luego quitó el $3$ casos en los que toda la palabra está formada por una letra, junto con los $3(2^6)$ casos en los que la palabra estaba formada por sólo dos letras entre las tres elegidas.

Perdón si es confuso, pero cualquier tipo de ayuda sería muy apreciada. Gracias. También se agradecería cualquier recurso útil para las matemáticas discretas.

Answer 1

Escribo esto sin mirar primero el número o la técnica de solución de los demás. La combinatoria es un poco un arte, pero lo malo es que demasiado arte lleva a soluciones diferentes. Mi estilo consiste en encontrar soluciones que estarían igual de bien si se nos pidiera que encontráramos palabras de veinte letras que utilizaran exactamente nueve letras de la palabra INCORRECTABLE. Hay cierta libertad en pensar "¡Tres, seis y siete son números relativamente pequeños, así que vamos a hacer fuerza bruta!" y demasiada libertad es peligrosa. ^_^

En primer lugar, pensemos en el número de maneras de formar una palabra de seis letras a partir de las letras ABC, donde cada letra se utiliza al menos una vez. Este es el número de proyecciones de un conjunto con seis elementos a un conjunto con tres elementos. Por la camino del dodecagonal Esto es $3!\{{6\atop3}\}=6\cdot90=540$ . (La cantidad en el paréntesis es un Número de remolino del segundo tipo .)

De hecho, queremos que nuestras palabras estén formadas por tres letras de la palabra MONSTRUO. Esas tres letras se pueden elegir en $\binom73=35$ formas, lo que nos da un total de $35\cdot540=18900$ posibilidades.

Answer 2

Tienes que añadir los 3 casos en los que la palabra está formada por una sola letra, ¡no los reste!

$3^6$ es el número total de palabras compuestas por 1, 2 o 3 letras.

$3 \cdot 2^6$ es el número total de palabras formadas por 1 o 2 letras, pero se cuenta cada palabra formada por 1 letra dos veces : una vez que has fijado un triple de letras {A,B,C}, puedes obtener AAAAAA de dos maneras, una seleccionando {A,B} como tu subconjunto de dos letras, y otra seleccionando {A,C}.

Así que has restado dos veces las palabras compuestas por una letra, y tienes que volver a sumarlas.

Este es un ejemplo de la principio de inclusión-exclusión en el trabajo.

Sí, es cierto, $\binom{7}{3}(3^6-3\cdot 2^6+3) = 18900$ .

Answer 3

(Nota: No estoy seguro de que esta sea la respuesta correcta ya que no coincide con el cálculo del OP, así que agradecería que alguien comprobara la solución).

Las letras de la palabra MONSTRUO son todas distintas, así que la pregunta es de cuántas maneras podemos formar una cadena de $6$ con cada uno de los caracteres elegidos de entre estos $7$ opciones, bajo la restricción de que haya tres letras diferentes. Para contar esto, podemos elegir qué tres letras son las primeras: un factor de $\binom73$ . Una vez elegidas las letras, hay que ver cómo ordenarlas.

Podemos hacerlo por casos: llamar a las tres letras $A,B,C$ , entonces o bien hay $4$ de una letra y $1$ de los otros dos, o $3$ de una letra y $2$ y $1$ respectivamente de los otros dos, o $2$ de cada letra. En el primer caso hay $\binom{6}{4}\binom{3}{1}\binom{2}{1}$ formas, en la segunda hay $\binom{6}{3}\binom{3}{1}\binom{3}{1}\binom{2}{1}$ formas, y en la tercera hay $\binom{6}{2}\binom{4}{2}\binom{3}{1}\binom{2}{1}$ maneras. Así que la respuesta es $$\binom73\left[\binom{6}{4}\binom{3}{1}\binom{2}{1}+\binom{6}{3}\binom{3}{1}\binom{3}{1}\binom{2}{1}+\binom{6}{2}\binom{4}{2}\binom{3}{1}\binom{2}{1}\right]=34650.$$

---

Editar: $18900$ es correcto, como se explica en la respuesta de Matthew Daly. Creo que he descubierto dónde me he equivocado arriba: al contar el tercer caso, la cantidad $\binom62\binom42$ se pretendía que fuera el número de formas de dividir un conjunto de $6$ artículos en tres $2$ -La lógica es que primero elegimos un subconjunto de este tipo y luego elegimos otro en el resto $4$ artículos. Sin embargo, eso es un error, ya que cuenta cada posibilidad $3!=6$ veces (según el orden de elección de las particiones). Por lo tanto, la respuesta correcta debería ser $$\binom73\left[\binom{6}{4}\binom{3}{1}\binom{2}{1}+\binom{6}{3}\binom{3}{1}\binom{3}{1}\binom{2}{1}+\frac1{3!}\binom{6}{2}\binom{4}{2}\binom{3}{1}\binom{2}{1}\right]=18900.$$

Answer 4

En efecto, la fuerza bruta rara vez es una solución, pero cuando dos respuestas difieren, y la complejidad es razonable, puede demostrar que uno se equivoca :-)

El código C siguiente cuenta en base 7 (número de letras, en la matriz "palabra" count[6] ) y enumera el número de casos en los que tenemos 4 tipos de letras que no se utilizan (es decir, cuando el recuento de cada letra (array a[7] ) tiene 4 ceros).

 int j,ok = 0,total = 0,go = 1; // 'ok' is number of correct matches
 int count[6] = { 0 };          // "words", as 6 digits from 0 to 6

 while ( go ) {
      total++;                 // total cases, should be 7^6
      int a[7] = { 0 };        // Counter in base 7
      for(int j=0 ; j<6 ; j++) {
            a[ count[j] ]++;   // Inc digit at count[j] in a
      }
      int zero = 0;            // Tautology :-)
      for(j=0 ; j<7 ; j++) {
            if (a[j] == 0) zero++; // Count digits of 0 count
      }
      if (zero == 4) ok++; // Need 4 zeroes...

      // Count in base 7 (number is reverse but that's not important!)
      for(j=0 ; j<6 ; j++) {
            if (++count[j] < 7) break; // Leave this loop if in base
            if (j == 5) go = 0;        // 7^6 reached, leave main loop
            count[j] = 0;
      }
 }
 printf("Total: %d, matches: %d\n", total, ok);

Y el ganador es

Total: $\boxed{117649}$ coincide: $\color{blue}{\boxed{18900}}$

El 'UNCOPYRIGHTABLE' mencionado arriba (quizás abajo, pero más probablemente arriba) debería ser solucionable en un ordenador decente gracias a algunas optimizaciones...