Número de formas de organizar la palabra 'KBCKBCKBC'

Question

La palabra 'KBCKBCKBC' es estar dispuestos en una fila de modo tal que ninguna palabra contiene el patrón de KBC.

$Attempt$

Evento de $A$=1 de KBC es en el patrón, $B$=2 KBC es en el patrón y similar es el caso de C.

Ahora se requiere es $n((notA) (notB) (notC)) =Total ways - [\sum n(A) - \sum n(AB)+ \sum n(ABC)] $

Total de maneras = $\frac{9!}{3!3!3!}$

$\sum n(AB) = \frac{5!}{2!}$

$\sum n(ABC) = 1$

Pero, mi principal duda es que no soy capaz de calcular el $\sum n(A)$.

Alguna sugerencia? Por favor, también sugieren acerca de otro método que usted sabe.

Gracias por la ayuda.

Answer 1

El número de palabras válidas es \begin{align*} \frac{9!}{3!3!3!}-\frac{7!}{2!2!2!1!}+\frac{5!}{1!1!1!2!}-\frac{3!}{3!}=1\,680-630+60-1\color{blue}{=1\,109} \end{align*}

Comentario:

• Tenemos en cuenta las palabras de longitud $9$ construido a partir de tres grupos de $BBB,CCC,KKK$, lo que resulta en $\frac{9!}{3!3!3!}$.

• Restamos todas las palabras que tienen al menos una ocurrencia de $BCK$. Pensamos en $BCK$ como un nuevo personaje $X$. Tenemos en cuenta las palabras de longitud $7$ construido a partir de $4$ grupos $BB,CC,KK,X$, lo que resulta en $\frac{7!}{2!2!2!1!}$.

• Hemos restado las cadenas con las ocurrencias de dos veces $BCK$ más de una vez. Como compensación añadimos todas las palabras que contienen al menos dos veces $BCK$. Pensamos en $BCK$ como un nuevo personaje $X$. Tenemos en cuenta las palabras de longitud $5$ construido a partir de $4$ grupos $B,C,K,XX$, lo que resulta en $\frac{5!}{1!1!1!2!}$.

• Hemos añadido las cadenas con las ocurrencias de tres veces $BCK$ más de una vez. Como compensación restamos todas las palabras que contienen al menos tres veces $BCK$. Tenemos en cuenta las palabras de longitud $3$ construido a partir de $1$ grupo $XXX$, lo que resulta en $\frac{3!}{3!}$.

Answer 2

Parece que usted está considerando sólo los tres casos, cuando se $KBC$ aparece en la parte delantera, central y final. De hecho, puede aparecer en otros lugares, como señaló JMoravitz en el comentario.

Deje $A_1,A_2,...,A_7$ indican la posición inicial del bloque de $KBC$. Así, $A_1,A_4,A_7$ corresponden a casos $A,B,C$. Mediante la inclusión-exclusión, el número de palabras con uno, dos o tres palabras bloques de $KBC$es: $$|A_1|+|A_2|+|A_3|+|A_4|+|A_5|+|A_6|+|A_7|-\\ (|A_1A_4|+|A_1A_5|+|A_1A_6|+|A_1A_7|+|A_2A_5|+\\ |A_2A_6|+|A_2A_7|+|A_3A_6|+|A_3A_7|+|A_4A_7|)+\\ (|A_1A_3A_7|)=\\ 7\cdot \frac{6!}{(2!)^3}-10\cdot 3!+1=630-60+1=571.$$ Nota: Muchos superposición de eventos tales como $A_1A_2,A_1A_2A_3,A_1A_2A_3A_4,$ etc se cayó en la expresión anterior y sólo los eventos con los no-cero de cardinalidad se conservan.

El número total de palabras es: $$\frac{9!}{(3!)^3}=1680.$$ Por lo tanto, el número de palabras sin la palabra del bloque de $KBC$ cualquier lugar en el $9$letras de la palabra es: $$1680-571=1109.$$

Answer 3

Esta respuesta se basa en la Goulden-Jackson Clúster Método que es un método conveniente para derivar una generación de función para problemas de este tipo.

Tenemos en cuenta el conjunto de palabras en $ \mathcal{V}^{\star}$ de la longitud de la $n\geq 0$ construido a partir de un alfabeto $$\mathcal{V}=\{B,C,K\}$$ and the set $\mathcal{B}=\{KBC\}$ de malas palabras, que no se les permite ser parte de las palabras que estamos buscando.

Que se derivan de una función de $F(x)$ con un coeficiente de $x^n$ siendo el número de ganas de palabras de longitud $n$ desde el alfabeto $\mathcal{V}$. Según el periódico (p.7) la generación de la función de $F(x)$es \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} con $d=|\mathcal{V}|=3$, el tamaño de las letras del alfabeto y con el peso numerador $\mathcal{C}$con \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[KBC]) \end{align*}

Calculamos de acuerdo con el documento \begin{align*} \text{weight}(\mathcal{C}[KBC])&=-x^3 \end{align*}

Se sigue con un poco de ayuda de Wolfram Alpha \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-3x+x^3}\\ &=1 + 3 x + 9 x^2 + 26 x^3 + 75 x^4 + 216 x^5+622 x^6 \\ &\qquad+ 1\,791 x^7 + 5\,157 x^8 + \color{blue}{14\,849} x^9+42\,756 x^10 +\cdots\tag{1}\\ \end{align*}

Denotando con $[x^n]$ el coeficiente de $x^n$ en una serie que podemos ver en (1) no hay $\color{blue}{14\,849}$ palabras de longitud $9$ que no contienen la cadena de caracteres $KBC$.

Queremos encontrar todas las palabras que tienen exactamente tres ocurrencias de cada una de las letras $B,C,K$. Para encontrar este número hemos de seguir la pista de las letras en la generación de la función de $F(x)$. Lo hacemos a ser la creación de \begin{align*} \color{blue}{G(x)}&\color{blue}{=\frac{1}{1-(B+C+K)x+(BCK)x^3}} \end{align*} y se obtiene mediante la extracción de los coeficiente de $B^3C^3D^3x^9$ de $G(x)$ nuevo con un poco de ayuda de Wolfram Alpha \begin{align*} [B^3C^3D^3t^9]G(x)\color{blue}{=1\,109} \end{align*}

Nota: este ejemplo es relativamente simple, ya que sólo tenemos una mala palabra y esta palabra no tiene ninguna superposición. Una situación con una mala palabra con la superposición de , por ejemplo, con $BCB$ es más difícil de calcular y en tales casos este método muestra más de su poder.