La elección de los números sin números consecutivos.

Question

De cuántas maneras podemos escoger $r$ números de $\{1,2,3,...,n\}$,

En un camino donde no tenemos números consecutivos en el set? (como $1,2$)

Answer 1

Suponiendo que el orden de elección, no importa, imaginar marcar las posiciones de la $r$ números elegidos y dejando espacios en blanco antes, entre y después de ellos durante la $n-r$ sin números elegidos; si $r=3$, por ejemplo, que vas a tener un esqueleto como $_|_|_|_$, donde las barras verticales representan las posiciones en $1,2,\ldots,n$ de los números elegidos. El resto de los $n-r$ números deben ir en el $r+1$ ranuras abiertas en el diagrama, y debe haber al menos uno de ellos en cada una de las $r-1$ de los espacios en el medio. Después de colocar un número en cada una de las ranuras, tenemos $n-r-(r-1)=n-2r+1$ números de izquierda a cabo de manera arbitraria en el $r+1$ ranuras. Este es un estándar de estrellas-y-bares problema: hay

$$\binom{(n-2r+1)+(r+1)-1}{(r+1)-1}=\binom{n-r+1}r$$

formas de hacer. El razonamiento detrás de la fórmula es razonablemente claramente explicado en el enlace.

Answer 2

primero decidimos que vamos a comenzar a elegir de una manera creciente... una vez que hemos elegido un $i$ no eligió cualquier número de$i-1$$1$. así que después de la elección de un número no debemos seleccionar el siguiente número y por lo tanto la elección de $r$ números debemos dejar a $r-1$ números de la elección del último número no vamos a tener ninguna restricción para la próxima.donde $r$ es el número de objetos a ser elegido. así que dejando $r-1$ números, tenemos $n-(r-1)$ o $n-r+1$ números restantes. y podemos elegir el $r$ cifras en $\binom{n-r+1}r$ maneras.