Counting The Number Of K-Bounded Good Lists Of Length N

Question

Problem Statement:
A k-bounded list of length n is a sequence [x₁, x₂, . . . , x_n] where each x_j is an integer between 0 and k, inclusive. A good list is one that does not contain three consecutive values 0, 1, 0. For example, for n = 4 and k = 2, [2, 0, 0, 1] and [1, 0, 0, 1] are good lists while [0, 1, 0, 2] and [0, 0, 1, 0] are not. Let good(n, k) be the number of good k-bounded lists of length n. For instance, the good 1-bounded lists of length 2 are {[0, 0], [0, 1], [1, 0], [1, 1]}, so good(2, 1) = 4. Similarly, you can check that good(4, 1) = 12 and good(3, 2) = 26. Your task is to compute good(n, k) for the following values of n and k.

(a) good(7, 1)
(b) good(7, 3)
(c) good(20, 1)

Note: This is a question from a past contest and the official answers for the parts a, b and c are as follows:

(a) good(7, 1) = 65
(b) good(7, 3) = 15163
(c) good(20, 1) = 97229

My Approach: I came up with the following recurrence relations,
$$p(i,0) = p(i-1,0) + p(i-1,1) - p(i-2,0)$$ $$p(i,1) = [p(i-1,0) + p(i-1,1)]\times k$$ where $p(i,0)$ is the number of good lists of length $i$ ending with 0 and $p(i,1)$ is the number of good lists of length i not ending with 0. The idea behind this is that every good list of length $i$ is an extension of a good list of length $i-1$ but there can also be some bad extensions in the process, hence it is better to handle them separately. Therefore, in case a good list ends with 0,1 then we need to take care of the fact that while extending this list we don't count the lists where we place a 0 at the end, otherwise we will have 0,1,0 in the list. So what we do is that we just count all the lists of length $i$ ending with 0 and then subtract the lists of length $i-2$ that end with a 0. Whereas the case where we do not use a 0 at the end is a bit simpler.
I just filled the table for the above recurrence manually with the initial values as $p(0,0) = 0$, $p(0,1) = 0$, and $p(1,0) = 1$, $p(1,1) = k$ (since it was a pen and paper exam) and could arrive at the answers which is the sum of $p(n,0)$ and $p(n,1)$ [C++ code for reference: https://ideone.com/wSVhVL]. But then I have been thinking whether this problem has a closed form solution, some function in n and k. I couldn't arrive at one until now. Can anyone provide some combinatorial insight? Is a closed form solution possible?

Answer 1

I am going to use Chomsky-Schutzemberger method to find the generating function of this (you put DP as tag, so I guess you are interested in computational stuff). Consider the following automaton that accepts the good lists.

If you label $A,B,C,D$ the nodes of the automaton, then the following system of equations gives you the generating function of the number of strings of size $n$ that the automaton accepts. $$A=1+kxA+xB, \, B=xB+xC+(k-1)xA+1,C=\, kxA+1.$$ We omit $D$ because is a state that dies. Doing the substitution, you get $$(1-kx)A=1+xB=1+x\frac{x+kx^2A+(k-1)xA+1}{1-x},$$ So $$A=\frac{1+\frac{x^2+x}{1-x}}{1-kx-\frac{kx^3+(k-1)x^2}{1-x}},$$ hence $$A=\frac{1+x^2}{(1-x)(1-kx)-(kx^3+(k-1)x^2)}=\frac{1+x^2}{1-(k+1)x+x^2-kx^3}=\frac{1}{1-\left ( kx+\frac{x}{1+x^2}\right ) }.$$ This agrees with your findings.

One can try to factor the denominator to try to use partial fractions and get a formula. The problem is that this polynomial does not seem to have a nice factorization (for low $k'$s) that would be enough evidence to me that a "nice close formula" is not possible. OEIS just seems to have $k=1$.

Case k=1: The OEIS gives that $$a_n = \sum_{k=0}^{n+2} \binom{n+2-k}{2k}.$$ which says that somehow a tiling problem can be attach to this(reminds me of Fibonacci).

General case: A very ugly but closed formula can be seen to be $$a_n=\sum _{i=0}^n\sum _{\substack{a_0+2a_1+4a_2+\cdots +2\ell \cdot a_{\ell}+\cdots =n-i\\ a_0+a_1+\cdots =i}}\frac{i!}{\prod _{j=0}^{\infty} a_j!}(k+1)^{a_0}(-1)^{a_1+a_3+\cdots +a_{2\ell +1}+\cdots }$$

Answer 2

I believe that this is from a hand-written Computing contest, where you're expected to use algorithms to evaluate these finite cases. If so, the goal is to come up with a simple equation to describe the scenario, and then iterate to the corresponding $n,k$ values.

Fill in the gaps as needed, especially when it says "Show that". If you're stuck, explain what you've tried and why it doesn't seem to work.

---

Let

• $A_k (n)$ be the number of $k-$bounded lists of length $n$ that end with $0$.
• $B_k (n)$ be the number of $k-$bounded lists of length $n$ that end with $0, 1$.
• $C_k (n)$ be the number of $k-$bounded lists of length $n$ that end with "not $0$, and not $0,1$".

We are after $A_k (n) + B_k(n) + C_k(n)$.

Show that we have the recurrence relations

• $A_k(n+1) = A_k(n) + C_k(n)$.
• $B_k(n+1) = A_k(n)$
• $C_k (n+1) = (k-1) A_k (n) + (k) B_k (n) + (k) C_k(n) $

Show also that we have the initial values

• $A_k(2) = k+1 $
• $B_k(2) = 1 $
• $C_k(2) = (k+1)^2 - (k+1) - 1 = k^2 + k -1$.

---

For example, here is good$(7,3)$.

Answer 3

The following answer is based upon the Goulden-Jackson Cluster Method which provides a convenient technique to solve problems of this kind. We consider the set of words of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{A_0,A_1,\ldots, A_{k}\}$$ of size $k+1$ and the set $B=\{A_0A_1A_0\}$ containing a bad word of length $3$, which is not allowed to be part of the words we are looking for.

---

Generating function $f_k(t)$: We derive a generating function $f_k(t)$ with the coefficient of $t^n$ being the number of wanted words of length $n$.

According to the paper (p.7) the generating function $f_k(t)$ is \begin{align*} f_k(t)=\frac{1}{1-(k+1)t-\text{w}(\mathcal{C})}\tag{1} \end{align*} with $k+1=|\mathcal{V}|$ the size of the alphabet and $\text{w}(\mathcal{C})$ the weight-numerator of bad words with \begin{align*} \text{w}(\mathcal{C})=\text{w}(\mathcal{C}[A_0A_1A_0])\tag{2} \end{align*}

We calculate according to the paper: \begin{align*} \text{w}(\mathcal{C}[A_0A_1A_0])&=-t^{3}-t^2\text{w}(\mathcal{C}[A_0A_1A_0])\tag{3}\\ \end{align*} where the expression $t^2\text{w}(\mathcal{C}[A_0A_1A_0])$ accounts for overlappings of $A_{0}A_1A_0$ with itself. We obtain from (3): \begin{align*} \text{w}(\mathcal{C}[A_0A_1A_0])&=-\frac{t^3}{1+t^2} \end{align*} It follows from (1) - (3): \begin{align*} \color{blue}{f_k(t)}&=\frac{1}{1-(k+1)t-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-(k+1)t+\frac{t^3}{1+t^2}}\\ &\,\,\color{blue}{=\frac{1+t^2}{1-(k+1)t-t^2-kt^3}}\tag{4} \end{align*} and conclude the number of valid words of length $n\geq 0$ is the coefficient of $t^n$ in (4).

Coefficient extraction: We use the coefficient of operator $[t^n]$ to denote the coefficient of $t^n$ of a series. Applying standard techniques to extract the coefficient $[t^n]$ from $f_k(t)$ we obtain for $n\geq 2$: \begin{align*} \color{blue}{[t^n]f_k(t)}&\color{blue}{=\sum_{j=0}^{n}(-1)^j\sum_{l=0}^j\binom{n-j}{l}\binom{l}{j-l}k^{j-l}(k+1)^{n-j-l}}\\ &\qquad\color{blue}{+\sum_{j=0}^{n-2}(-1)^j\sum_{l=0}^j\binom{n-2-j}{l}\binom{l}{j-l}k^{j-l}(k+1)^{n-2-j-l}}\tag{5} \end{align*}

Calculation: We derive from (5)

\begin{align*} \color{blue}{[t^7]f_1(t)}&=\sum_{j=0}^{7}(-1)^j\sum_{l=0}^j\binom{7-j}{l}\binom{l}{j-l}2^{7-j-l}\\ &\qquad+\sum_{j=0}^{5}(-1)^j\sum_{l=0}^j\binom{5-j}{l}\binom{l}{j-l}2^{5-j-l} \color{blue}{=65}\\ \color{blue}{[t^7]f_3(t)}&=\sum_{j=0}^{7}(-1)^j\sum_{l=0}^j\binom{7-j}{l}\binom{l}{j-l}3^{j-l}4^{7-j-l}\\ &\qquad+\sum_{j=0}^{5}(-1)^j\sum_{l=0}^j\binom{5-j}{l}\binom{l}{j-l}3^{j-l}4^{5-j-l} \color{blue}{=15\,163}\\ \color{blue}{[t^{20}]f_1(t)}&=\sum_{j=0}^{20}(-1)^j\sum_{l=0}^j\binom{20-j}{l}\binom{l}{j-l}2^{20-j-l}\\ &\qquad+\sum_{j=0}^{18}(-1)^j\sum_{l=0}^j\binom{18-j}{l}\binom{l}{j-l}2^{18-j-l}\color{blue}{=97\,229}\\ \end{align*}

which has been programmatically verified.