Número de maneras de conectar conjuntos de $k$ puntos en un perfecto $n$-gon

Question

Deje $Q(n,k)$ el número de maneras en las cuales podemos conectar conjuntos de $k$ vértices en una perfecta $n$-gon tal que no hay dos líneas se cruzan en el interior de la $n$-gon y sin vértices permanece aislado.

Intersección de las líneas de fuera de la $n$-gon es aceptable. Obviamente, $k|n$, e $n$ puede no ser la mejor, porque de lo contrario no habrá puntos desconectado. El $n$-gon en sí es una solución aceptable para una conexión de $n$ vértices, y en el caso de $k>2$, estos no son líneas, sino un conjunto de líneas conectadas, una especie de una red formada por conectadas grafos planares con bordes rectos con $k$ vértices, que son necesarios para ser los vértices de la $n$-gon sí mismo.

Siempre hay que ser $S =\frac nk$ conjuntos de líneas. Para $k=2$, hay exactamente $\frac nk$ líneas, y para $k>2$, hay exactamente $\frac nk$, no líneas, pero los conjuntos de tales conectado grafos planares.

Tomemos, por ejemplo,$Q(6,2)$. Tenemos un hexágono perfecto. Por fuerza bruta con lápiz y papel, me encontré con que hay 5 maneras de conectar conjuntos de 2 vértices (puntos) de tal manera que no hay dos líneas se cruzan en el interior del hexágono. Por lo tanto, $Q(6,2) = 5$.

La siguiente imagen muestra el caso de $Q(6,2)$:

Estoy seguro de que una elegante solución para $k=2$, pero no puedo averiguar. Para la generalidad yo pregunte acerca de cualquier cantidad de $k$ puntos.

También es extremadamente importante tener en cuenta que no estamos dividiendo el $n$-gon en $k$-ágonos, pero la conexión de caminos entre el $k$ nodos o vértices o puntos.

Ahora vamos a dar un paso más allá:

Deje $U(n,k)$ el número de las únicas maneras de conectar conjuntos de $k$ puntos en un perfecto $n$-gon, de tal manera que no hay dos líneas se cruzan, y la simetría rotacional se descuida, yo.e, cada contrato es único y no puede ser formado por la rotación o volteado otra disposición en cualquier forma. $U(6,2)=2$. Tenga en cuenta que $U(6,2)=2$ debido a que el régimen de la primera línea en la imagen no son únicos, y puede estar formado por la rotación de uno a otro. Lo mismo sucede para la segunda línea de los acuerdos. Esto se traduce en sólo 1 de acuerdo único para cada línea. Por lo tanto $U(6,2)=2$.

Estoy bastante desorientado acerca de ambas funciones $U$$Q$, y no podía derivar un algoritmo o fórmula para cualquiera de ellos. Por lo tanto voy a postear esto aquí.

Estoy bastante seguro de que hay un pura combinatoria aproximación a este problema, tal vez en relación con Polya la Enumeración Teorema (PET). Hay una solución elegante para estas funciones? Puede incluso ser resuelto por $k>2$?

Cualquier luz en ninguna de las funciones que va a ser muy apreciable, ya que no he tenido éxito en la obtención de una fórmula para cualquiera de ellos.

EDITAR - Temporal de las Soluciones de + preguntas Pertinentes Y progreso

$$Q(n,2) = C_{n \over 2}\quad\text{where}\quad C_n = \frac{1}{n+1} {2n\choose n}$$ Y $C_n$ indica el $n$'th catalán número.

Ahora vamos a denotar $W(n) = U(n,2)$. Se puede encontrar una fórmula para $W(n)$? Tal vez una conexión entre el$Q(n,2)$$W(n)$?

Otra EDICIÓN: (2)

$$Q(k,k) = k\cdot 2^{k-3}$$

EDICIÓN 3

Parece que, en general, $Q(n,3)$ está aquí: https://oeis.org/search?q=3%2C27%2C324&sort=&language=english&go=Search

Tal vez la generalización de los poderes superiores resultará en la general $Q(n,k)$ función..

EDICIÓN 4

Aquí hay una pequeña tabla de valores de la $Q(n,k)$, lo que parece ser la correcta, proporcionada por fabian's algoritmo: (La tabla se encuentra en el formulario de $Q(x\cdot k,k)$)

$$ \begin{array}{c|rrrrr} {_k\,\backslash\, ^n} & k & 2k & 3k & 4k & 5k \\ \hline 2 & 1 & 2 & 5 & 14 & 42\\ 3 & 3 & 27 & 324 & 4455 & 66339\\ 4 & 8 & 256 & 11264 & 573440 & 31752192\\ 5 & 20 & 2000 & 280000 & 45600000 & 8096000000\\ 6 & 48 & 13824 & 5640192 & 2686058496 & 1396580548608\\ \end{array} $$

EDICIÓN DE 5 $Q(n,k)$ RESUELTO

Como bellamente encontrado y explicado por @CuddlyCuttlefish en su respuesta, la fórmula para $Q(n,k)$ es de la siguiente manera: $$Q(n,k) = \frac{(n)_{\frac{n}{k}-1}}{\left(\frac{n}{k}\right)!}\cdot (k\cdot 2^{k-3})^{\frac{n}{k}} \quad\text{where}\quad (n)_j = n(n-1)...(n-(j-1))$$

Y $(n)_j$ es la caída de factorial, que se define como el anterior.

Ahora se mueve a $U(n,k)$

Ahora sólo queda encontrar una fórmula o algoritmo para $U(n,k)$. Personalmente creo que tiene que ver con Polya la Enumeración Teorema y Burnside del lexema, combinado con el ciclo del índice del grupo simétrico, $Z(S_n)$. He tocado algo en relación a eso, y por lo tanto creo que es relativa. No estoy 100% seguro, pero mis instintos me dicen que es relativa.

EDICIÓN 6

Para que quede claro, yo estoy por la presente adición de una imagen para describir el caso de $U(6,3)$ y que para aclarar mejor lo $U(n,k)$ medios.

$U(6,3)=4$, como se muestra en la imagen de arriba (@Marko Riedel ha señalado una disposición adicional que había perdido). Hay cuatro únicos arreglos para conectar conjuntos de 3 vértices tales que ningún vértice permanece aislado, no hay líneas se cruzan en el interior del hexágono, y cada arreglo es único y no puede ser formado por la rotación o volteado de cualquier otra disposición.

Hay dos único camino-tipos, uno que es introducido por la conexión de 3 vértices adyacentes ($p_1$), y otro que conecta 2 vértices con un poco de "saltar", y el tercer vértice es entonces adyacentes ($p_2$).

Esperamos que hace las cosas un poco más claras.

EDICIÓN 7

Como siempre por @Marko Riedel del algoritmo, $U(n,3)$ secuencia comienza de la siguiente manera:

$$1, 4, 22, 201, 2244, 29096, 404064, 5915838,\ldots$$

El cálculo era muy áspera, y el cálculo de los tiempos largos. Que tan eficiente como se obtiene, a partir de ahora. Producir más valores sólo consume demasiada memoria, tiempo o ambos. Se refieren a Marko Riedel de respuestas para obtener más secuencias y más explicaciones. También si alguien puede comprobar lo anterior sería genial.

Answer 1

Podemos contar el número de particiones descrito anteriormente por la primera división de la $n$-gon en la no-intersección $k$-ágonos, luego la creación de la $k$-caminos dentro de la $k$-ágonos.

El número de descomposiciones de un $n$-gon en $\frac{n}{k}$ no de intersección de las particiones de tamaño $k$ es $$Q'(n,k) = \frac{(n)_{\frac{n}{k}-1}}{\left(\frac{n}{k}\right)!}$$ Donde $(n)_j$ es la caída de factorial. Este es un caso especial de un resultado de Kreweras (en la traducción).

Ahora bien, dentro de cada una de las $k$-gon, se puede comenzar en cualquiera de $k$-vértices (k opciones) y crear un no-intersección ruta por el procedimiento de las agujas del reloj o en el sentido antihorario hasta el vértice más cercano en el $k$-gon (2 opciones) con el último vértice forzada. Se tendrá en cuenta en cada ruta dos veces, como una ruta de acceso válida puede comenzar desde cualquiera de sus dos extremos. Este rendimientos

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

Formas de crear una ruta de acceso válida dentro de la $k$-gon (ver @fabian de la respuesta para la explicación original).

A continuación, para cada una de las $n$-gon, tenemos $\frac{n}{k}$ diferentes $k$-ágonos con el que hacer de los caminos, dando

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

ruta de acceso válida configuraciones para cada una de las $k$-gon configuración. La combinación de los dos resultados da

$$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)!}$$

Answer 2

Usted puede hacer el cálculo con la fórmula recursiva para ese problema.

Se puede observar lo siguiente:

• no necesitamos restringir endeudamos frente a los polígonos regulares, los números siguen siendo los mismos, si es estrictamente convexa se utilizan polígonos.

• hay $k \cdot 2^{k-3}$ formas de combinar $k$ nodos recorridos que no hay ninguna línea en el camino se cruza con otra línea de la ruta de acceso (elegir el punto de partida ($k$ posibilidades), entonces usted puede optar $k-2$ de las veces, si el siguiente nodo es el siguiente nodo no ya en el camino de las agujas del reloj o en sentido antihorario desde el nodo de inicio; Que hace que $k \cdot 2^{k-2}$ caminos, pero todos los caminos se contó exactamente dos veces)

  Ejemplo con 6 nodos:

  Todos los caminos comienzan en el nodo derecho. Empezamos con todo la elección de todos los nodos a ser el siguiente nodo a la izquierda desde el nodo de inicio (0000), luego en "cuenta" para seleccionar todos los nodos a ser el siguiente nodo en sentido antihorario desde el nodo de inicio (1111); (0001 significa elegir el primer nodo a ser el siguiente nodo en sentido antihorario desde el nodo de inicio y todo el resto a la siguiente nodo de las agujas del reloj desde el nodo de inicio)

  

  Tenga en cuenta que todos los caminos son diferentes, pero si utilizamos todos los nodos a partir de los nodos, a continuación, la ruta usando el nodo como nodo inicial y el nodo de inicio como de fin de nodo y se conecta el mismo nodos no pueden ser distinguidos en el final, ya que las rutas no están dirigidos. E. g. el primer paso sería la misma que la última ruta con inicio y el punto final intercambiados.

• El número de nodos que puede haber "omitido" entre los nodos en una ruta de acceso sólo puede ser un múltiplo de $k$

• Los gráficos pueden ser de forma recursiva construido como este: elija $k$ nodos, de tal manera que sólo hay multipes de $k$ entre 2 nodos vecinos, si enumerados en sentido horario (todo el polígono). Elija cualquier forma de conectar los nodos a un camino de $p$ de manera tal que las líneas no se cruzan. Para cada una de las $k$ (posiblemente vacía) de los conjuntos de nodos entre los nodos en $p$ si enumerados en sentido horario(todo el polígono) de forma recursiva construir los caminos.

• La definición recursiva de $Q$ es:

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

Este es un enfoque de programación dinámica para calcular el $Q(n, k)$ (se llama de esta forma: 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);
    }

}

Answer 3

Poner $T_n = Q(n, 2)$ y teniendo en $T_0 = 0$ por convenio. A continuación, el $T_n$ son extraños al $n$ es impar y los valores de incluso $n$ satisfacer las siguientes ecuaciones de recursividad:

$$ \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*} $$

Para ver esto, enumerar los vértices de la $n$-gon como $v_0, \ldots, v_{n-1}$, Una solución con la conexión de un par de $(v_i, v_j)$ $i < j$ han $j -i$ impar y para $i < s < j$, $v_t$ debe estar conectado a algunos de los $v_t$ donde $i < t < j$. Por lo tanto, podemos conectar $v_0$ $v_1$o $v_3$ o $v_5$ y así sucesivamente. Cuando nos conectamos $v_0$ $v_{2i+1}$tenemos dos instancias de la misma problema con $n$ reemplazado por $n'$ es decir, un con $n' = 2(i-1)$ y un con $n'=2(n/2-i)$. Esto nos da:

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

Y (después de hacer las sumas derecho $\ddot{\frown}$), estos a su vez como se ha señalado por CuddyCuttlefish a ser el catalán números:http://oeis.org/A000108.

Answer 4

Esto es más de un "largo(ish) comentario" que una respuesta, y estos son en su mayoría de mis instintos hablando. Pero, vengo teniendo referencias!

Aunque no voy a decir que hay una directa relación entre este y el catalán números, yo sospecho que hay una conexión, particularmente los relacionados con la generalizada catalán números que contar las maneras para subdividir regular $n$-ágonos en $(k + 1)$-ágonos (Nota: este no es mi campo, por lo que las variables en la descripción de mi no coinciden con lo que se utiliza en el artículo). Yo no reclamo no es cualquier tipo de bijection, pero me imagino técnicas similares a las que podría ser utilizado para ambos.

Es un problema abierto para contar el número de órbitas de polígono subdivisiones bajo la acción de la diedro grupo, que es lo su $U(n, k)$ me recuerda. He aquí un papel por la Luna y Moser en órbitas de las triangulaciones de $n$-ágonos desde hace varias décadas, y aquí están los dos últimos tesis ([1] y [2]) en órbitas de más general subdivisiones bajo la acción de la diedro grupo.

De nuevo, no estoy diciendo que estos estarán relacionados, pero son las investigaciones de similar naturaleza, que son esencialmente abierta y definitivamente de investigación de nivel. Además, creo que la poligonal disecciones de tener un poco más de la estructura de lo que se está investigando, para mejor o peor.