Recurrencia para el número de regiones formadas por diagonales de un polígono convexo.

Question

He tenido problemas con este problema en particular, ha de pensar para que durante una hora o dos, pero no he conseguido una explicación a la siguiente pregunta.

Supongamos $a_n$ el número de regiones en las que una región poligonal convexa con $n+2$ lados se divide por sus diagonales, suponiendo que no hay tres diagonales tienen un punto en común. Definir $a_0 = 0$. Mostrar que

$$a_n = a_{n-1} + {n+1 \choose 3} + n \quad (n \geq 1)$$

Hasta el momento, tengo que para $n \geq 1$, nos fijamos en un $(n+2)$-gon. Escoge un borde de uno de los $n+2$ bordes de la $(n+2)$-gon. A continuación, lindan con un triángulo, de modo que podemos tener una $(n+3)$-gon. Dado el triángulo que nos tocan a la $(n+2)$-gon, echemos un vistazo a lo expuesto vértice de ese triángulo. Podemos crear $n$ de las diagonales, ya que no podemos crear una diagonal uniendo la parte expuesta de vértice a vértice adyacente. Ahora, tenemos que $n$ diagonales ejecutar a través del borde creado por la intersección de la $(n+2)$-gon y el triángulo. Esto nos da $n+1$ regiones en el triángulo. Pero ahora, me parece que no puede encontrar un patrón de por qué el $(n+2)$-gon ha ${n+1 \choose 3}$ extra regiones, como resultado de los $n$ diagonales que atraviesan a través de la $(n+2)$-gon. Cualquier consejo o sugerencia se agradece.

Answer 1

Así, desde su recurrencia se define a $a_n$ en términos de $a_{n-1}$, creo que sería más apropiado considerar las regiones adicionales creado al agregar el $(n+2)$nd vértice a de un $(n+1)$-gon en lugar de la $(n+3)$rd vértice a de un $(n+2)$-gon.

Así, supongamos que tenemos una $(n+2)$-gon. Designar a la "expuestos vértice" $X$, y llamar a los otros vértices $P_1$, $P_2$, ..., $P_{n+1}$, donde $P_1$ $P_{n+1}$ son adyacentes a $X$. El $P_i$s forma un $(n+1)$-gon dentro de las cuales no se $a_{n-1}$ regiones hecho de que todas las diagonales y los lados $P_iP_j$. Ahora, considere el $n-1$ diagonales que emanan de $X$ y terminando en $P_k$ donde $2 \leq k \leq n$. Como podemos extraer de estos, siempre que una diagonal golpea una dibujado previamente en diagonal, entra en una región diferente, que será cortado en dos regiones cuando la diagonal golpea la línea siguiente. Es decir, para cada intersección entre una nueva diagonal $XP_k$ y un viejo diagonal $P_iP_j$, podemos hacer una nueva región en el interior del polígono $P_1\ldots P_{n+1}$. Cuántas de estas intersecciones hay? Es sólo el número de formas de seleccionar tres enteros $1 \leq i < k < j \leq n+1$, $\binom{n+1}3$.

Y luego, por supuesto, tenemos la $n$ nuevas regiones en el interior del triángulo $XP_1P_{n+1}$.

Answer 2

Creo que estás un poco mezclado de los índices. Usted se pasó de una $(n+2)$-gon a un $(n+3)$-gon, mientras que la recurrencia que va de $a_{n-1}$ $a_n$va desde una $(n+1)$-gon a un $(n+2)$-gon. Así que vamos a empezar de la misma manera que comenzó, pero la adición de un triángulo a una $(n+1)$-gon para crear un $(n+2)$-gon. A continuación, como se mostró, el triángulo contiene $n$ nuevas regiones.

Para cada intersección en una diagonal que involucran el nuevo punto le corresponde un nuevo borde interno que aumenta el número de regiones por $1$, es decir, el borde a partir de esa intersección y terminando en la siguiente intersección de la diagonal o el extremo de la diagonal. Ahora considere todos los triángulos formados por tres de las $n+1$ puntos de la $(n+1)$-gon; hay $\binom{n+1}3$ de estos. Hay tres maneras en las que podemos conectar el nuevo punto a uno de los tres puntos del triángulo y conectar los otros dos puntos a cada uno de los otros. De estos tres, uno conduce a una intersección y dos no. También, todos los pares de las diagonales en el que una de las diagonales contiene el nuevo punto aparece exactamente una vez en este conteo. Por tanto, el número de intersecciones, y por lo tanto de las nuevas regiones, se $\binom{n+1}3$.