Secuencia finita con ningún dos términos consecutivos

Question

$\newcommand{\N}{\mathbb{N}}$ Deje $n \in \N$, definimos $[n] \doteq \{1 , \ldots, n \}$. Considere el siguiente $$ H_n^k \doteq \{ z \in [n]^k  \mid \forall i \in [k-1]: \ z_{i+1} \neq z_i + 1 \} $$

Donde, $z_i$ es el valor en la posición $i$. En otras palabras, estamos considerando las secuencias de longitud $k$ con elementos en $[n]$, de tal manera que para cada posición de la siguiente no es el sucesor. Por ejemplo, la secuencia de $z = 13476 \notin H_7^5$.

Cómo calcular el $\left | H_{n}^k \right |$ ?

Permítanme mostrarles mi intento. Vamos a definir $$ F_{n}^{i} = \{ z \in [n]^k \mid z_{i+1} = z_i + 1 \} $$ then, what we are looking for is $$n^k - \left | \bigcup\limits_{i=1}^{k-1} F_n^i \right | $$Después, lo que yo quería usar es la inclusión-exclusión en el principio, pero tengo problemas al intentar calcular el cardinal de la intersección de cualquiera de ellos.

Cualquier sugiere?

Saludos!

Answer 1

Los números de $|H_n^k|$ puede ser obtenida a través de la lineal de la relación de recurrencia $$ |H_n^k| = \sum_{i=1}^{n} (-1)^{i+1}(n-i+1)|H_n^{k-i}|, $$ mediante el convenio que $H_n^k$ está vacía si $k<0$, e $|H_n^0|=1$.

Para demostrar esta fórmula, rompemos $H_n^k$ en los siguientes subgrupos: $$J_n^k(i) := \{ z\in H^k_n \ | \ z_1 = i \} \quad (i=1,\ldots, n).$$ En otras palabras, $J_n^k(i)$ es el conjunto de secuencias en $H_n^k$ a partir de con $i$. Obviamente, $|H_n^k| = \sum_{i=1}^n |J_n^k(i)|$. Por otra parte, tenemos los siguientes:

• $|J_n^k(n)| = |H_n^{k-1}|$. En efecto, si la secuencia se inicia con $n$, luego el resto de la $k-1$ términos puede ser cualquier secuencia en la $H_n^{k-1}$.
• Para$j=1,\ldots,n-1$,$|J_n^k(j)| = \sum_{i=1}^{n+1-j}(-1)^{i+1}|H_n^{k-i}|$. Para ver esto, observe que si la secuencia se inicia con $j$, luego el resto de la $k-1$ términos puede ser cualquier secuencia en la $H_n^{k-1}$ que no se inicia con $j+1$. Por lo tanto $|J_n^k(j)| = |H_n^{k-1}|-|J_n^{k-1}(j+1)|$. La anterior igualdad se obtiene por inducción.

Por lo tanto, tenemos $|H_n^k| = \sum_{j=1}^n |J_n^k(j)| = \sum_{j=1}^n \sum_{i=1}^{n+1-j}(-1)^{i+1}|H_n^{k-i}| = \sum_{i=1}^{n} (-1)^{i+1}(n-i+1)|H_n^{k-i}|$.

Esto demuestra la recurrencia de la relación.

El uso de este, es fácil calcular los primeros términos de una secuencia de $|H_n^k|$. Por ejemplo, para $n=3$ y comenzando con $k=0$, obtenemos $1,3,7,16,37,86,200,465,1081, \ldots$ (que, por cierto, es la secuencia de A095263 de la OEIS).

Métodos generales para resolver lineal de relaciones de recurrencia que también podría aplicarse a partir de ahí.