0

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.

enter image description here

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

Bernard
  • 175,478
Marcos Fernandez Ramos
  • 101
  • This seems very similar to this other recent question. They're not quite the same, but very alike. Anyway, if we're talking about arbitrary restricted paths, it'll be harder, but in the specific case of $(0,1)$ and $(4,5)$, or for any number $k$ of adjacent pairs, once you include those $k$ pairs, the remaining $2n-2k$ vertices will just be have like a $2n-2k$-gon, so the number of such cases is the $n-k$-th Catalan number. For example, Catalan $2$ is $2$, which works in your $n=4, k=2$ case. – Kevin Long Apr 29 '18 at 18:13
  • Yes, sorry, I did not see the other question because it was published by the time I was writing (I took me too long to carefully explain the case). I will try to follow your hints, just need to read them a few times more xD – Marcos Fernandez Ramos Apr 29 '18 at 18:23
  • Oh no, it's not a problem that your questions are similar, since they're not quite asking the same thing. It just seems strange to me that two similar questions would pop up at the same time. – Kevin Long Apr 29 '18 at 18:25
  • @KevinLong I got full of coffee and start thinking in what you said to try not to waste your time, but I dont understand it full yet, sorry:

    In the case I have to remove (0,1),(4,5),(2,3),(6,7) paths

    (0,1) -> remove 5, (4,5) -> remove 3 (2 overloads), (2,3) -> remove 2 (3 overloads), (6,7) -> remove 1 (4 overloads), Total: 11, 3 left from 14

    Followin n − kth Catalan formula I got: 4 - (catalan 4) = -10

    Can you explaint it a bit more? Thanks in advance (edit: I lost line breaks)

     – Marcos Fernandez Ramos Apr 29 '18 at 19:29
  • My comment showed how many combinations will have certain restricted paths present, which you can use to count the number of combinations without those paths. This uses the inclusion-exclusion principle. The idea is you look at the total number of combinations. You take out the number that have at least one bad path. But this double counts, so you add back the number with at least two bad paths. Then you take out the number with at least three, and so on. You can read about it in the link. – Kevin Long Apr 29 '18 at 19:34

0 Answers0