¿Cuántas palabras hay de longitud $7$ están en $\{u,v,w,x,y,z\}$ sin la cadena de letras $xxxx$ ?

Question

¿Cuántas palabras hay de longitud $7$ están en $\{u,v,w,x,y,z\}$ sin la cadena de letras $xxxx$ ?

Mi idea es utilizar la inclusión-exclusión. Estaba pensando en plantear el problema de la siguiente manera: denotando $C_i$ para ser la condición de que las palabras de longitud $7$ son con una cadena de $x's$ de longitud $i$ y que $N$ sea una función que cuente el tamaño del conjunto.

Alors $N(C_5)={3 \choose 1}5^2$ ya que podemos colocar la cadena $xxxxx$ en sólo 3 formas. Entonces, con el resto $2$ podemos elegir cualquier elemento de $\{u,v,w,y,z\}$ al lugar, lo que da $5^2$ posibilidades. Así que por la regla del producto, $N(C_5)={3 \choose 1}5^2$ .

Así es: $$\begin{align} N(C^{\complement}) & =|\{\text{words of length $7$ on the set $\{u,v,w,x,y,z\}$}|-N(C_4)-N(C_5)-N(C_6)-N(C_7) \\ &=6^7-4\cdot5^3-3\cdot5^2-2\cdot5^1-1 \end{align}$$

¿Estoy muy equivocado o tengo la idea correcta?

Answer 1

La idea de restar a $6^7$ el número de cadenas "malas" está bien, al igual que la idea de contar las cadenas malas según la longitud de la cadena única de $x$ (Obsérvese que esto sería mucho más difícil si se tratara de cadenas mucho más largas, ya que dichas cadenas pueden ser malas más de una vez).

Claramente $N(C_7)=1$ , como usted dice, y $N(C_6)=2\cdot5=10$ ya que el no $x$ debe ser uno de $5$ letras y puede estar en cualquiera de los extremos. $N(C_5)$ es un poco más complicado.

• Puedes tener $axxxxxb$ , donde ni $a$ ni $b$ puede ser $x$ ; hay $5^2=25$ cadenas de este tipo.
• Puedes tener $xxxxxab$ o $baxxxxx$ , donde $a\ne x$ y $b$ puede ser cualquiera de los $6$ letras; hay $2\cdot5\cdot6=60$ cadenas de este tipo.

Así, $N(C_5)=25+60=85$ .

Te dejo que intentes arreglar el cálculo de $N(C_4)$ utilizando ideas similares; he dejado la respuesta en el bloque protegido por spoilers de abajo para que puedas comprobarlo tú mismo.

$2\cdot5\cdot6^2+2\cdot5^2\cdot6=660$ .