0

I have to pair numbers in a circle without crossing chords.

This:

Image example

The way to solve this is Catalan Numbers where n = nodes/2

The problem comes with some restrictions. I have to calculate the number of possible combinations without some chords. In the next example there are 8 nodes, so the possible combinations are 14. But with these restrictions the solution is 7:

Example with 8 nodes and restrictions

  • 5 with 0
  • 6 with 1
  • 3 with 6
  • 2 with 7

How can I calculate the number of results without combining the restrictions?

dvil
  • 1
  • Are these arbitrary restrictions, or can you state precisely what they are? – Kevin Long Apr 29 '18 at 17:28
  • I don't understand the restrictions. Does "$5$ with $0$" mean that $5$ must be paired with $0$ or that it must not be so paired? Also, what do you mean by "without combining restrictions"? – saulspatz Apr 29 '18 at 17:29
  • @KevinLong Those restriction are given within the problem, it says 8 nodes and those 4 restrictions. – dvil Apr 29 '18 at 17:30
  • @saulspatz 5 with 0 says that you can't pair 5 with 0 in all the possible combinations. Without combining is that I can combine all the restrictions together, for example "3 with 6" and "2 with 7" appear twice on their own and 1 time in the same possibility. – dvil Apr 29 '18 at 17:31
  • "Without combining" means you can combine them? I give up. – saulspatz Apr 29 '18 at 17:38
  • Okay, I understand that part, but I'm still a little confused. Your second image shows the number of possibilities when you impose all four of the restrictions listed in the bullet points. Are you asking how to calculate the number of results if you impose only a single one of those four restrictions? If so, it's obvious that three of those restrictions are identical, so they'll all be counted the same. – Kevin Long Apr 29 '18 at 17:40
  • I will try to explain it better... How can I know the number of times the restrictions appear in the combinations? If there is a total of 14 combinations, how can I know that (5,0), (6,1), (3,6) and (2,7) appear 7 times in those 14 combinations – dvil Apr 29 '18 at 17:43
  • Well, if there are $14$ combinations without those restrictions and $7$ with those restrictions, the difference of $7$ is the number of combinations that break those restrictions. But are you asking about the "bad" combinations, or how many times each individual restricted pair appears? Most of them will cross each other, so most of the bad ones will contain only of those restricted pairs. However, $(2,7)$ and $(3,6)$ can both appear in the same combination, and that combination is the unique one with more than one restricted pair. You can always just all combinations to check. – Kevin Long Apr 29 '18 at 17:51
  • @KevinLong thanks for your help. I've been researching non-stop since yesterday and I've found some things... For example I've developed a formula to detect the number of possibilities to remove given a forbidden path: C( n - (k + 1) ) * C( k - 1) being k the distance (for example in 1-6 it would be 6, number of nodes inside). It kinda works but I've found a case where it didn't: in n=4 (0-7)(4-5). I'm totally overwhelmed with this. FYI: it's like this problem but with restrictions. What I would like to know known the sum of bad paths – dvil Apr 30 '18 at 18:17

0 Answers0