Color $m$ vértices de un gráfico cíclico rojo tal que hay exactamente $k$ segmentos rojos.

Question

Dejemos que $n,m,k$ sean enteros positivos con $$n\ge m\ge k\ge2,\quad n\ge 2k$$ y considerar el gráfico cíclico con $n$ vértices. ¿Cuántas formas diferentes hay de colorear cada vértice en azul o en rojo de forma que

• Un total de $m$ vértices es de color rojo
• Hay $k$ segmentos rojos en total

Si una coloración puede convertirse en otra girando el gráfico, estas dos se consideran coloraciones diferentes (excepto, por supuesto, cuando una rotación por $0^\circ$ es suficiente).

---

Por supuesto, contar los gráficos en los que sólo se cumple una de estas condiciones no es difícil.

• Hay ${n\choose m}$ diferentes formas de colorear el gráfico de manera que exactamente $m$ los vértices se colorean de rojo.
• Hay $2{n\choose 2k}$ formas de colorear el gráfico de manera que haya exactamente $k$ segmentos rojos.

Answer 1

Consideremos una restricción adicional: el vértice $1$ debe ser azul.

Entonces tenemos que distribuir $m$ vértices rojos en $k$ segmentos distinguibles no vacíos. Por el método de las estrellas y las barras obtenemos $k-1$ bares y $m$ estrellas, pero cada barra necesita una estrella a su izquierda, y tenemos que terminar con una estrella. Esto da $\binom{m-1}{k-1}$ opciones.

A continuación, tenemos que poner el $k$ segmentos entre el $n-m-1$ vértices azules restantes, y entre dos segmentos cualesquiera tiene que haber al menos un vértice azul. Por un razonamiento similar al anterior obtenemos $\binom{n-m}{k}$ opciones.

En total hay $\binom{m-1}{k-1}\binom{n-m}{k}$ opciones. Por simetría, lo mismo ocurre si elegimos cualquier otro vértice que $1$ para ser azul. Podemos considerar que todos los vértices pueden ser azules, y entonces habremos considerado todas las coloraciones válidas exactamente $n-m$ tiempos. Esto significa que hay $\frac{n}{n-m}\binom{m-1}{k-1}\binom{n-m}{k}$ colorantes válidos en total.