Combinatoria: Selección de objetos dispuestos en círculo

Question

Si $n$ objetos distintos están dispuestos en un círculo, tengo que demostrar que el número de maneras de seleccionar tres de estos $n$ cosas para que no haya dos de ellas una al lado de la otra es $\frac{1}{6}n(n-4)(n-5)$ .

Inicialmente puedo seleccionar $1$ objeto en $n$ formas. Entonces sus vecinos no podrán ser seleccionados. Así que tendré $n-3$ objetos a elegir $2$ objetos de. De nuevo, puedo seleccionar el segundo objeto en $n-3$ formas. Los vecinos de este objeto no pueden seleccionarse. Sin embargo, a partir de aquí no puedo ampliar este argumento, ya que la selección del tercer objeto depende de la posición del primero y del segundo. ¿Existe algún método más sencillo para demostrar el resultado?

Answer 1

Referencias: El número de formas de elegir $d$ no consecutivos en un círculo de tamaño $n$ es $${n-d+1 \choose d} - {n-d-1 \choose d-2}.$$ Aryabhata explica la derivación en la respuesta aquí Probabilidad de cumpleaños consecutivos . El primer término es el número de formas de elegir $d$ no consecutivos posiciones en un línea de tamaño $n$ y el segundo término resta aquellos acuerdos en los que las posiciones $1$ y $n$ fueron elegidos.

Esta expresión también puede reescribirse como $${n\over n-d}{n-d\choose d}.$$ Este formulario, denominado $d_k$ en el siguiente enlace, se utiliza en la solución de la página problema de menage (con $2n$ en lugar de $n$ y $k$ en lugar de $d$ ).

Answer 2

Sugerencia Cuenta las formas de seleccionarlos para que al menos dos sean vecinos (puedes dividirlo en dos casos). Esto es más fácil. A continuación, resta el número total de formas de seleccionar tres objetos. Factoriza el resultado y obtendrás la respuesta.

Answer 3

Elige primero un objeto. Luego piensa en el resto $n-3$ objetos en una línea. A continuación $n-4$ espacios entre los restantes $n-3$ objetos en la línea. Elija 2 de los $n-4$ y elija el objeto situado a la izquierda del espacio izquierdo y a la derecha del espacio derecho.

Este último paso está en correspondencia 1-1 con las formas de tener los 2 objetos finales; por lo tanto dividimos por 3 (correspondiente a la primera elección inicial, que podría haber sido cualquiera de los 3 objetos para empezar) dando $1/3 \cdot n \cdot \binom{n-4}{2} = 1/6 \cdot n(n-4)(n-5)$ .