1
$\begingroup$

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial solutions:

https://math.stackexchange.com/questions/1294224/number-of-ways-to-connect-sets-of-k-dots-in-a-perfect-n-gon

Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices (dots), in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon, and no vertice remains isolated.

Intersection of the lines outisde the $n$-gon is acceptable. Obviously, $k|n$, and $n$ can't be prime because otherwise there will be vertices/dots left unconnected. The $n$-gon itself is an acceptable solution to a connection of $n$ vertices, and in the case of $k>2$, these aren't lines, but a set of connected lines, a sort of a network formed by connected planar graphs with straight edges with $k$ vertices, which are required to be vertices of the $n$-gon itself.

There must always be $S =\frac nk$ sets of lines. For $k=2$, there are exactly $\frac nk$ lines, and for $k>2$, there are exactly $\frac nk$, not lines but sets of such connected planar graphs.

Take for example $Q(6,2)$. We have a perfect hexagon. By brute-forcing with pencil and paper, I found that there are 5 ways to connect sets of 2 vertices (dots) such that no two lines intersect inside the hexagon and no vertice remains unconnected. Hence, $Q(6,2) = 5$.

The following image depicts the case of $Q(6,2)$:

Q(6,2)

For generality I ask about any amount of $k$ dots, even though I've recently found the solution for $k=2$.

Now let's move one step further:

Let $U(n,k)$ be the number of unique ways to connect sets of $k$ dots in a perfect $n$-gon, such that no two lines intersect, and rotational symmetry is neglected, i.e, every possible arrangement is unique and can't be formed by rotating another arrangement in any way. $U(6,2)=2$. Note that $U(6,2)=2$ because the arrangements of the first line in the image are not unique, and can be formed by rotating one another. The same happens for the second line of arrangements. Hence $U(6,2)=2$.

I'm pretty clueless about both functions $U$ and $Q$, and I couldn't derive an algorithm or formula to any of them. Hence I'm posting this here.

I'm pretty sure there's a pure combinatorial approach to this problem, perhaps involving Polya's Enumeration Theorem (PET). Is there an elegant solution to these functions? Can they even be solved for $k>2$?

Any light shed on any of the functions will be very much appreciable, as I haven't been successful in deriving a formula for any of them. Also, both formulas and algorithms will be great!

I can program in Java and Mathematica.

Thanks a lot in advance.

EDIT - Temporary Solutions + Relevant questions AND progress

$$Q(n,2) = C_{n \over 2}\quad\text{where}\quad C_n = \frac{1}{n+1} {2n\choose n}$$ And $C_n$ denotes the $n$'th Catalan number.

Now let us denote $W(n) = U(n,2)$. Can you find a formula for $W(n)$? Perhaps a connection between $Q(n,2)$ and $W(n)$?

$\endgroup$

closed as off-topic by Gilles May 24 '15 at 23:01

  • This question does not appear to be about computer science within the scope defined in the help center.
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ It is generally not recommended to cross-post questions. If your question was not properly answered on math.stackexchange.com because it is a research problem on combinatorics, it is unlikely to be well received here. You should ask for it to be migrated, perhaps to mathoverflow.net. $\endgroup$ – André Souza Lemos May 23 '15 at 20:43
  • $\begingroup$ @AndréSouzaLemos Perhaps you're right about cross-posting questions. Thing is I think a solution does exist, but is just not well known. This is why I'm trying to reach as many people as I can. $\endgroup$ – Matan May 23 '15 at 20:49
  • 1
    $\begingroup$ I'm closing this question as off-topic because it's pure combinatorics (hence mathematics, not computer science) and it has already been posted on Mathematics. $\endgroup$ – Gilles May 24 '15 at 23:01