$\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?



1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .