Probabilidad vértices son adyacentes en un polígono

Question

Con respecto a mi pregunta original:

Un subconjunto de k vértices es elegido a partir de los vértices de un N-ágono regular. ¿Cuál es la probabilidad de que dos vértices son adyacentes?

Supongo que las respuestas que se suscitó a mi pregunta eran de esperar. Verás, he estado en tu posición, y pensó en lo que había hecho, en muchas ocasiones. Pero sobre todo no en el área de matemáticas.

Por la forma de proporcionar el fondo, yo no soy un estudiante en absoluto. De hecho, soy un bioquímico y de tiempo parcial de la universidad de instructor. Muchas veces he dado las respuestas a los estudiantes que post química/bioquímica preguntas (muestras bajo petición). Y, al igual que usted, espero que yo no tengo (o no!) convertirse en un vehículo para los estudiantes a evitar el pensamiento a través de SUS química de las asignaciones de la tarea.

La pregunta de arriba, lo creas o no, viene desde lo local, con sede en Boston programa de televisión "extrahelp", organizado por un poco sarcástico personaje que fue por el nombre de "el Señor de las Matemáticas". Estaba destinado a la K-12 demográfica, pero, según la historia detrás del video, en M. I. T. estudiante estaba escuchando, y le pidió a la pregunta, aparentemente para darle a este hombre su merecido. El vídeo ya no está disponible online, pero me puede enviar una copia, si no que la mente es 25.1 MB, y que no tengo acceso a cualquier servidor FTP en la universidad donde doy clases. Es hilarante.

Cuando vi este video (y después de que dejé de reír), me he interesado por la pregunta en sí misma. Y dado que al menos uno de ustedes pidieron para cualquier trabajo que he hecho por mi cuenta, aquí es como llegué antes de que hice mi post original:

1) N debe, por supuesto, ser un entero positivo >= 3. k debe ser un entero positivo <= N. 2) Cuando k = 1, la solución es trivial (p = 0). De hecho, la no-trivial de los valores de k son: 2 <= k <= (N \ 2), donde "\" es la división entera. Para otros valores de k, p = 1. 3) Para los no-trivial de los valores de k, el denominador es C(N,k). 4) Para k = 2, el numerador es N. 5) Para k = 3, el numerador es N(N-k). 6) Para N par, y k = N / 2, el numerador es N – 2. Para N impar, y k = N \ 2, el numerador es C(N,k) – N. 7) Para k = (N \ 2) -1, el numerador puede ser C(N,k) – N(N-k).

Donde tengo problemas es, obviamente, llegar desde aquí a una solución general. Se ha sugerido que me tome el enfoque de la búsqueda de la expresión general para la probabilidad de NO seleccionar vértices adyacentes, pero la respuesta general de p = 1 - [C(N-k,k) / C(N,k)] no es confirmada por los ejemplos que estoy segura (es decir, donde N es tan pequeña que las respuestas pueden ser confirmado por la enumeración)

Estoy seguro de que estaréis de acuerdo en que, por ahora, ha pasado suficiente tiempo, que, si esto fuera realmente una tarea cuestión, que la fecha de vencimiento de tal tarea habría pasado. Además, espero que les haya convencido de que más allá de una sospecha razonable de que: a) definitivamente no es una tarea cuestión, y b) la que he trabajado en el problema a mí mismo a tal grado que no he pasado esta fuera de los encuestados sin hacer algún esfuerzo.

Answer 1

Me disculpo por prejuzgar la cuestión. Una versión más corta de este fondo explicación al principio, habría sido útil. La verdad es que muchas preguntas de este tipo se muestran como tarea en títulos de grado de la probabilidad y la combinatoria de los cursos.

Un problema equivalente es contar no adyacentes subconjuntos de vértices de tamaño $k$. Ayuda a marcar uno de los elegidos, los vértices, lo que aumenta la respuesta por un factor de $k$. Cualquiera de las $n$ vértices pueden ser marcados, y después de eso, el vértice a la derecha de la marcada uno no puede ser elegido. Si se casan cada vértice a la ranura que se encuentra a su derecha, la combinatoria patrón (de nuevo excluyendo el marcado vértice y el uno a su derecha) es equivalente a la palabra de longitud $(n-2)-(k-1)$ en dos símbolos, "un" por no usar, y "b" para "que se utiliza casado no utilizados"; y hay $k-1$ de la "b" de las letras. Así que la respuesta final de este conteo problema es: $$N(n,k) = \frac{n}{k}\binom{n-k-1}{k-1}.$$ Por supuesto, el recuento de respuesta también puede ser convertido a una probabilidad.

(El problema todavía puede pertenecer mejor en AoPS en lugar de aquí, pero no me importa demasiado.)

Answer 2

No es tan difícil calcular la probabilidad de que no hay dos puntos adyacentes:

Bien podemos suponer que el primer vértice es elegido para nosotros. Así que vamos a ignorarlo y desenrollar el resto del polígono en una línea. Ahora imagina que yo escriba una secuencia de $0$s y $1$s a lo largo de esta línea para indicar si los vértices correspondientes son elegidos o no. La condición de esta secuencia es que: el primer y el último número de esta secuencia no debe ser $1$s, y cualquier $1$ debe ser seguido por un $0$. Así que, vamos a sustituir cualquier subsequence de la forma $01$ $x$ e ignorar el pasado $0$ en la secuencia, así por ejemplo tendríamos la transformación de $01001010 \rightarrow x0xx$. Ahora no hay ninguna condición en la secuencia de $0$s y $x$s, otros que la longitud y el número de $x$s.

La longitud de la nueva secuencia se $(n-1)-(k-1)-1 = n-k-1$, y contendrá $k-1$ $x$s, por lo que el número de secuencias es sólo $\binom{n-k-1}{k-1}$, mientras que el número de todas las secuencias de $0$s y $1$s (incluyendo violando nuestra condición) es $\binom{n-1}{k-1}$. Por lo que la probabilidad de que usted quiere es $1-\frac{\binom{n-k-1}{k-1}}{\binom{n-1}{k-1}}=1-\frac{(n-k-1)!(n-k)!}{(n-1)!(n-2k)!}$.

Sólo para estar seguro, vamos a ver que con $n = 6, k = 3$. Nuestra fórmula nos da una probabilidad de $1-\frac{2!3!}{5!0!} = 1-\frac{12}{120} = \frac{9}{10}$. Podemos comprobar con la mano que hay dos maneras para que los vértices no todos tienen que ser adyacentes - los dos triángulos en el hexágono, y hay un total de $\binom{6}{3} = 20$ formas de elegir los tres vértices, y esto nos da una probabilidad de $1-\frac{2}{20} = \frac{9}{10}$. ¡Hurra! No fuera por uno de los errores!