Encontrar una biyección para demostrar la cantidad de cadenas binarias de longitud $n$ con $k$ 1s no consecutivos es ${{n - k + 1}\choose{k}}$

Question

Estoy confundido en cuanto a cómo encontrar una biyección para probar el conjunto de cadenas binarias de longitud $n$ con $k$ 1s no consecutivos es ${{n - k + 1}\choose{k}}$

Entiendo que si hay una biyección, ambos conjuntos son del mismo tamaño. Así que parece razonable que necesite encontrar una biyección desde este conjunto de cadenas binarias a un conjunto de tamaño conocido ${{n - k + 1}\choose{k}}$ ?

Aunque no entiendo cómo llegar a ese conjunto o demostrar que hay una biyección entre ellos. ¿Podría alguien guiarme en este problema?

Answer 1

Sabes que debe haber un cero entre dos unos adyacentes cualquiera en la secuencia. Puedes eliminar el $0$ inmediatamente a la derecha de cada uno de los primeros $k-1$ los. ¿Con qué te da esto una biyección? En realidad es el conjunto de cadenas arbitrarias de longitud $n-k+1$ con $k$ los. Para encontrar la inversa, toma tu cadena de longitud $n-k+1$ e insertar un $0$ inmediatamente a la derecha de la primera $k-1$ los.