En una mesa redonda, hay $12$ caballeros. Cada par de caballeros contiguos son enemigos. ¿De cuántas maneras puede $5$ ¿se eligen los caballeros de manera que ninguna pareja de caballeros sea enemiga?
Para decirlo de otra manera, ¿de cuántas maneras podemos seleccionar cinco de los doce caballeros de la mesa para que no haya dos de ellos sentados en asientos adyacentes?
Primero resolvemos el problema para una línea, y luego restamos los casos en los que se seleccionan personas en ambos extremos de la línea para garantizar que no se seleccionan dos caballeros adyacentes cuando los extremos de la línea se unen para formar un círculo.
Disponemos siete bolas azules y cinco verdes de manera que no haya dos bolas verdes adyacentes. Colocamos siete bolas azules en fila. Esto crea ocho espacios, seis entre bolas azules sucesivas y dos en los extremos de la fila. $$\square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square$$ Para garantizar que no haya dos bolas verdes adyacentes, debemos elegir cinco de estos ocho espacios para las bolas verdes, lo que puede hacerse en $$\binom{8}{5}$$ formas.
Sin embargo, debemos excluir aquellas disposiciones en las que ambos extremos de la línea están ocupados por bolas verdes, ya que al unir los extremos de las líneas se formaría un círculo en el que dos de las bolas seleccionadas son adyacentes. Si ambos extremos de la fila están ocupados por bolas verdes, nos quedan seis espacios en los que colocar una bola verde. $$\color{green}{\bullet} \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{blue}{\bullet} \square \color{green}{\bullet}$$ Para asegurar la separación de las bolas verdes, debemos elegir tres de estos espacios, lo que puede hacerse en $$\binom{6}{3}$$ formas.
Por lo tanto, el número de maneras en que se pueden seleccionar cinco caballeros de los doce que hay en la mesa redonda para que no haya dos adyacentes es $$\binom{8}{5} - \binom{6}{3}$$
¿De cuántas maneras puede $k$ los objetos se seleccionan entre $n$ objetos dispuestos en un círculo si no hay dos de los $k$ los objetos son adyacentes.
Comenzamos por organizar $n - k$ azul y $k$ bolas verdes en una fila de manera que no haya dos bolas verdes adyacentes, luego resta los casos en los que las bolas verdes ocupan ambos extremos de la fila de manera que las bolas verdes no sean adyacentes cuando unimos los extremos de la fila para formar un círculo.
Razonando como antes, colocando $n - k$ bolas azules seguidas crea $n - k + 1$ espacios, $n - k - 1$ entre el $k$ sucesivas bolas azules y dos en los extremos de la fila. Para garantizar que no haya dos bolas verdes adyacentes, debemos seleccionar $k$ de estos $n - k + 1$ espacios, lo que puede hacerse en $$\binom{n - k + 1}{k}$$ formas. Obsérvese que esto es cero cuando $k > n - k + 1$ .
De ellos, debemos excluir los casos en los que las bolas verdes ocupan los dos extremos de la fila. Si las bolas verdes ocupan los dos extremos de la fila, nos queda $n - k - 1$ espacios. Para garantizar que no haya dos bolas verdes adyacentes, debemos elegir $k - 2$ de estos espacios para las bolas verdes restantes, lo que puede hacerse en $$\binom{n - k - 1}{k - 2}$$ formas.
Por lo tanto, el número de formas que $k$ los objetos pueden ser seleccionados desde $n$ objetos dispuestos en un círculo de manera que no haya dos de los $k$ los objetos son adyacentes es $$\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}$$
