¿Cuántos triángulos hay en la "foto" de $K_5$ ? Diferentes formas de contarlo

Question

Entonces, mi primo me pidió que contara el número de triángulos de un dibujo. La imagen era el gráfico completo en $5$ vértices, conocidos como $K_5$ en la teoría de grafos. Aquí hay una "imagen" de $K_5$ :

Una respuesta parcial se ha dado aquí en MSE en este pregunta lo que puede ser erróneo dependiendo de la interpretación de lo que es un "nodo". En nuestra interpretación del problema, la intersección de dos aristas forma un nuevo nodo. Por lo tanto, los puntos de intersección dentro del pentágono que se encuentran en las aristas de la estrella interior se consideran nodos por sí mismos y, por lo tanto, la fórmula dada en esa respuesta es efectivamente un recuento insuficiente para nuestro problema.

Razoné así:

Caso I - triángulos formados por los tres vértices del pentágono: Esto es dado por ${5 \choose 3}=10$

Caso II - triángulos con exactamente un vértice en el pentágono: Ves que en este caso, la única manera de formar un triángulo es seleccionar los otros dos vértices de la estrella interior adyacentes a nuestro vértice inicial en el pentágono. En este caso, como tenemos $5$ vértices, obtenemos $5$ diferentes triángulos.

Caso III - triángulos con exactamente dos vértices en el pentágono: Me gustaría poder hacer un dibujo para este caso, pero no sé cómo hacerlo. De todos modos, en este caso, tendremos $2$ casos separados:

a) Los dos vértices son adyacentes entre sí: En este caso, obtenemos $3$ triángulos no equivalentes. ¿De cuántas maneras podemos elegir dos vértices adyacentes en el pentágono? $5$ formas. Por lo tanto, obtenemos $15$ triángulos.

b) Los dos vértices no son adyacentes entre sí: En este caso, la elección de dos vértices no adyacentes nos da un triángulo cada vez. Para un vértice fijo del pentágono, podemos elegir dos vértices no adyacentes. Por lo tanto, obtenemos $10$ triángulos esta vez. (Esto es incorrecto, por favor, lea mi edición y los comentarios bajo la pregunta).

Apreciaría mucho una solución elegante que utilice una combinación de teoría de grafos y teoría de grupos. Creo que debería haber una respuesta así y si la tienes, por favor, publícala con explicaciones.

EDITAR: Como ha señalado zar, parece que he sobrecontado el número de triángulos en el caso III b por un factor de dos porque después de elegir una diagonal del pentágono, obtengo un único triángulo. Por supuesto, si en cambio me centro en los vértices del pentágono, dos vértices unidos por una diagonal del pentágono dan lugar al mismo triángulo en el caso III b y por eso he contado de más por un factor de $2$ . Sigo apreciando una solución sistemática que utilice relaciones de recurrencia, teoría de grafos, teoría de grupos o cualquier cosa que dé una visión más matemática y que tal vez se pueda generalizar a problemas que impliquen $p$ - de los gones.

Answer 1

Hay por lo menos dos maneras diferentes de extender este problema a un tamaño mayor $n$ . Aquí hay un enfoque que funciona para la más fácil de las dos formas, que es cuando los vértices de $K_n$ son $n$ puntos en posición general formando un convexo $n$ -gon, por lo que cada nodo interno está en exactamente dos aristas.

Cada triángulo puede asociarse a un triple de aristas distintas de $K_n$ (las aristas que se obtienen si se extienden los lados del triángulo lo máximo posible), y cada triple de aristas se asocia como máximo a un triángulo. Así que sólo tenemos que contar los triples "buenos" que sí dan un triángulo, es decir, cada par de aristas se encuentra (ya sea en un vértice del gráfico original o en un nodo interno).

Supongamos que conocemos el conjunto de puntos finales de un triple de aristas bueno (sin multiplicidad): ¿cuántos triples buenos tienen exactamente esos puntos finales? Si hay seis puntos en el conjunto, $a,b,c,d,e,f$ en orden cíclico, sólo hay una tripleta buena formada por las aristas $ad,be,cf$ . Si tenemos cinco puntos finales, $a,b,c,d,e$ en orden cíclico, hay exactamente un punto en dos de las aristas. Supongamos que es $a$ . Entonces la única posibilidad es $ac,ad,be$ (gracias a Henning Makholm por señalar que mis otras "posibilidades" no eran válidas). Dado que la elección de $a$ era arbitraria, hay $5$ posibilidades en total. Si hay cuatro puntos $a,b,c,d$ en el conjunto, las únicas posibilidades son $ab,bd,ac$ y reordenamientos cíclicos. Por último, si sólo hay tres puntos sólo hay una posibilidad.

Esto significa que el número de triángulos es $\binom n6+5\binom n5+4\binom n4+\binom n3$ .

Para hacer frente a la otra extensión plausible (los vértices forman un $n$ -gon) habría que calcular el número de triángulos degenerados que surgen de tres diagonales que confluyen en un punto, y restarlos.

Answer 2

El problema con el enfoque de los nodos es que no todos los $3$ nodos producen un triángulo. Contar todas las exclusiones puede ser más complejo que simplemente contar triángulos. Suelo utilizar un enfoque sistemático basado en triángulos simples, dobles y triples, y en este caso incluyendo el pentágono interior más $2$ triángulos y pentágono interior más $4$ triángulos. Para estos $5$ casos........

Soltero, $= 10$

Doble, $= 10$

Triple, $= 5$

Pentágono interior $+ 2, = 5$

Pentágono interior $+ 4, = 5$

Total, $= 35$