If ordered pairs eliminate combinatins of ordered numbers, how many combinations are left?

Question

I came across this problem after playing around with some numbers. I am unsure how to approach this problem, or what is involved in solving it. This is an example of many questions. What equation or algorithm do I need to use to solve this type of problem?

The problem:

There are five numbers in the following loop: a,b,c,d, and e. There are a few rules:

1) All combinations that result in the consecutive numbers $(a,b)$ , $(c,a)$ , $(c,b)$ , and $(d,e)$ must be eliminated.

For example, the sequence $a,b,c,d,e$ contains $(a,b)$, and $(d,e)$. However the sequence $a,e,b,c,d$ contains none of the above and cannot not be eliminated.

2) The pairs and sequences are read from left to right. Therefore, the consecutive pair $(a,b)$ is not the same as $(b,a)$.

3) These numbers are in a loop, which means the end of the last number of the sequence happens before the first. For example, $(e,a)$ exists as an ordered pair in the combination $a,b,c,d,e$.

Are there any remaining sequences left after applying these rules?

---

Through trying to make sense of it, I found with the numbers $a,b,c$ and $d$ (Only 24 combinations) only 1/3 of the combinations are eliminated given only one ordered pair. However, having more than two pairs can result in a different amount of sequence elimination. With the $a,b,c$ and $d$ example, 5/6 of all sequences are eliminated with the sets $(a,b)$, $(c,d)$ , and $(a,d)$ compared to 2/3 of all sequences with the sets $(a,b)$, $(c,d)$ , and $(d,c)$. This lead me to further confusion.

---

Edit: This is a Hamilton path problem. When I first saw this, I thought it was a complicated probability problem.

Answer 1

The number of oriented loops is the same as the number of permutations of letters that begin with any one of the letters, So the total number of loops is equal to the number of permutations of the remaining 4 letters $$N_{tot}=4!=24$$

To count the number of legal loops it is best to consider permutations starting with the letter C since C can be followed only by D or E and can be preceded by anything.

This is a good problem for using a tree diagram - something like ...

CD -> CDA -> CDAE -> CDAEB
   -> CDB -> CDBA -> CDBAE
          -> CDBE -> CDBEA
CE -> CEA -> CEAD -> CEADB
   -> CEB -> CEBA -> CEBAD
          -> CEBD -> CEBDA
   -> CED -> CEDA 
          -> CEDB -> CEDBA

In this way you can generate the 7 legal loops.

Answer 2

Yes, consider for instance the sequence $acdbe$.