Arreglar una palabra con condición.

Question

Por favor, ayúdame a resolver la siguiente pregunta.

¿Cuántas palabras puede fijar de $\{0,1,2, ..., m-1\}$ en longitud $n$ cuando el número de ceros de la palabra es impar?

Ejemplos de palabras válidas: $001, 00, 00m-1, 002$ y así sucesivamente.

Gracias de antemano.

Answer 1

Dejemos que $a_n$ sea el número de palabras de longitud $n$ con un número par de $0$ 's, y $b_n$ el número con un número impar de $0$ 's. Tenemos las siguientes recurrencias: $$a_{n+1}=(m-1)a_n+b_n;\qquad b_{n+1}=a_n+(m-1)b_n.$$ Porque para hacer una palabra de longitud $n+1$ con un número par de $0$ se añade uno de los siguientes elementos $1,2,\dots, m-1$ a un $n$ -palabra de letras con un número par de $0$ o añadir $0$ a un $n$ -palabra de letras con un número impar de $0$ 's. El argumento para la segunda recurrencia es casi el mismo.

Hay ,muchas maneras de resolver el sistema anterior. Una forma sencilla que aprovecha la simetría es restar. Obtenemos $$a_{n+1}-b_{n+1}=(m-2)(a_n-b_n).\tag{1}$$ Tenemos $a_0=1$ (la palabra vacía) y $b_0=0$ . O, para los que no les gusta la palabra vacía, tenemos $a_1=m-2$ amd $b_1=1$ . Así, a partir de (1) obtenemos $$a_n-b_n=(m-2)^n.\tag{2}$$ El número total de palabras de longitud $n$ es $m^n$ y por lo tanto $$a_n+b_n=m^n.\tag{3}$$ Las ecuaciones (2) y (3) son ecuaciones lineales en las dos "incógnitas" $a_n$ y $b_n$ . Resuelve.