# Number of ways to connect sets of $k$ vertices in a perfect $n$ -gon [closed]

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)$:

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.

$$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)$?