¿Cuántos arreglos de las letras de la palabra CALIFORNIA no tiene ninguna letra consecutiva el mismo?

Question

En primer lugar, la respuesta correcta es $$584,640 = {10!\over 2!2!}- \left[{9! \over 2!}+{9! \over 2!}\right] + 8!$$, que se pueden encontrar a través de la inclusión-exclusión principio.

Mi propio enfoque es diferente de la anterior: En el mundo de CALIFORNIA, tenemos 2 repitiendo Una y 2 I, y los 6 restantes unrepeated letras. Tenemos el primer lugar el 6 unrepeated letras, un total de 6! los arreglos. Entonces, para evitar que se la de a y B en posiciones consecutivas, se coloca el 2 a y 2 B, entre el 6 cartas, entre el principio y final de posiciones, lo que nos da 8 posiciones posibles. El número de posibles arreglos es la permutación de 7 de los 4, pero tenemos que dividir la repetición de a y B, que se $${7!\over 2!2!3!}$$ So in total, we have $${6!7!\over 2!2!3!} = 151,200$$ que es obviamente diferente de la respuesta correcta. ¿Por qué esta mal, y si es posible, ¿cómo puedo solucionar esto usando el mismo enfoque?

Answer 1

Modificar su enfoque por primera colocación de la Una, poniendo el yo.

Podemos organizar las seis distintas letras C,L,F,S,R,N $6!$ maneras. Esto crea siete espacios, cinco entre sucesivas cartas y dos en los extremos de la fila.

Caso 1: se elige dos de estos siete espacios en los que colocar los dos, lo que los separa.

Ahora tenemos ocho letras. Esto crea nueve espacios, siete entre sucesivas cartas y dos en los extremos de la fila. Elegimos dos de estos nueve espacios para el yo. El número de este tipo de acuerdos es $$6!\binom{7}{2}\binom{9}{2} = 544,320$$

Caso 2: colocamos tanto en el mismo espacio.

Tenemos de nuevo ocho letras. De nuevo, esto crea nueve espacios. El espacio entre los dos deben ser llenados con una I. por lo Tanto, hay ocho maneras de elegir la posición de la otra I. El número de este tipo de acuerdos es $$6!\binom{7}{1}\binom{8}{1} = 40,320$$

Total: Estos dos casos son mutuamente excluyentes. Por lo tanto, el número total de acuerdos de las letras de la palabra CALIFORNIA en la que no hay dos consecutivos letras tienen el mismo se $$6!\left[\binom{7}{2}\binom{9}{2} + \binom{7}{1}\binom{8}{1}\right] = 584,640$$ lo cual está de acuerdo con el resultado obtenido mediante la Inclusión-Exclusión Principio.

Answer 2

$\underline{A\; shorter\; method}$

Supongamos $2$ objetos que deben ser mantenidos aparte en una permutación, hay $2$ bien conocidos los métodos de

• el "método del déficit", donde estos $2$ objetos se colocan en los huecos (incl. termina)

• el "método de sustracción" [ total de permutaciones - $2$ objetos juntos ]

Hallar el número de maneras de $A's$ $I's$ están separados por la sucesiva aplicación

• $A's$ separados o juntos, $I's$ además $= (8!/2!)\binom92= 725,760$

• $ A's$ juntos, $I's$ además $= 7!\binom82 = 141,120$

• así, tanto la $A's$ $I's$ aparte = $725,760 - 141,120 = 584,640$

Answer 3

Hay sólo $3$ patrones para la primera colocación de la $A's \; and\; I's\;$ algunos de los cuales necesitan separadores pegados a la primera aparición de la"doble(s)" y muestra por grandes de la letra(s).

Tanto "dobles" juntos:
${\Large A}A{\Large I}I\quad or \quad{\Large I}I{\Large A}A$ que el uso de hasta dos de las otras letras en $6\cdot5$ formas,
y el resto de $4$ puede ser sucesivamente inserta en $5\cdot 6\cdot 7\cdot 8$ formas

Uno doble:
$A{\Large I}IA \quad or \quad I{\Large A}AI$, que utiliza una letra en $6$ formas
y el resto de $5$ puede ser sucesivamente inserta en $5\cdot6\cdot7\cdot8\cdot9$ formas

No dobles:
$AIAI\quad or \quad IAIA$
y el resto de $6$ puede ser insertado en $5\cdot 6\cdot 7\cdot 8\cdot 9\cdot 10$ formas

Sumando, obtenemos $2\cdot 5\cdot 6\cdot 7 \cdot 8(6\cdot 5 +6\cdot 9+ 9\cdot 10) = 584,640$

AGREGÓ

Me posteriormente se encontró un método más corto, que estoy publicando por separado, pero salir de esta, también.

Answer 4

El problema aquí es que no se trata de contar la posibilidad de que un $A$ e una $I$ podría estar en el mismo "espacio", como en esta cadena: $$CALIFORNIA$$ Aquí, no tenemos consecutivos mismas letras, pero "yo" y "a", ambos en la final, en el séptimo espacio, el cual no está de contabilidad.

Por lo tanto, debemos tener en cuenta el $A$s y $I$s por separado. Tenemos $6!$ distintos arreglos de las distintas cartas y luego se puede poner el $A$s en $7 \choose 2$ spots y luego se puede poner el $I$s en $7 \choose 2$ spots, por lo tanto tenemos: $$6\cdot {7 \choose 2}\cdot {7 \choose 2}=317520$$ Esto es incorrecto, sin embargo, porque no estamos de contabilidad para la orden de $A$ $I$ si están en el mismo espacio. Si usted puede averiguar cómo tener en cuenta que, usted puede salvar su método, pero creo que la inclusión-exclusión es bastante más fácil en este momento.

Answer 5

Una manera de ver esto es la enumeración de varios conjuntos.

En primer lugar, ¿cuántas permutaciones de california contienen aa y ii? Vamos a llamar a ese conjunto $C$, y su tamaño es de $|C|$.

En segundo lugar, cómo muchos de ellos contienen aa? Y cuántas ii? Vamos a llamar a estos conjuntos de $A$$I$.

Vamos a llamar el número total de permutaciones $U$. El conjunto de las permutaciones que contienen no consecutivos letras es, por tanto,$U - A - I + C$. Y por lo que el número que estamos buscando es $|U| - |A| - |I| + |C|$.

Debemos volver a agregar $C$ porque es el área de superposición en el diagrama de Venn. Es decir, tanto el conjunto de $A$ y establezca $I$ contienen $C$, y por lo que si restamos les de $U$ a través de la diferencia de conjuntos, nos terminan restando $C$ dos veces. $A$ contiene $C$ debido a que el conjunto de todas las permutaciones de california que contengan aa incluye todas las permutaciones que contengan ii también, y de ese subconjunto de $A$ corresponde a $C$.

Vamos a tratar con el conjunto C:

Esto puede ser contestada como: dada una matriz de diez lugares, ¿de cuántas maneras distintas podemos colocar el dígrafo aa y ii en la matriz? Cada una de estas formas de hojas seis espacios, que luego se llenan de permutaciones de cflnor: el resto de las letras en california. Multiplicamos junto a estas posibilidades: es decir $6!$ multiplicado por el número de maneras de llenar los bigramas.

Ahora, hay 9 maneras de lugar aa en la matriz, obviamente. De estos 9 maneras, el borde de las colocaciones aa........ y ........aa, soporte 7 maneras de agregar un ii. Todos los 7 de interior colocaciones de apoyo 6 maneras de introducir la ii. Así que las posibilidades son $2\times 7 + 7\times 6 = 56$.

Por lo tanto $|C| = 56\times 6! = 56\times 720 = 40320$.

Algunos diagramas:

Edge aa-relleno:

aaii...... 1
aa.ii..... 2
aa..ii.... 3
aa...ii... 4
aa....ii.. 5
aa.....ii. 6
aa......ii 7

Interior aa-relleno:

.aaii..... 1
.aa.ii.... 2
.aa..ii... 3
.aa...ii.. 4
.aa....ii. 5
.aa.....ii 6

iiaa...... 1
..aaii.... 2
..aa.ii... 3
..aa..ii.. 4
..aa...ii. 5
..aa....ii 6

Ahora vamos a tratar con Un I. y son fáciles de espejo de los casos. Básicamente, tenemos nueve maneras de colocar aa en diez espacios, dejando ocho espacios, que luego se llenan de permutaciones de las letras restantes. Por lo tanto $|A| = 9\times 8! = 9! = 362880$ también $|I| = 362880$.

De curso $|U| = 10! = 3628800$.

Ahora podemos calcular el $|U| - |A| - |I| + |C| = 3628800 - 2\times 362880 + 40320 = 2943360$.

Oops: no se valida por la máquina:

$ txr -i
1> (count-if (notf (op search-regex @1 #/aa|ii/)) (perm "california"))
2338560

La respuesta correcta es 2338560.

A continuación ...

(Matemáticas ha cliffhangers también!)

Y aquí es donde metí la pata! En el cálculo de las cardinalidades $|C|$$|A| = |I|$, supuse que no es sólo uno de los distintos aa y ii: que tanto a-s son el mismo objeto. Pero en realidad son distintos: hay dos aa de los bigramas y dos ii de los bigramas (estoy tratando de permutaciones que no necesita ser distintas). Por lo tanto, la $|C|$ es en realidad cuatro veces mayor, debido a las cuatro combinaciones de los bigramas, por lo tanto $4\times 56\times 720 = 161280$. Del mismo modo, $|A|$ $|I|$ es el doble de grande: $2\times 9!$. Con estas correcciones, $|U| - |A| - |I| + |C| = 2338560$.

Ahora supongamos que queremos considerar sólo distintas permutaciones, de modo que no es exactamente un dígrafo aa y un dígrafo ii. La cardinalidad de la nueva $|U|$ se reduce por un factor de cuatro, ya que las cadenas que se diferencian sólo en el intercambio de una a con el otro, y uno i con el otro son equivalentes. Es $|U| = \frac{10!}{2} = 907200$. El original de la $|C| = 40320$ valor es correcto, ya que el cálculo se considera tanto i-s y a-s como indistinta. La correcta $|A|$ cálculo $|A| = |I| = 9!\div 2 = 181440$: debemos dividir por dos, ya que el resto de las letras después de que el dígrafo se coloca incluyen dos que son indistintos. Y por lo $|U| - |A| - |I| + |C| = 907200 - 2\times 181440 + 40320 = 584640$.

Comprobación de la máquina:

3> (count-if (notf (op search-regex @1 #/aa|ii/)) (uniq (perm "california")))
584640

Así que esas son las respuestas: si el i-s y a-s se consideran distintos, a continuación, $2338560$ permutaciones no contienen un dígrafo. Si se considera que son indistintas, a continuación, $584640$ permutaciones no contienen un dígrafo.