Dejemos que $n$ los objetos se coloquen en un círculo. Se supone que debemos seleccionar $k$ objetos de tal manera que ningún $2$ de la $k$ los objetos se colocan adyacentes entre sí

Question

Digamos que $n$ Los objetos se colocan de forma circular. Se supone que debemos seleccionar $k$ objetos de tal manera que ningún $2$ de la $k$ Los objetos se colocan adyacentes en el círculo.

Esto era lo que estaba pensando para resolver realmente este problema

Un script tiene $n$ cartas $b_1, \cdots , b_n$ .

Para algunos $k < n/2$ asumir que todas las palabras formadas por cualquiera de las k letras (escritas de izquierda a derecha) son significativas. Estas palabras se denominan $k-$ palabras. A $k-$ La palabra se considera sagrada si:

i) ninguna letra aparece dos veces y,

ii) si una carta $b_i$ aparece en la palabra entonces las letras $b_{i-1}$ y $b_{i+1}$ no aparecen. (Aquí $b_{n+1} = b_1$ y $b_0 = b_n$ .)

Por ejemplo, si $n = 7$ y $k = 3$ entonces $b_1b_3b_6$ , $b_3b_1b_6$ , $b_2b_4b_6$ son sagrados $3-$ palabras. Por otro lado otro lado $b_1b_7b_4$ , $b_2b_2b_6$ no son sagradas.

¿Cuál es el número total de sagrados $k-$ ¿palabras?

Pero todavía no tengo ni idea, de cómo seguir adelante con mi pensamiento. Puede alguien darme una pista.

Answer 1

Contamos el número de selecciones admisibles de una especial y $k-1$ objetos ordinarios. El objeto especial puede ser elegido en $n$ formas. Cuando se hace esta elección tenemos un conjunto lineal de $n-1$ objetos a la izquierda. La selección de los objetos ordinarios es una palabra binaria de longitud $n-1$ teniendo exactamente $k-1$ los. Escríbelas con un amplio espacio entre ellas y en los extremos: $$-1-1-\ldots-1-1-\ .$$ A continuación, escriba un cero en cada uno de los $k$ espacios: $$-01-01-\ldots-01-01\>0-\ .$$ Todavía hay $k$ espacios restantes, en los que tenemos que escribir $n-2k$ ceros de forma arbitraria. Según las estrellas y las barras esto se puede hacer en $${(n-2k)+(k-1)\choose k-1}={n-k-1\choose k-1}$$ formas. El número total $N$ de selecciones admisibles de todos los objetos llega entonces a $$N={n\over k}{n-k-1\choose k-1}\ .$$ Tenemos que dividir por $k$ ya que en realidad ninguno de los $k$ objetos elegidos está especializada. Por ejemplo, cuando $n=5$ , $\>k=2$ obtenemos $N=5$ como era de esperar.

Answer 2

No es más que un problema de estrellas y barras disfrazado. Considere $n$ objetos que se colocan alrededor del círculo. Considere $k$ barras para dividir el círculo en $k$ partes. Dejemos que $a_1,a_2, \ldots, a_k$ denotan el número de objetos entre estas barras.

Seleccione la posición inicial de la primera barra en $n$ formas.

Así que tenemos $a_1+a_2+\ldots+a_k=n-k$ y $a_i \geq 1, \forall 1 \leq i \leq k$ debido a la condición dada de que no hay dos objetos elegidos que sean adyacentes.

Además, como se trata de una permutación circular, cada solución se repite por un factor de $k$ . Por ejemplo, la solución de la tupla $(a_1,a_2,\ldots a_k)$ es idéntico a cualquiera de los $k$ permutaciones cíclicas de $(a_1,a_2,\ldots,a_k)$ .

Por lo tanto, la respuesta final es $\frac{n}{k}{n-k-1 \choose k-1}$ .

Answer 3

En realidad, una vez elegido el primer elemento a conservar, se rompe lo circular.

Digamos que tienes $n$ objetos. Usted tiene $n$ opciones para elegir el primer objeto. Una vez hecho esto, hay que elegir $k-1$ objetos del resto de $n-3$ (eliminando los dos vecinos). Pero en este nuevo caso, no hay más comportamiento circular, sólo una cadena.

Para el siguiente objeto, tenemos dos opciones: o elegimos un extremo de la cadena, o un objeto en el medio.

Hay $2$ para un extremo de la cadena (excepto si sólo hay un objeto restante), y entonces vamos recursivamente al mismo problema con $k-2$ para elegir $n-5$ objetos.

Si elige un objeto en el centro (hay $n-5$ de ellos), en realidad se crean dos subinstancias del problema: hay que elegir $k-2$ entre dos cadenas de elementos, cuyas longitudes suman $n-6$ . Supongo que este punto es el más complicado, con varias combinatorias implicadas.

Creo que descomponer los problemas en subrutinas como esta podría ayudar a encontrar una fórmula recursiva, dado $n$ y $k$ Pero no tengo ninguna otra pista, salvo la de hacer pruebas para valores pequeños y tratar de encontrar un patrón que surja.

Espero que eso ayude.