Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Solution 1:

We can count the number of partitions described above by first dividing the $n$-gon into non-intersecting $k$-gons, then creating the $k$-paths within the $k$-gons.

The number of decompositions of an $n$-gon into $\frac{n}{k}$ non-intersecting partitions of size $k$ is $$Q'(n,k) = \frac{(n)_{\frac{n}{k}-1}}{\left(\frac{n}{k}\right)!}$$ Where $(n)_j$ is the falling factorial. This is a specific case of a result of Kreweras (in translation).

Now, within each $k$-gon, we can start at any of $k$-vertices (k choices) and create a non-intersecting path by proceeding clockwise or counter-clockwise to the nearest vertex in the $k$-gon (2 choices) with the last vertex forced. This will count each path twice, as a valid path can begin from either of its two ends. This yields

$$\frac{k2^{k-2}}{2} = k2^{k-3}$$

Ways to create a valid path inside the $k$-gon (see @fabian's answer for the original explanation).

Then for each $n$-gon, we have $\frac{n}{k}$ distinct $k$-gons with which to make the paths, giving

$$(k2^{k-3})^{\frac{n}{k}}$$

valid path configurations for each $k$-gon configuration. Combining the two results gives

$$Q(n,k) = (k2^{k-3})^{\frac{n}{k}} \times Q'(n,k) = (k2^{k-3})^{\frac{n}{k}}\frac{(n)_{\frac{n}{k}-1}}{\left(\frac{n}{k}\right)!}$$

Solution 2:

You can do the calculation on the recursive formula for that problem.

You can observe the following:

we don't need to restrict ourselfs to regular polygons, the numbers remain the same, if strictly convex polygons are used.
there are $k \cdot 2^{k-3}$ ways to combine $k$ nodes to paths such that no line on the path crosses another line of the path (choose the starting point ($k$ possibilities), then you can choose $k-2$ times, if the next node is the next node not already on the path clockwise or counterclockwise from the start node; That makes $k \cdot 2^{k-2}$ paths, but every path was counted exactly twice)

Example with 6 nodes:

All those paths start at the rightmost node. We start with all choosing all nodes to be the next node counterclockwise from the start node (0000), then "count up" to choosing all nodes to be the next node counter-clockwise from the start node (1111); (0001 means choosing the first node to be the next node counter-clockwise from the start node and all the rest to be the next node clockwise from the start node)

Note that all those paths are different, but if we use all nodes as starting nodes, then the path using the end node as start node and the start node as end node and connecting the same nodes cannot be distinguished in the end, since paths are not directed. E.g. the first path would be the same as the last path with start and end point exchanged.
The number of nodes that can be "skipped" between nodes on one path can only be a multiple of $k$
Graphs can be recursively constructed like this: choose $k$ nodes, such that there are only multipes of $k$ between 2 neighboring nodes, if enumerated clockwise (whole polygon). Choose any way to connect those nodes to a path $p$ such that the lines don't intersect. For each of the $k$ (possibly empty) sets of nodes between nodes on $p$ if enumerated clockwise(whole polygon) recursively construct the paths.
The recursive definition of $Q$ is:

$Q(n, k) = k \cdot 2^{k-3} \cdot\sum\limits_{\substack{p_1, p_2, ..., p_{k-1} \in \mathbb{N}\\p_1 + p_2 + ... + p_{k-1} \leq n/k-1}} Q(k \cdot(n/k-1-\sum\limits_{j=1}^{k-1} p_i), k) \cdot \prod\limits_{i=1}^{k-1} Q(p_i \cdot k, k)$

$Q(0, k) = 1$

This is a dynamic programming approach to calculate $Q(n, k)$ (called like this: new PolygonLinesCombinations(k).getResult(n))

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;

public class PolygonLinesCombinations {

    public static void main(String[] args) {
        System.out.println(new PolygonLinesCombinations(Integer.parseInt(args[1]))
                .getResult(Integer.parseInt(args[0])));
    }

    public PolygonLinesCombinations(int k) {
        if (k < 2) {
            throw new IllegalArgumentException("k >= 2 expected, but found " + k);
        }
        this.k = k;
        this.results = new ArrayList<>();
        this.kDec = k - 1;
        this.factor = planarLineNumber(k);
        this.partition = new int[kDec];

        // exactly 1 way to connect 0 nodes
        this.results.add(BigInteger.ONE);

        // exactly 1 way to choose the rest
        this.results.add(this.factor);
    }

    private final int k;
    private final BigInteger factor;
    private final int kDec;
    private final ArrayList<BigInteger> results;
    private final int[] partition;

    public BigInteger getResult(int n) {
        if ((n % this.k) != 0) {
            throw new IllegalArgumentException("n is not divisible by k; n=" + n + ";k=" + k);
        }

        // calculate all missing results with increasing n
        int m = n / k;
        for (int i = results.size(); i <= m; i++) {
            results.add(calculateResult(i));
        }
        return results.get(m);
    }

    private BigInteger calculateResult(int m) {
        // nodes remaining, after this set is chosen
        int remainingPartitions = m - 1;
        Arrays.fill(partition, 0);

        BigInteger possibilities = BigInteger.ZERO;

        int sum = 0;
        do {
            // number of possiblities for this partition
            // = product of the number of possibilities for each remaining part
            BigInteger possibilitiesForPartition = this.factor;
            for (int i = 0; i < kDec; i++) {
                possibilitiesForPartition = possibilitiesForPartition.multiply(results.get(partition[i]));
            }
            possibilities = possibilities.add(
                    possibilitiesForPartition.multiply(results.get(remainingPartitions - sum)));

            // generate next ordered partition
            for (int i = 0; i < kDec; i++) {
                partition[i]++;
                sum++;
                if (sum > remainingPartitions) {
                    // reset to 0, if a partition gets too large
                    sum -= partition[i];
                    partition[i] = 0;
                } else {
                    break;
                }
            }
        } while (sum > 0); // stop, if all-zeroes partition is reached again

        return possibilities;
    }

    // returns n * 2^(n-3)
    private static BigInteger planarLineNumber(int k) {
        return BigInteger.valueOf(k).shiftLeft(k - 3);
    }

}

Solution 3:

Put $T_n = Q(n, 2)$ and taking $T_0 = 0$ by convention. Then the $T_n$ are odd when $n$ is odd and the values for even $n$ satisfy the following recursion equations:

$$ \begin{align*} T_0 &= 1 \\ T_2 &= 1 \\ T_n &= \sum_{i=1}^{n/2}T_{2(i-1)} \cdot T_{2(n/2-i)} \end{align*} $$

To see this, enumerate the vertices of the $n$-gon as $v_0, \ldots, v_{n-1}$, A solution with a connected pair $(v_i, v_j)$ with $i < j$ has to have $j -i$ odd and for $i < s < j$, $v_t$ must be connected to some $v_t$ where $i < t < j$. Thus we can connect $v_0$ to $v_1$ or $v_3$ or $v_5$ and so on. When we connect $v_0$ to $v_{2i+1}$ we get two instances of the same problem with $n$ replaced by $n'$ say, one with $n' = 2(i-1)$ and one with $n'=2(n/2-i)$. This gives:

$$T_4 = 2, T_6 = 5, T_8 = 14, T_{10} = 42$$

And (once you do the sums right $\ddot{\frown}$), these turn out as pointed out by CuddyCuttlefish to be the Catalan numbers:http://oeis.org/A000108.

Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Solution 1:

Solution 2:

Example with 6 nodes:

Solution 3:

Related

Recent Posts