Number of ways to colour number line.

Question

I thought of this question:

Consider you have a number line that starts at $0$ and ends at $n$ where $n>0$. Consider there are $k$ number of points on this number line which are said to be lucky, that is $\{a_1,a_2,\ldots,a_k\}$, where all of them are non-negative. Find the number of ways to color a strip or segment of this number line with a paint, so that you paint at least $2$ lucky numbers. The paint begins at a integer point and ends at integer point and your boundary's are $0$ and $n$ (you can color both of them).

For example:

If $n=3$ and $a_1=0$, $a_2=1$, $a_3=2$,

then number of ways is $5$.

Can anybody help me?

Answer 1

Let $a_0=-1$ and $A=\{a_1,\ldots,a_k\}$, where $a_1<a_2<\ldots<a_k$.

Suppose that $1\le i<k$, and suppose further that $a_i$ is the smallest member of $A$ in a strip $S$ that covers at least two members of $A$. The left endpoint of $S$ can be any integer $\ell$ such that $a_{i-1}<\ell\le a_i$, and the right endpoint of $S$ can be any integer $m$ such that $a_{i+1}\le m<n+1$. There are $a_i-a_{i-1}$ such $\ell$ and $n+1-a_{i+1}$ such $m$, so there are $(a_i-a_{i-1})(n+1-a_{i+1})$ such strips $S$. The total number of strips covering at least two members of $A_0$ is therefore

$$\begin{align*} \sum_{i=1}^{k-1}(a_i-a_{i-1})(n+1-a_{i+1})&=(n+1)\sum_{i=1}^{k-1}(a_i-a_{i-1})-\sum_{i=1}^{k-1}a_{i+1}(a_i-a_{i-1})\\ &=(n+1)(a_{k-1}+1)-\sum_{i=1}^{k-1}a_{i+1}(a_i-a_{i-1})\;. \end{align*}$$