¿De cuántas maneras se puede elegir $k$ números de $\{1,2,3,\dots,n\}$ ¿así que ninguno de ellos es consecutivo?

Question

Soy un novato en combinatoria y todavía no tengo suficientes herramientas para manejar este tipo de problemas.

Suponiendo que tengo un conjunto de enteros: $ \{1,2,3,4,\dots,n\} $

¿De cuántas maneras puedo elegir $k$ números de esos $n$ ¿ de manera que ninguno de ellos sea consecutivo?

Por ejemplo, para el siguiente conjunto $ \{1,2,3,4,5\} $

Para $ k=3 $ Sólo tengo una opción: $\{1,3,5\}$

Mi propósito es, en primer lugar, comprender la forma en que usted pensaría en este problema, no necesariamente la solución en sí misma (yo tengo la respuesta final para ello).

Gracias.

Answer 1

Lugar $n - k$ bolas azules en fila, dejando espacios entre ellas. Ahora tenemos $n - k - 1$ espacios entre las sucesivas bolas azules y los dos espacios de los extremos de la fila para un total de $n - k + 1$ espacios en los que colocar $k$ bolas verdes. Elegimos $k$ de estos $n - k + 1$ espacios para las bolas verdes. Ahora numeramos las bolas de izquierda a derecha. Los números de las bolas verdes son el conjunto deseado de enteros no consecutivos. Por lo tanto, el número de formas de seleccionar $k$ enteros del conjunto $\{1, 2, 3, \ldots, n\}$ para que no haya dos consecutivos es $$\binom{n - k + 1}{k}$$

Para ilustrar la idea, veamos $n = 10$ y $k = 4$ . Comenzamos con $n - k = 6$ bolas azules.

$$\color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}\ \ \color{blue}{\bullet}$$

Elegimos cuatro de los siete espacios disponibles para colocar una bola verde.

$$\color{green}{\bullet}\color{blue}{\bullet}\color{green}{\bullet} \color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{blue}{\bullet}\color{blue}{\bullet}\color{green}{\bullet}\color{blue}{\bullet}$$

Si numeramos las bolas de izquierda a derecha, vemos que esta selección particular corresponde al subconjunto $\{1, 3, 6, 9\}$ .

Answer 2

Denota el número de formas de elegir $k$ números no consecutivos de $\{1, 2, \cdots, n\}$ como $C_{n, k}$ . Hay dos casos.

• $n$ es elegido. En este caso, hay que elegir $k - 1$ números no consecutivos de $\{1, 2, \cdots, n - 2\}$ es decir $C_{n - 2, k - 1}$ .

• $n$ no es elegido. En este caso, hay que elegir $k$ números no consecutivos de $\{1, 2, \cdots, n -1 \}$ es decir, $C_{n-1, k}$ .

En otras palabras, $C_{n, k} = C_{n-2,k-1} + C_{n-1,k}$ .

Answer 3

Comienza con $k$ palos (que representan los números elegidos) y $n-k$ puntos (que representan los otros números),

y eliminar $k-1$ puntos (que serán nuestros "bloqueadores").

Esto deja $k$ palos y $n-2k+1$ puntos, que pueden disponerse en $\color{blue}{\dbinom{n-k+1}{k}}$ formas;

y luego podemos insertar el $k-1$ bloqueadores entre los palos para asegurarse de que no son consecutivos.