Cuál es el número máximo de regiones producidas, es decir $f(n)$ uniendo todos los vértices con segmentos de línea de un polígono convexo con $n$ ¿Lados?

Question

Cuál es el número máximo de regiones producidas, es decir $f(n)$ uniendo todos los vértices con segmentos de línea de un polígono convexo con $n$ ¿Lados?

Por ejemplo, para el hexágono de la izquierda, el número de regiones es 24, pero el de la derecha es 25, lo que Creo que es de hecho $f(n)$ para el caso $n=6$ .

Entonces, ¿hay alguna manera de encontrar la ecuación general para $f(n)$ ?

Gracias, señor.

Answer 1

Debería ser bastante obvio para usted (como se ve en sus dos diagramas) que el número máximo de regiones interiores se generan cuando no hay tres o más diagonales tienen un punto de intersección común. La prueba es bastante sencilla. Ahora, vamos a considerar el número de regiones que se crean cuando no hay tres o más diagonales tienen un punto de intersección común. Lo demostraremos añadiendo recursivamente un nodo más:

Sea el número máximo de regiones interiores de un polígono convexo que tenga $n$ lados ser $f(n)$ . Para el caso base, considere $f(4) = 4$ que es trivial.

Añadamos un vértice más $P_{n+1}$ a un $n$ -para convertirlo en un polígono. $n+1$ polígono de lados. Tendrá $n-2$ nuevas diagonales que se originen a partir de ella. Los vértices del polígono original más cercanos al nuevo vértice se denominarán $P_1$ y $P_n$ . Entonces, el lado $P_1P_n$ es también una nueva diagonal en el nuevo polígono. Observamos que una vez que cualquiera de las nuevas diagonales con origen en el vértice $P_{n+1}$ entra en el polígono más pequeño, cuando se mueve desde su intersección con cualquier diagonal del nuevo polígono (incluyendo $P_1P_n$ ) a cualquier otro vértice diagonal o de terminación, divide la región en dos partes, creando así una región extra. Esto se traduce en que el número de regiones adicionales creadas en el polígono antiguo, es igual al número de veces que cualquier diagonal de nueva creación originada a partir de $P_{n+1}$ se cruza con otra diagonal (incluyendo $P_1P_n$ ). El número de formas diferentes en que esto puede ocurrir se puede encontrar fijando el punto final de la diagonal que se origina en $P_{n+1}$ y los posibles puntos finales de la otra diagonal. Los tres puntos estarán entre los vértices del polígono original, es decir, entre $P_1 ... P_n$ . Por lo tanto, tenemos que elegir 3 enteros de entre $1 ... n$ que es $n\choose3$ .

Obsérvese también que la recién creada $\triangle$$ P_1P_nP_{n+1} $ will be divided into $ n-1 $ regions by the $ n-2 $ new diagonals originating from $ P_{n+1} $. Thus, the total increase in regions is $ n\elegir3 $$+ (n-1)$ dando la relación de recurrencia:

$f(n+1) = f(n) + {n\choose3} + (n-1)$

Resolviendo esta relación de recurrencia se obtiene la siguiente expresión de forma cerrada:

$f(n) = \frac{1}{24}n(n-3)[n(n-3) + 14] + 1$

Se puede encontrar otra solución que da un resultado idéntico (pero expresado de forma diferente) aquí .

Answer 2

Sea $v$ el número de vértices, $e$ el número de aristas y $f$ el número de caras (sin contar el exterior de la dada $n$ -gon $P$ ) en la configuración resultante. Entonces, por la fórmula de Euler $$v+f = e+1\ .$$ Por otra parte, el número de vértices viene dado por $$v=n+{n\choose 4}\ ,$$ porque cuatro vértices cualesquiera de $P$ determinan un único vértice en el interior de $P$ . Por último, el número de aristas satisface $$2e=n(n-1)+4{n\choose 4}\ ,$$ porque cada vértice de $P$ tiene grado $n-1$ y cada vértice interior tiene grado $4$ .

Resolviendo estas tres ecuaciones para $f$ obtenemos $$f={n(n-1)\over2}+2{n\choose 4}-n-{n\choose 4}+1={1\over24}(n^4-6n^3+23n^2-42n+24)\ .$$

Answer 3

Probablemente

A006522 Análogo en 4 dimensiones de los números poligonales centrados. También número de regiones creadas por lados y diagonales de n-gon. (Anteriormente M3413) 12

1, 0, 0, 1, 4, 11, 25, 50, 91, 154, ...

Ver sus referencias, notas y fórmulas, por ejemplo es la suma de varios binomios.

FÓRMULA a(n)=binomio(n, 4)+binomio(n-1, 2)+binomio(n,2)+binomio(n,3)+binomio(n,4), n>=-1.

Buena herramienta, la Enciclopedia en línea de secuencias de números enteros.

Answer 4

La expresión más conveniente para f(n) es f(n) = n(n-1)(n-2)(n-3)/24 + (n-1)(n-2)/2 que, por supuesto, es f(n) para cualquier polígono irregular de n lados (o cualquier polígono regular de "lados Impares"}. Para los polígonos regulares de lados pares es necesario reducir el valor dado por f(n) contando el número de 6,8,10,12 ... nodos producidos por las diagonales que se cruzan. Por cada 6 nodos el número de regiones se reduce en uno, por cada 8 en 3, cada 10 en 6, cada 12 en 10 y así sucesivamente en una secuencia numérica triangular. Por ejemplo, en un polígono regular de 18 lados hay 216 nodos de 6, 54 nodos de 8, 54 nodos de 10 y un nodo central de 18 ("oculta" 28 regiones). El valor f(n) de 3196 se reduce en 730 para obtener el valor "observado" de 2466.