I am trying to solve the next problem:
Find all the possible combinations of roads that do not cross each other given a number of towns.
First I started permuting all combinations with low numbers to figure it.
The possibilities was:
- 6 towns: 5 possible combinations
- 8 towns: 14 possible combinations
- 10 towns: 42 possible combinations
- 12 towns: 132 possible combinations
Bingo! (Catalan numbers). All possible combinations are Catalan of n (towns/2).
The next step is to take into consideration that there are some forbidden paths. Lets take the permutations of 8 towns grouped by first pairs:
[0-1,2-3,4-5,6-7]
[0-1,2-3,4-7,5-6]
[0-1,2-5,3-4,6-7]
[0-1,2-7,3-4,5-6]
[0-1,2-7,3-6,4-5]
[0-3,1-2,4-5,6-7]
[0-3,1-2,4-7,5-6]
[0-5,1-2,3-4,6-7]
[0-5,1-4,2-3,6-7]
[0-7,1-2,3-4,5-6]
[0-7,1-2,3-6,4-5]
[0-7,1-4,2-3,5-6]
[0-7,1-6,2-3,4-5]
[0-7,1-6,2-5,3-4]
This first group has Catalan(n - 1) elements, the second has Catalan(n - 2) and so on. Group 3 is equal to group 2 and group 4 is equal to group 1. This kind of symmetry is present with all number of towns.
If the path 0-1 is forbidden you must substract 5 (paths containing 0-1 are invalid so we remove it) to 14 to get the right answer.
I have found that if 4-5 is forbidden, the distance between 4 and 5 is 1 and is equal to the distance of 0-1, so 4-5 is present 5 times in the permutatios as 0-1 is. If 1-4 is forbidden, the distance is 3 that equals to 0-3 and you must substract 2 to your total count.
My problem is when paths 0-1 and 4-5 are forbidden at the same time. I know that I have to substract 5 from total because of 0-1 paths but then cant do de same with 4-5 because 2 of 4-5 cases are already removed thanks to the 0-1 cases.
I was trying to find a way to determine the number of cases where 0-1 and 4-5 are present ... and I'm out of ideas
Thanks