Recurrencia para el número de palabras de longitud $r$ sobre $[n]$ sin tres letras consecutivas iguales

Question

Pregunta

Sea $b_{n,r}$ el número de palabras de longitud $r$ sobre $[n] = \{1,2,\dotsc, n\}$ sin tres letras consecutivas iguales. Muestra que $$ b_{n,r} = (n-1)(b_{n,r-1} + b_{n,r-2})\quad (r>2) $$ con condiciones iniciales $b_{n,1} = n$ y $b_{n,2} = n^2$

Esta pregunta es de la Introducción al Análisis Combinatorio de Riordan.

Contexto

Se sugiere en el problema considerar aquellas secuencias en la pregunta con un elemento dado primero (llamemos a estas $b_{n,r}^\star$) y un par dado de elementos primero (llamemos a estas $b_{n,r}^{\star\star}$) y derivar un sistema de recurrencias con $b_{n,r}$.

Anteriormente resolví el problema correspondiente (sin dos letras consecutivas iguales) con las secuencias correspondientes $a_{n,r}$ y $a_{n,r}^\star$ (aquellas secuencias con un elemento dado primero) y derivé las recurrencias $$ \begin{align} a_{n,r} &= na_{n,r}^\star\\ a_{n,r}^\star &= (n-1)a_{n,r-1}^\star \end{align} $$ lo que implica que $a_{n,r} = n(n-1)^{r-1}$. Se supone que esta pregunta generaliza este tipo de método.

Mi Intento

Con la notación discutida anteriormente pude deducir que $$ \begin{align} b_{n,r} &= nb_{n,r}^\star\\ b_{n,r}^\star &= (n^2-1)b_{n,r-1}^\star \end{align} $$ ya que para la primera posición hay $n$ opciones. Además, una vez que un elemento dado es el primero, hay $n^2-1$ pares que pueden seguir.

Y aquí es donde comienzan mis dudas. Para $b_{n,r}^{\star\star}$, no se puede hacer un análisis sencillo ya que comenzar una secuencia con $00$ y $01$ requiere dos análisis separados.

También parece que, a diferencia del problema anterior, la secuencia derivada $b_{n,r}^{\star\star}$ no es independiente de la elección del par dado para comenzar.

Se prefiere cualquier ayuda con un intento utilizando el contexto, pero otras soluciones también son bienvenidas.

Answer 1

Dejaría que $c_{n,r}$ sea el número de palabras de longitud $r$ que no tienen tres letras consecutivas iguales y no terminan en dos letras iguales y $d_{n,r}$ sea el número de palabras de longitud $r$ que no tienen tres letras consecutivas iguales y terminan en dos letras iguales. Luego podemos escribir recurrencias acopladas $$c_{n,r}=(n-1)(c_{n-1,r}+d_{n-1,r})\\ d_{n,r}=c_{n-1,r}$$ porque dado un $c$ o un $d$ podemos agregar una letra diferente de la última para obtener un $c$. Dado un $c$ podemos agregar una letra que coincida para obtener un $d$. Luego $$\begin {align}b_{n,r}&=c_{n,r}+d_{n,r}\\&=(n-1)(c_{n-1,r}+d_{n-1,r})+c_{n-1,r}\\ &=(n-1)c_{n-1,r}+(n-1)c_{n-2,r}+(n-1)(c_{n-2,r}+d_{n-2,r})\\ &=(n-1)c_{n-1,r}+(n-1)c_{n-2,r}+(n-1)(d_{n-1,r}+d_{n-2,r})\\ &=(n-1)(b_{n-1,r}+b_{n-2,r}) \end {align}$$

Answer 2

Dado que aquí también son bienvenidos otros enfoques, se presenta una técnica llamada Método Cluster de Goulden-Jackson, la cual nos proporciona una función generadora a partir de la cual podemos derivar la relación de recurrencia deseada.

Consideramos las palabras de longitud $r\geq 0$ construidas a partir de un alfabeto $$[n]=\{1,2,3,\ldots,n\}$$ y el conjunto $B=\{111,222,333,\ldots,nnn\}$ de palabras prohibidas, las cuales no pueden formar parte de las palabras que estamos buscando. Derivamos una función generadora \begin{align*} B_n(s)=\sum_{j=0}^\infty b_{n,j} s^j\qquad\qquad n\geq 1 \end{align*> siendo el coeficiente de $s^r$ el número de palabras buscadas de longitud $r$.

Según el artículo (p.7) la función generadora $B_n(s)$ es \begin{align*} B_n(s)=\frac{1}{1-ds-\text{peso}(\mathcal{C})}\tag{1} \end{align*> con $d=n$, el tamaño del alfabeto y $\mathcal{C}$ el numerador de peso con \begin{align*> \text{peso}(\mathcal{C})=\text{peso}(\mathcal{C}[111])+\text{peso}(\mathcal{C}[222])+\cdots+\text{peso}(\mathcal{C}[nnn]) \end{align*> Calculamos según el artículo \begin{align*> \text{peso}(\mathcal{C}[kkk])&=-s^3-\text{peso}(\mathcal{C}[kkk])(s+s^2)\qquad\qquad 1\leq k\leq n\\ \end{align*> y obtenemos \begin{align*> \text{peso}(\mathcal{C}[kkk])=-\frac{s^3}{1+s+s^2}\qquad\qquad 1\leq k\leq n\\ \end{align*> a partir de lo cual \begin{align*> \text{peso}(\mathcal{C})&=\sum_{k=1}^n\text{peso}(\mathcal{C}[kkk]) =-\frac{ns^3}{1+s+s^2}\\ \end{align*> se sigue.

$$ $$

Obtenemos de (1) para $n\geq 2$ \begin{align*> \color{blue}{B_n(s)}&=\sum_{j=0}^\infty b_{n,j}s^j\\ &=\frac{1}{1-ds-\text{peso}(\mathcal{C})}\\ &=\left(1-ns+\frac{ns^3}{1+s+s^3}\right)^{-1}\\ &\color{blue}{=\frac{1+s+s^2}{1-(n-1)s-(n-1)s^2}}\tag{2}\\ &=1+ns+n^2s^2+n(n^2-1)s^3+n(n^3-2n+1)s^4+\cdots \end{align*>

donde la última línea fue calculada con la ayuda de Wolfram Alpha.

$$ $$

Podemos derivar la relación de recurrencia a partir de (2) mediante la multiplicación por el denominador \begin{align*> B_n(s)(1-(n-1)s-(n-1)s^2)&=1+s+s^2\tag{3}\\ \end{align*> a partir de lo cual, extrayendo el coeficiente de $s^r\,(r>2)$, se obtiene \begin{align*> \color{blue}{b_{n,r}-(n-1)b_{n,r-1}-(n-1)b_{n,r-2}=0} \end{align*>

Answer 3

Usando la notación dada,

$$b^\star_{n,r}=(n-1)(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})\tag{1}$$

ya que una secuencia que comienza con exactamente una copia de una letra en particular puede ser seguida por una secuencia que comienza con exactamente 1 copia o 2 copias de las $n-1$ letras restantes.

También

$$b^{\star\star}_{n,r}=(n-1)(b^\star_{n,r-2}+b^{\star\star}_{n,r-2})\, ,\tag{2}$$

usando un razonamiento similar para secuencias que comienzan con exactamente dos copias de una letra en particular.

Ahora, dado que hay $n$ letras posibles para el primer lugar, tenemos

$$b_{n,r}=n(b^\star_{n,r}+b^{\star\star}_{n,r})\tag{3}$$

secuencias válidas en total.

Podemos usar $(1)$, $(2)$ y $(3)$ para obtener

$$\begin{align}b_{n,r}&=n(b^\star_{n,r}+b^{\star\star}_{n,r})\\[1ex] &=n((n-1)(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})+(n-1)(b^\star_{n,r-2}+b^{\star\star}_{n,r-2}))\\[1ex] &=(n-1)(n(b^\star_{n,r-1}+b^{\star\star}_{n,r-1})+n(b^\star_{n,r-2}+b^{\star\star}_{n,r-2})\\[1ex] &=(n-1)(b_{n,r-1}+b_{n,r-2})\, .\tag*{$\blacksquare$}\end{align}$$

Por cierto: ¡ese es un libro increíble en mi opinión! Recomiendo altamente los dos capítulos sobre polinomios de torre.

Answer 4

Usando el diagrama de Sopa y Costrones - una explicación de la teoría GJ

Este autómata produce cadenas con multiplicidades. Sin embargo, las multiplicidades se registrarán en la función generadora. Por ejemplo, el cluster 11111 se genera con multiplicidad 8 pero se registrará exactamente como $1 + 3t + 3t^2 + t^3$ en la función generadora "al menos".

1. 1 1 1 1 1 no tiene t
2. 111 1 1 - al menos un mal 111 (en la primera posición)
3. 1 111 1 - al menos un mal 111 (en la segunda posición)
4. 1 1 111 - al menos un mal 111 (en la tercera posición)
5. 111 1 1 - al menos dos mal 111 (en las primeras dos posiciones)
6. 111 11 - al menos dos mal 111 (en la primera y tercera posición)
7. 1 111 1 - al menos dos mal 111 (en la segunda y tercera posición)

8. 111 1 1 - los tres malos 111

   $$C_k = k^3t + (k + k^2)tC_k$$ por lo tanto cada $C_k$ tiene la función generadora

   $$ \frac {s^3t} {1 - st - s^2t}$$

Con el diagrama tenemos $$S = 1 + nsS + nCS$$ por lo que la función generadora para S es

$$ \frac 1 { 1 - ns - n \frac {s^3t} {1 - st - s^2t} }$$

Por el principio de inclusión-exclusión de Goulden-Jackson, tenemos $Exact(t) = AtLeast(t-1)$ y estamos interesados en $Exact(0)$ así que tomamos $t = -1$ en el anterior y obtenemos el resultado esperado - previamente presentado.