# Constrained combinatorics

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)

• Not sure this is clear. There are $N$ single element groups and $N-1$ consecutive pairs, yes? If you exclude some of these then there are fewer. What's the question?
– lulu
May 20, 2018 at 12:18
• I guess I am not sure what you mean by "you are to group". Suppose $N=5$ and that there are no extra exclusions. Is the answer $5+(5-1)=9$ or is it something else?
– lulu
May 20, 2018 at 12:20
• Some of the other possible pairs are $(1,2,3,4)$ which is not valid because $(1,3)$ or $(2,4)$ shouldn't be in the same group, and $(2,3,4)$ is invalid because $(2,4)$ for the same reason. May 20, 2018 at 12:21
• As I say, this is not clear at all. Do you agree with my formula (with no extra restrictions)? I get $2N-1$. Sure gives $7$ in the case $N=4$.
– lulu
May 20, 2018 at 12:26
• @lulu, $N = 5$ and there are no exclusions, then there would be $1 + 2 + 3 + 4 + 5 = 15$ groups. May 20, 2018 at 12:26