You are to group numbers from $1$ to $N$. You can only group adjacent numbers (difference of $1$), and you are also given with a set of pairs of numbers that conflict and should not be present in a group. Also a group can contain a single integer as such. You can also take consecutive strings of arbitrary length.
For ex: If $(1,3)$ and $(2, 4)$ are two such pairs, and $N$ is $4$, then the possible groups are $(1), (2), (3), (4), (1,2), (2,3), (3,4)$.
Note that $(1,3)$ cannot be combined not only because of the constraint, but they have a difference of greater than $1$. Similarly $(2,4)$.
I tried for a few hours and found a pattern that goes like this:
Let's say the number of ways $1$ can be grouped, is $1$ because the only way is to have a single integer in the group.
For $2$, it does not have a conflict with $1$, so we can say, $2$ ways.
For $3$, it has a conflict with $1$, and since it has a difference greater than $1$ from $1$, the number of ways is the same as that for $(2). i.e. 2$ ways.
For $4$, we have a conflict with $2$, so the number of ways is the same as for $(3). i.e. 2$ ways.
(If the adjacent numbers have a conflict, then we decrease the number of ways by $1$.)
As a whole, it gives $1+2+2+2 = 7$ ways.
The above method works but how can we represent the number of ways in a mathematical way? (Possibly with a proof)