¿De cuántas maneras distintas puede $r$ no consecutivos enteros de ser elegido en la primera $n$ enteros?

Question

Durante el auto-estudio, me encontré con la pregunta de cuántas formas de seis números que pueden ser elegidos a partir de los números 1 - 49 sin sustitución, indicando que no hay dos de los números que ser consecutivos.

Puedo obtener un simple límite inferior diciendo que, en el peor de los casos, cuando usted elija un número en particular, ahora hay tres números que no pueden ser elegidos siguiente. Por ejemplo, si soy la primera pick 17, entonces no se puede elegir de 16, 17 o 18 para el resto de las opciones. Esto me da el límite inferior

$$\frac{49*46*43*40*37*34}{6!} = 6,773,770 \frac{8}{9}$$

Este es aproximadamente el 48% de % de${}_{49}C_6 = 13,983,816$. En realidad, la respuesta debe ser más grande (y un número entero). No he encontrado una forma de calcularlo, aunque.

El problema original se le pide que muestre que la probabilidad de tener no enteros consecutivos cuando usted elige seis es mayor que 50%, por lo que si el problema es complicado contar exactamente, mejores aproximaciones que muestran la respuesta está por arriba del 50% también sería apreciada.

Por supuesto, puede utilizar un ordenador para hacer el recuento, pero estoy interesado en el aprendizaje de los métodos que me estoy perdiendo.

Answer 1

Otra buena manera de resolver este tipo de problemas es establecer una correspondencia con un problema que ya saben cómo resolver. En este caso, imagina que tienes un conjunto ordenado de seis números no consecutivos $a_1, a_2, \dots a_6$ entre 1 y 49. ¿A qué se parece? Así, el primer número $a_1$ es esencialmente arbitrario; no puede ser mayor que un cierto valor (es decir, 39) o de lo contrario no hay "espacio" para cinco números no consecutivos por encima de él, pero podemos ignorar que, por ahora. El segundo número $a_2$ tiene que ser mayor que $a_1+1$ — que es lo que significa ser no consecutivos, después de todo — así que sabemos que $a_2-1$ (llaman a esto $b_2$) es mayor que $a_1$. Del mismo modo, $a_3$ tiene que ser mayor que $a_2+1$, lo $a_3-1$ es mayor que $a_2$, e $a_3-2$ es mayor que $a_2-1 = b_2$; podemos llamar a esto $b_3$. Y así sucesivamente, y así sucesivamente, hasta que definimos $b_6 = a_6-5$. Pero esta correspondencia funciona en ambos sentidos — dada la $b_n$ es fácil obtener el $a_n$ — y así tenemos una correspondencia uno a uno entre nuestras series de números consecutivos y ordinaria de la combinación (pero con diferentes límite superior - se puede ver lo que debería ser?). Se toma un tiempo para construir este tipo de instinto, sino aprender a detectar estas correspondencias es la más básica de la herramienta para probar la existencia de la mayoría de la combinatoria de las identidades.

Answer 2

En analogía con el triángulo de Pascal, definir D(n,r) como el número de formas de seleccionar r objetos de n por no dos consecutivos. Usted puede utilizar 1 o no. Si usted lo utiliza, no se puede usar 2 pero solo necesitas escoger r-1. Si usted no la uso tiene n-1 elementos para la recogida de r. De manera que D(n,r)=D(n-2,r-1)+D(n-1,r). El caso base es D(2r-1,r)=1 para valores como esta se puede utilizar una hoja de cálculo.