Finite sequence with no two consecutive terms

Question

$\newcommand{\N}{\mathbb{N}}$ Let $n \in \N$, we define $[n] \doteq \{1 , \ldots, n \}$. Consider the following $$ H_n^k \doteq \{ z \in [n]^k  \mid \forall i \in [k-1]: \ z_{i+1} \neq z_i + 1 \} $$

Where, $z_i$ is the value at the position $i$. In other words, we are considering the sequences of length $k$ with elements in $[n]$, such that for every position the next one is not the succesor. For example the sequence $z = 13476 \notin H_7^5$.

How to calculate $\left | H_{n}^k \right |$ ?

Let me show you my attempt. Let's define $$ 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 | $$Afterwards, what I wanted to use is the inclusion-exclusion principle but I got in troubles when I try to calculate the cardinal of the intersection of any of them.

Any suggests?

Regards!

Answer 1

The numbers $|H_n^k|$ can be obtained via the linear recurrence relation $$ |H_n^k| = \sum_{i=1}^{n} (-1)^{i+1}(n-i+1)|H_n^{k-i}|, $$ using the convention that $H_n^k$ is empty if $k<0$, and $|H_n^0|=1$.

To prove this formula, we break $H_n^k$ into the following subsets: $$J_n^k(i) := \{ z\in H^k_n \ | \ z_1 = i \} \quad (i=1,\ldots, n).$$ In other words, $J_n^k(i)$ is the set of sequences in $H_n^k$ starting with $i$. Obviously, $|H_n^k| = \sum_{i=1}^n |J_n^k(i)|$. Moreover, we have the following:

• $|J_n^k(n)| = |H_n^{k-1}|$. Indeed, if a sequence starts with $n$, then the remaining $k-1$ terms can be any sequence in $H_n^{k-1}$.
• For $j=1,\ldots,n-1$, we have $|J_n^k(j)| = \sum_{i=1}^{n+1-j}(-1)^{i+1}|H_n^{k-i}|$. To see this, notice that if a sequence starts with $j$, then the remaining $k-1$ terms can be any sequence in $H_n^{k-1}$ that does not start with $j+1$. Thus $|J_n^k(j)| = |H_n^{k-1}|-|J_n^{k-1}(j+1)|$. The above equality is then obtained by induction.

Therefore we have $|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}|$.

This proves the recurrence relation.

Using this, it is easy to compute the first terms of a sequence of $|H_n^k|$. For instance, for $n=3$ and starting with $k=0$, we get $1,3,7,16,37,86,200,465,1081, \ldots$ (which, incidentally, is sequence A095263 of the OEIS).

General methods to solve linear recurrence relations could also be applied from there.