Enumerar ciertas configuraciones especiales - combinatoria.

Question

Consideremos los vértices de un n-gono regular, numerados del 1 al n. (Sólo los vértices, no los lados). Una "configuración" significa que algunos de estos vértices están unidos por aristas.

Una "buena" configuración es aquella que tiene las siguientes propiedades:

1) Hay al menos una arista.

2) Puede haber múltiples aristas a partir de un solo vértice.

3) Si A y B están unidos por una arista, entonces el grado de A es igual al grado de B.

4) No debe haber dos aristas que se crucen entre sí, excepto posiblemente en los puntos finales.

5) El grado de cada vértice es como máximo k. (donde $0\leq k \leq n$ )

Encuentra f(n, k), el número de configuraciones buenas. Por ejemplo, f(3, 2) = 4 y f(n, 0) = 0.

Answer 1

De los diversos comentarios que tenemos

• $f(n,0) = 0$ ya que podemos no tener aristas, pero necesitamos al menos una
• $f(n,1)=M_n-1$ donde $M_n$ son los Números de Motzkin el número de formas diferentes de dibujar cuerdas no intersecantes en un círculo entre $n$ puntos, y $-1$ porque necesitamos al menos una arista
• $f(n,2)=C_n-1$ donde $C_n$ son los Números catalanes el número de particiones no cruzadas en un círculo entre $n$ puntos, y $-1$ porque necesitamos al menos una arista
• $f(n,k)=f(n,2)$ para $k\gt 2$ ya que no podemos tener grados mayores que $2$ en un polígono convexo sin intersecciones

Hay muchas relaciones de recurrencia. Dos bonitas son $$M_{n+1}=M_n+\sum_{i=0}^{n-1}M_i M_{n-i-1}$$ y $$C_{n+1}=\sum_{i=0}^{n}C_i\,C_{n-i}$$ a partir de $M_0=1$ y $C_0=1$ .

Los números catalanes pueden escribirse de forma cerrada como $C_n = \frac{1}{n+1}{2n\choose n}$ pero no existe una forma igualmente sencilla para los números de Motzkin.

Answer 2

Podemos demostrar que los grados de los vértices $k \le 2$ . Supongamos por contradicción que $n$ es el tamaño de un contraejemplo mínimo, un convexo $n$ -gon con algún grado $k \gt 2$ . Por minimidad (descartando los vértices no conectados al dado) todos los vértices del $n$ -gon tienen grado $k$ .

Pero se sabe que el máximo número de diagonales no intersectadas de un $n$ -gon es $n-3$ . Si añadimos las aristas exteriores del propio polígono, tendríamos como máximo $2n-3$ aristas no intersectadas.

Pero para $n$ vértices para que cada uno tenga un grado $k$ nécessite $\frac{nk}{2}$ bordes. Ahora un argumento elemental de desigualdad:

$$ \frac{nk}{2} \le 2n-3 $$

$$ k \le 4 - \frac{6}{n} $$

inmediatamente nos da que $k \le 3$ .

Para descartar $k = 3$ hace un uso esencial de la convexidad del polígono, en el sentido de que un cuadrilátero no convexo permite aristas no intersectadas con tres que se encuentran en cada vértice. Sin embargo, en un polígono convexo, una vez añadido el número máximo de diagonales no intersecantes, el resultado es una disección del polígono en triángulos. Al menos dos de estos triángulos están formados por dos aristas "externas" y una diagonal, de modo que el vértice correspondiente opuesto a la arista diagonal sólo tiene grado $2$ .

---

Añadido: Vamos a dar cuerpo a la reducción de $f(n,k)$ a menos vértices por consideración de los casos: vértice $1$ no tiene (a) ninguna arista, (b) una arista, o (c) dos aristas (si $k=2$ permite).

Si el vértice $1$ no tiene ninguna arista, obtenemos una contribución de $f(n-1,k)$ de las "buenas configuraciones" del resto de $n-1$ vértices.

Si el vértice $1$ tiene una sola arista, su otro vértice terminal $p$ también debe tener sólo ese borde. Esto induce una contribución que suma las "buenas configuraciones" de los dos conjuntos de vértices a ambos lados del vértice $p$ incluyendo los posibles vacíos allí, ya que hemos cumplido el requisito de al menos una arista:

$$ \sum_{p=2}^{n} (1 + f(p-2,k)) (1 + f(n-p,k)) $$

Si el vértice $1$ tiene dos aristas (como se ha señalado, sólo es posible si $k=2$ ), las contribuciones son similares pero necesitan más contabilidad. Vértice $1$ pertenece a un ciclo de $r \gt 2$ bordes, y el resto $n-r$ Los vértices se dividen así en subconjuntos consecutivos variables, cada uno de los cuales tiene su propia "configuración buena" (o una vacía).