6 votos

número de maneras de elegir puntos de $r$ %#% puntos de #% dispuestos en un círculo tal que no hay puntos consecutivos se toma.

número de maneras de elegir a $r$ puntos de $n$ ponts dispuestos en un círculo, de tal manera que no hay puntos consecutivos que se toma.

(He visto a algunas preguntas SE relacionan con ello. Pero estoy tratando de resolverlo usando mi propio método).

Vamos a los puntos que se toman en una línea recta $\{A_1,A_2,...,A_n\}$. Si tengo que elegir me $r$ puntos de tal manera que no hay dos puntos consecutivos. Vamos a los puntos escogidos ser representado por $\{x_1,x_2,...,x_r\}$. El número de maneras de elegir dichos puntos es el mismo que el número de maneras de colocar estos $r$ puntos entre los $n-r$ objetos tales que ninguno de los puntos de $\{x_1,x_2,...,x_r\}$ vienen juntos. Ya que estoy hablando sólo de la "elección" de los puntos, voy a suponer que todos los puntos a ser idénticos.

Esto puede ser calculado suponiendo que los huecos entre las $n-r$ inicial de los objetos. Habrá $n-r$ diferencias desde el extremo izquierda de la brecha y el derecho de la mayoría de gap son las mismas para un arreglo circular. Primero voy a poner a $x_1$. El número de maneras de colocar el resto de los $r-1$ $n-r-1$ lagunas es $$^{n-r-1}C_{r-1}$$ (los puntos se supone que son idénticos).

Del mismo modo, Si empiezo con $x_2$, el número de maneras en que se $$^{n-r-1}C_{r-1}$$

Por lo que el total será de $$n\cdot^{n-r-1}C_{r-1}$$

Pero la respuesta dada es $$\frac{n\cdot^{n-r-1}C_{r-1}}{r}$$

4voto

DiGi Puntos 1925

Hay varios problemas con su enfoque.

  • Es cierto que después de colocar $x_1$, $\binom{n-r-1}{r-1}$ maneras de colocar el resto de los $r-1$ de los puntos, pero no has tenido en cuenta el hecho de que no se $n-r$ diferentes plces poner $x_1$.

  • Cada uno de los puntos de $x_k$ da lugar a la misma serie de acuerdos, por lo que incluso si el $\binom{n-r-1}{r-1}$ figura correcta para que el régimen después de colocar $x_1$, usted no debe multiplicar por nada.

  • Incluso si fuera cierto que para cada una de las $x_k$ obtener $\binom{n-r-1}{r-1}$ arreglos diferentes, y diferentes puntos de $x_k$ le dio arreglos diferentes, hay$r$$x_k$, no $n$, por lo que el número total de diferentes medidas serían $r\binom{n-r-1}{r-1}$ arreglos, no $n\binom{n-r-1}{r-1}$.

Su enfoque puede ser, pero tienes que ser bastante cuidadoso. Imagina que el $n$ puntos están numerados de derecha a izquierda desde $1$$n$. Supongamos que tenemos una lista de las lagunas $G_1,\ldots,G_{n-r}$ en orden de las agujas del reloj. Hay $\binom{n-r}r$ formas para recoger $r$ estos $n-r$ huecos para los puntos de $x_1,\ldots,x_r$, lo que voy a asumir que se enumeran en el orden consecutivo de las agujas del reloj. Sin embargo, este overcounts. Específicamente, estamos contando cada una selección de $r$ $n-r$ veces. Esto puede ser un poco difícil de ver, así que permítanme utilizar un ejemplo concreto. Supongamos que ponemos a $x_1$ en $G_1$, $x_2$ en $G_2$, y así sucesivamente, finalmente situar $x_r$$G_r$. Esto significa que hay una unchosen punto entre el$x_1$$x_2$, uno unchosen punto entre el$x_2$$x_3$, y así sucesivamente a uno unchosen punto entre el$x_{r-1}$$x_r$, con el resto de unchosen puntos entre el$x_r$$x_1$.

Ahora supongamos que en lugar de que pongamos $x_1$ en $G_2$, $x_2$ en $G_3$, y así sucesivamente, finalmente situar $x_r$ a $G_{r+1}$. Esto también significa que hay una unchosen punto entre el$x_1$$x_2$, uno unchosen punto entre el$x_2$$x_3$, y así sucesivamente a uno unchosen punto entre el$x_{r-1}$$x_r$, con el resto de unchosen puntos entre el$x_r$$x_1$. En otras palabras, obtenemos exactamente la misma circular progresión de la elegida y unchosen puntos. Lo mismo es cierto no importa que la disparidad se $x_1$, siempre que $x_2,\ldots,x_r$ son consecutivamente poner en lagunas adyacentes de las agujas del reloj. Hay $n-r$ lagunas, y podríamos empezar por poner $x_1$ en alguna de ellas, por lo que hay $n-r$ formas de obtener exactamente la misma circular progresión de la elegida y unchosen puntos. Y lo que es la verdad de la disposición que tenemos cuando se nos ponen los puntos elegidos en huecos consecutivos es cierto para cualquier otro arreglo así. Por lo tanto, estamos contando cada uno de acuerdo $n-r$ tiempos y la necesidad de dividir por $n-r$. Ello nos da

$$\frac1{n-r}\binom{n-r}r=\frac1r\binom{n-r-1}{r-1}\;.\tag{1}$$

Por supuesto, usted sabe que esto no es correcto, ya que le falta un factor de $n$; ¿qué hemos perdido?

El problema es que sólo hemos establecido la relación de las posiciones de los puntos elegidos: sabemos cuántos unchosen puntos hay entre consecutivos puntos escogidos, pero no sabemos si el primer punto elegido es el punto de $1$, punto de $n$, o algo en el medio. Así, cada una de las modalidades de elegido y unchosen puntos que hemos contado en realidad corresponde a la $n$ diferentes opciones de $r$ de puntos con el mismo espaciado entre los puntos elegidos. Y que nos da el factor faltante de $n$: hay realmente

$$\frac{n}r\binom{n-r-1}{r-1}$$

las formas para elegir el $r$ puntos.

Si nos preocupáramos sólo sobre el espaciado de los puntos elegidos y no acerca de su absoluta posiciones alrededor de la circunferencia, ya no había necesidad de hacer esa última corrección: $(1)$ sería el número de la derecha.

3voto

Roger Hoover Puntos 56

Elige un punto arbitrario en el círculo y "romper" el círculo en ese punto. La configuración resultante puede ser visto como una cadena de longitud $n$ sobre el alfabeto $\Sigma=\{0,1\}$, con las siguientes propiedades:

  • Hay exactamente $r$ caracteres "$1$";
  • No hay consecutivos "$1$"s;
  • El primer dígito y el último carácter no son tanto "$1$".

Si el primer carácter y la última "$0$", estamos expresando $n-r$ como una suma de $r+1$ enteros positivos, que representan las longitudes de los bloques de ceros. Por las estrellas y las barras, hay $\binom{n-r-1}{r}$ cadenas de ese tipo. Por otro lado, si el primer carácter es cero, mientras que el último es uno, o por el contrario, estamos expresando $n-r$ como una suma de $r$ enteros positivos. De ello se deduce que el número total de nuestros arreglos está dada por:

$$\begin{eqnarray*} \binom{n-r-1}{r}+2\binom{n-r-1}{r-1} &=& \binom{n-r-1}{r-1}+\binom{n-r}{r}\\[0.2cm]&=&\color{red}{\frac{n}{n-r}\binom{n-r}{r}}\\[0.2cm]&=&\color{blue}{\frac{n}{r}\binom{n-r-1}{r-1}}.\end{eqnarray*}$$

3voto

andy.gurin Puntos 1516

Llamaremos el $r$puntos motores $(E)$ y el resto bogies $(B)$

Mirando hacia la derecha, forma $r$ trenes de $[BE]$, entonces el $(n-2r)\;\;B's$ son independiente.

Sujete a los trenes por medio de estrellas y barras de $\dbinom{n-r-1}{r-1}$ maneras,

El primer motor puede colocarse en cualquier lugar de $1$ $n$ asumiendo un círculo numerado, pero cada combinación será repetido $r$ veces, hasta multiplicar por $\dfrac{n}{r}$

2voto

eljenso Puntos 7690

Vamos a comenzar con la etiqueta de los puestos a cubrir $1,2,\cdots,r$ va alrededor del círculo en un orden cíclico, decir hacia la izquierda. (Estas posiciones no están ordenados de ninguna manera en el problema, sólo debemos introducir esta cíclico de orden a facilitar un recuento argumento necesario.)Debe haber lagunas $g_k \ge 1$ entre cada uno de los etiquetados posición y sus dos adyacentes etiquetados posiciones. Esto le da a la cíclico de pedidos $$g_1,1,g_2,2,\cdots,g_r,r.$$ Aquí la primera brecha $g_1$ sirve como la brecha entre los etiquetados posición $r$ y etiquetados en la posición $1.$ Ahora la suma de los $g_k$ $n-r$ y ya que cada uno es, al menos, $1$ podemos definir $h_k=g_k-1$, de modo que $h_k \ge 0$ e las $h_k$ total $n-2r.$ destacar: esto sólo representa un ciclo de pedido, no las posiciones finales de las cosas.

Ahora volvemos a contar cuántas soluciones hay para $$h_1+h_2+\cdots+h_r=n-2r, \tag{1}$$ y tenga en cuenta que hay $r-1$ más señales, de tal manera que el uso de "estrellas y barras" tenemos que añadir el número de signos más para el total $n-2r$ conseguir $(n-2r)+(r-1)=n-r-1.$ (1) $C(n-r-1,r-1)$ soluciones, el uso de $C(m,k)$ a significar el coeficiente binomial.

Ahora vamos a $A$ ser nuestro deseado recuento del número de colocaciones de la $r$ de las cosas en la $n$ posiciones alrededor del círculo, donde para este recuento de los puestos son considerados como un subconjunto, por lo que no están ordenadas (de forma cíclica o de otra manera). De ello se desprende que una situación dada contado en $A$ se puede convertir en uno en el que los puestos son cíclicamente etiquetados en $rA$ formas, ya que uno puede elegir cualquiera de las $r$ colocó posiciones y llamar a $1$ la inducción de una cíclica con el pedido en el puesto de las posiciones.

Por otro lado, el binomio coeffficient que cuenta con las soluciones a$1$, si se multiplica por $n$ a cuenta para la rotación de la orden cíclico, en definitiva una de las $n$ posibles ubicaciones para ello, también se puede contar para el número de colocaciones de la $r$ cosas en sus posiciones, donde esta vez, el ciclo de pedidos de dichos puestos de trabajo ya ha sido realizado por la construcción.

En suma, se obtiene la ecuación $rA=nC(n-r-1,r-1),$ y dividiendo aquí por $r$ conduce a la deseada fórmula para el número de $A$ de maneras de seleccionar el $r$ posiciones alrededor del círculo havint $n$ posiciones en todos.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X