Pregunta de combinatoria sobre la elección de enteros no consecutivos

Question

El problema es el siguiente:

¿Cuántas maneras hay de elegir $6$ de la primera $20$ enteros positivos tales que ningún $2$ de ellos son consecutivos?

A primera vista, parece un problema de combinatoria bastante sencillo, pero después de intentarlo (y fallar) decidí que no es tan fácil como parece.

Mi método fue encontrar el número de formas en que se puede elegir $6$ enteros tales que hay fait existen enteros consecutivos, entonces reste eso del número total de posibilidades ( ${20 \choose 6}$ )

Lo primero que hice fue tomar todas las posibilidades de pares de enteros consecutivos (hay $19$ de ellos, comenzando $(1,2),(2,3),(3,4),\dots,(19,20)$ ). Hay $\binom{18}{4}$ formas de elegir el resto $4$ enteros, por lo que hay un total de

$$19\times \binom{18}{4}=58140$$ posibilidades. Sin embargo, este número es mayor que el número total de posibilidades (que es $38760$ ). ¿Qué estoy haciendo mal?

Answer 1

Solución a través de estrellas y barras :

Supongamos que los números seleccionados son barras y los números no seleccionados son estrellas. Entonces tenemos que encontrar el número de disposiciones tales que entre dos barras cualesquiera haya al menos una estrella.(hay $6$ bares y $14$ estrellas).

Hay $5$ espacios entre barras. Por lo tanto, debe haber necesariamente $5$ estrellas ahí dentro. Así que todo lo que tenemos que hacer ahora es arreglar el resto $15$ objetos ( $9$ estrellas y $6$ barras) podemos hacerlo en $\binom{15}{6}$ formas.

Answer 2

Supongamos que ya ha seleccionado el $6$ enteros. Ordénalos en orden creciente. Restar $1$ al segundo número, $2$ al tercer número $3$ al cuarto número, $4$ al quinto número y 5 dólares al sexto número.

Ahora tendrá $6$ números diferentes entre $1$ y $15$ . Estos números están determinados de forma única por los enteros iniciales.

A la inversa, tome $6$ números entre $1$ y $15$ (Posiblemente algunos de ellos consecutivos) y añadir $1$ al segundo, $2$ al tercero y así sucesivamente. Ahora tendrá $6$ números, ninguno de ellos consecutivo, y todos ellos entre $1$ y $20$ .

Por lo tanto, hay tantas formas de elegir $6$ números no consecutivos como hay para elegir $6$ número entre $1$ y $15$ libremente.

Por lo tanto, la respuesta es $\binom{15}{6}$

Answer 3

Para cualquier selección de k enteros no constitutivos de un conjunto de n elementos X={ $x_1x_2...x_n$ }

Cualquier subconjunto de S de X puede representarse como una cadena binaria,
$b_s$ = $a_1a_2...a_n$ , donde $a_i=1$ si $x_i \in S$ , $0$ de lo contrario.

Está claro que queremos contar $b_s$ teniendo exactamente k $1$ y (n-k) $0$ 's $s.t$ $b_s$ no contiene ninguna secuencia de $1$ 's. Hay un total de $(n-k+1)$ posiciones para $1$ ya que puede aparecer entre dos veces consecutivas $0$ (total n-k-1 opciones)o a la izquierda a la primera $0$ o hasta el último $0$ . Tenemos que seleccionar k de estas posiciones para colocar k $1$ 's. Por lo tanto, hay un total de ${n-k+1\choose k}$ formas.