Todos los ternario n-palabras con una suma de dígitos y un cero.

Question

Estoy tratando de encontrar una fórmula recursiva para todos los ternario (usando ${0,1,2}$) secuencias de longitud $n$ que contienen al menos un cero, y tienen incluso una suma de dígitos.

Mi intento hasta ahora se agrega a continuación. Creo que la idea es buena, pero la recurrencia de la relación yo no se llevará a cabo cuando el valor en números (y no siempre es un número entero..). alguna idea?

Indicar con $f\left(n\right)$ el número de secuencias como en la pregunta, $\bar{f}\left(n\right)$ como el número de secuencias con al menos un 0 con un número impar de dígitos, y como $g\left(n\right)$ el número de secuencias con una suma de dígitos y sin ceros.

Para cualquier secuencia, la suma de los dígitos sería aún si y sólo si hay un número par de 1s, por lo tanto, cualquier legales secuencia de longitud $n$ se puede lograr en una única manera de salir de los siguientes:

• A partir de una secuencia donde las cifras son aún y no es cero, anexar a cero al final. Hay $g\left(n-1\right)$ dichas secuencias.

• A partir de la secuencia de longitud $n-1$, anexar 0 o 2 a la final, añadiendo $2f\left(n-1\right)$ secuencias.

• A partir de una secuencia con un cero donde la suma de los dígitos es un número impar, anexar 1, al final, añadiendo $\bar{f}\left(n-1\right)$ secuencias.

Estos nos da ese $$f\left(n\right)=2f\left(n-1\right)+\bar{f}\left(n-1\right)+g\left(n-1\right)$$

Considerando $g\left(n\right)$ en primer lugar, estamos interesados en las cadenas de longitud n de$\left\{ 1,2\right\} $, con un número par de 1s. Hay una sencilla bijection para el conjunto de cadenas de longitud $n$ con un número impar de 1s "cambiando" el primer valor, y como estos conjuntos incluyen todas las posibilidades, sin solapamiento, se deduce que el $g\left(n\right)=2^{n-1}$.

El próximo mirando a $\bar{f}\left(n-1\right)$. Podemos utilizar el hecho de que las secuencias con un cero donde la suma de los dígitos es impar y las secuencias con un cero donde la suma de los dígitos es aún son exactamente un discontinuo de la unión de todas las secuencias con un cero.

Como hay $n\cdot3^{n-1}$ dichas secuencias (primero escogemos un lugar a ser 0, y llenar el resto normalmente), obtenemos que $\bar{f}\left(n\right)+f\left(n\right)=n\cdot3^{n-1}$ o $\bar{f}\left(n\right)=n\cdot3^{n-1}-f\left(n\right)$

Poniendo esto todos juntos tenemos que $$f\left(n\right)=2f\left(n-1\right)+\left(n-1\right)\cdot3^{n-2}-f\left(n-1\right)+2^{n-2} o f\left(n\right)=f\left(n-1\right)+\left(n-1\right)\cdot3^{n-2}+2^{n-2}$$

Answer 1

Deje $E(n)$ contar el número de ternario $n$-cadenas, incluso con la suma, y deje $e(n)$ contar el número de binario $n$-cadenas, usando sólo los dígitos $1$$2$, incluso con la suma. Quieres una fórmula para

$$f(n)=E(n)-e(n)$$

Primero nos tenga en cuenta que $e(n)=2^{n-1}$, ya que la paridad de que el último dígito es determinado por la elección de la primera $n-1$ dígitos. Como para $E(n)$, si dejamos $O(n)$ contar el número de ternario $n$-cadenas con extraño suma, vemos que

$$E(n)=2E(n-1)+O(n-1)=2E(n-1)+(3^{n-1}-E(n-1))=E(n-1)+3^{n-1}$$

Poniendo a estos en conjunto, se han

$$\begin{align} f(n)&=E(n)-2^{n-1}\\ &=E(n-1)+3^{n-1}-2^{n-1}\\ &=E(n-1)-2^{n-2}+2^{n-2}+3^{n-1}-2^{n-1}\\ &=f(n-1)+3^{n-1}-2^{n-2} \end{align}$$

Como una comprobación de validez, sabemos que $f(1)=1$, por lo que tenemos

$$\begin{align} f(2)&=1+3-1=3\\ f(3)&=3+9-2=10 \end{align}$$

que se puede comprobar fácilmente con la mano. (Me resulta muy útil para ejecutar comprobaciones de validez, porque casi siempre al menos un error cuando la primera derivada de una fórmula. En este caso no fue la excepción.)

Comentario: una Vez que usted tiene la fórmula recursiva $f(n)=f(n-1)+3^{n-1}-2^{n-2}$, no es difícil demostrar (por inducción) la fórmula $f(n)=(3^n-2^n+1)/2$ (ver Jack D'Aurizio la respuesta):

$$\begin{align} f(n)&={3^{n-1}-2^{n-1}+1\over2}+3^{n-1}-2^{n-2}\\ &={3^{n-1}-2^{n-1}+1+2\cdot3^{n-1}-2^{n-1}\over2}\\ &={(1+2)3^{n-1}-2\cdot2^{n-1}+1\over2}\\ &={3^n-2^n+1\over2} \end{align}$$

Answer 2

La recurrencia enfoque no es estrictamente necesario. La paridad de la suma de dígitos, obviamente, depende del número de $1$s; el número ternario de las cadenas que tienen una longitud de $n$ con exactamente $k$ dígitos $1$ y al menos un dígito $0$$\binom{n}{k}\cdot\left(2^{n-k}-1\right)$. La respuesta es entonces:

$$\begin{eqnarray*} \sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2j}\left(2^{n-2j}-1\right)&=&-2^{n-1}+\sum_{j=0}^{\left\lfloor\frac{n}{2}\right\rfloor}\binom{n}{2j}2^{n-2j}\\&=&-2^{n-1}+\frac{1}{2}\sum_{k=0}^{n}\binom{n}{k}2^{n-k}((-1)^k+1^k)\\&=&\color{red}{\frac{3^n-2^n+1}{2}}.\end{eqnarray*} $$ Que hace que los sentidos: $2^n$ cadenas sin dígitos $0$, y entre el resto de los $3^n-2^n$ es razonable esperar que alrededor de la mitad de ellos tiene incluso una suma de dígitos.

Answer 3

Inspirado por Jack D'Aurizio post:

Hay $\ 3^n$ ternario cadenas de longitud $\ n$ en total, y $\ 2^n$ no $\ 0$. Del resto de las $\ 3^n - 2^n$, uno es la cadena con nada sino $\ 0$, y el resto tienen al menos un elemento no nulo. Como señaló en su propia prueba, el mapa que intercambia el primer elemento no nulo entre el $\ 1$ $\ 2$ es un bijection entre las cadenas con pares e impares sumas. Así $$\frac{3^n - 2^n - 1}{2}$$ of them will be even. Adding in the $\ 0$-string as also having an even sum gives $$\frac{3^n - 2^n + 1}{2}$$ como el número de cadenas de caracteres con al menos un $\ 0$, e incluso el de la suma.

Answer 4

Su error es el recuento de $\overline f(n-1)$. En el siguiente párrafo, que son el recuento $\overline f(n)$, no $\overline f(n-1)$. También recuento de las cadenas con más de un cero varias veces. La cadena de $0001$ sería contado tres veces, una vez para cada cero. No veo la forma de conseguir que no integral de los valores-no existe la división en cualquier lugar.

Añadido: yo también definiría $\overline g(n)$ como las cuerdas de un extraño suma y no tiene ceros. Su argumento de que $g(n)=2^{n-1}$ se aplica a $\overline g(n)$. Su recurrencia para $f(n)$ está bien. Para obtener $\overline f(n)$ usted puede comenzar con $\overline f(n-1)$ y añadir un $0$ o $2$,comenzar con una cadena de longitud $n-1$, e incluso el de la suma y anexar una $1$, o comenzar con una cadena de longitud $n-1$ con extraño suma y no tiene ceros y añadir un cero. Su argumento para $g(n)$ se aplica a la última, para $\overline f(n)=2\overline f(n-1)+f(n-1)++\overline g(n-1)=2\overline f(n-1)+f(n-1)$+2^{n-2}$

Answer 5

Como una adición a Barry la respuesta de arriba, aquí te muestro cómo resolver de la forma cerrada de la recurrencia de la relación directa.

Dada la recurrencia de la forma $f(n)=f(n-1)+3^{n-1}-2^{n-2}$ y la condición inicial $f(1)=1$ encontramos por primera vez lo que la solución homogénea.

El polinomio característico será de la forma $x-1=0$, entonces sabemos que la solución final será de la forma: $f(n)=c_1\cdot (1)^n + p(n)$ para algunos la solución particular $p(n)$.

Dada nuestra no-homogéneo parte, esperamos que $p(n)=d_13^n+d_22^n$ para algunas constantes $d_1$$d_2$. Conectar por $f(n)$$f(n-1)$, respectivamente, tenemos:

$d_13^n+d_22^n=d_13^{n-1}+d_22^{n-1}+3^{n-1}-2^{n-2}$

Por la agrupación del mismo modo ordenado, esto implica el siguiente sistema de ecuaciones:

$\begin{cases}3d_1=d_1+1\\4d_2=2d_2-1\end{cases}$

lo que implica $d_1=\frac{1}{2}$ $d_2=-\frac{1}{2}$

Por lo tanto, tenemos $f(n)=c_1+\frac{1}{2}3^n-\frac{1}{2}2^n$

El uso de nuestra condición inicial, podemos resolver para $c_1$

$1=c_1+\frac{1}{2}3^1-\frac{1}{2}2^1=c_1+\frac{1}{2}$ lo que implica $c_1=\frac{1}{2}$

Por lo tanto, $f(n)=\frac{1}{2}+\frac{1}{2}3^n-\frac{1}{2}2^n=\frac{3^n-2^n+1}{2}$