Problemas en encontrar el número de permutaciones

Question

Actualmente estoy tomando un curso de Matemáticas Discretas. En que mientras que la solución de este problema soy poco confundido con el método de solucionar el siguiente problema.

Problema: ¿cuántos arreglos hay de las letras TALLAHASSEE que no tienen adyacentes a?

No puedo encontrar el número total de permutaciones. Pero ¿Cómo encontrar el número de permutaciones de adyacente de Un?

así que, mi respuesta va a ser..

Respuesta = número total de permutaciones - número total de permutaciones de adyacente de Un

Answer 1

Podemos omitir la Inclusión/Exclusión mediante una modificación menor de Estrellas y Barras.

Primero arreglar las $8$ no. El número de arreglos es el coeficiente multinomial $$\binom{8}{2,2,2,1,1}.$$ Alternativamente, poner una pegatina en uno de los dos L, uno de los dos S, y uno de los dos E, para distinguirlos. El $8$ distintas letras pueden ser dispuestos en $8!$ maneras. Quitar las pegatinas, de una en una. Cada vez que quitar una pegatina, $2!$ arreglos colapso en $1$. Por lo que el número de acuerdos de la $8$ letras es $$\frac{8!}{2!2!2!}.$$

El $8$ letras determinar $9$ "agujeros", uno en el extremo izquierdo, uno en el extremo derecho, y siete inter-carta de agujeros. Tenemos que elegir a $3$ de estos agujeros para poner los en. Esto se puede hacer en $\binom{9}{3}$ maneras.

De ello se deduce que el número de palabras sin dos de Un adyacente es $$\binom{8}{2,2,2,1,1}\binom{9}{3} \qquad\text{or equivalently}\qquad\frac{8!}{2!2!2!}\binom{9}{3} .$$

Calcular. Llegamos $(5040)(84)$,$423360$.

Comentario: De la misma manera, podemos obtener una simple expresión para la respuesta si hay muchas más cartas, entre muchos más. Inclusión/Exclusión también se generaliza, pero poco a poco se vuelve más desagradable.

Answer 2

Hay un total de 11 caracteres, 3 "A", 2 "L", 2 "S", 2 "E" y una "T" y una "H". El número total de permutaciones sin restricciones $n_0$$n_0 =\binom{11}{3,2,2,2,1,1}=\frac{11!}{3! (2!)^3} = 831600$.

Ahora, sustituir a un par de "A" personajes con un doble $\tilde{A}$. El número de permutaciones aquí $n_1 =\binom{10}{1,1,2,2,2,1,1} = 453600$.

La sustitución de un triple de "A" con un solo personaje se $n_2 = \binom{9}{1,2,2,2,1,1} = 45360$.

El número de permutaciones con ningún lado "a"se obtiene por medio de la inclusión-exclusión en el principio de $n = n_0 - n_1 + n_2 = 423360$.

Aquí es Mathematica explícita a contar:

In[3]:= Length@
 DeleteCases[
  Permutations[Characters["TALLAHASSEE"]], {___, "A", "A", ___}]

Out[3]= 423360

Answer 3

Para encontrar el número en el que el As son adyacentes, ponerlos juntos y tratan como una unidad.

Si dos As están juntos, están encontrando las permutaciones de las letras T, L, L, H, S, S, una carta llamada AA, y una carta llamada A. Usted tiene que tener cuidado, sin embargo, ya que usted estará contando los casos en que A va primero, AA va inmediatamente después de tan diferentes de aquellos en los cuales AA va primero, A va inmediatamente después, mientras que son el mismo. Por lo que necesita para "sacar" de la cuenta a quienes permutaciones en la que los tres As están juntos. Cómo contar?

El tratamiento de los tres como una unidad! Ahora usted desea contar el número de permutaciones de las letras T, L, L, H, S, S, y una carta llamada AAA.

Así: el total debe ser:

(Número Total) - (contar con una carta AA y una carta A) + (contar con una carta AAA).