Regresemos al problema del post anterior (subconjuntos sin consecutivos):
Sea $S =\{1,2,...,n\}$. ¿De cuántas formas se puede elegir un subconjunto de tamaño $r$ y sin consecutivos?
Solución biyectiva ("descubierta" con el método regula falsi)
Sin restricciones serían $C(n,r)$. Pero algunos de esos subconjuntos tienen consecutivos. Sea $B = \{b_1,b_2,...,b_r\}$ un subconjunto de $S$ de tamaño $r$. Por ejemplo, si fuese $B = \{1,2,...,r\}$, lo podríamos convertir a $ \{1,3,5,...\}$ --que no tiene consecutivos--, lo cual equivale a dejar el primero igual, sumarle 1 al segundo, 2 al tercero, etc.Regresemos al problema del post anterior (subconjuntos sin consecutivos):
Sea $S =\{1,2,...,n\}$. ¿De cuántas formas se puede elegir un subconjunto de tamaño $r$ y sin consecutivos?
Solución biyectiva ("descubierta" con el método regula falsi)
Sin restricciones serían $C(n,r)$. Pero algunos de esos subconjuntos tienen consecutivos. Sea $B = \{b_1,b_2,...,b_r\}$ un subconjunto de $S$ de tamaño $r$. Por ejemplo, si fuese $B = \{1,2,...,r\}$, lo podríamos convertir a $ \{1,3,5,...\}$ --que no tiene consecutivos--, lo cual equivale a dejar el primero igual, sumarle 1 al segundo, 2 al tercero, etc.
Esto sugiere la transformación $b_i \to b_i+i-1$, lo cual aseguraría que no hay consecutivos. El único problema es que se logra un subconjunto tamaño r sin consecutivos !pero de $ \{1,2,...,n+r-1\} $ !
¿La gran idea ha fracasado? Pues depende del significado de fracaso. La idea es buena a pesar de que fracasó. Porque la solución obtenida puede ser ajustada (reciclada). Como en el método de regula falsi, la podemos ajustar de la siguiente manera. Puesto que me sobran r-1 en el rango, pues puedo empezar con un conjunto modificado $S'$, eliminando los últimos $r - 1$ elementos de $S$. Es decir, podemos tomar los subconjuntos de tamaño $r$ de $S' = \{1,2,...,n-r+1\}$. Y ya está. La respuesta es entonces $C(n+r-1,r)$. Los detalles al lector.
Ejercicio: establecer una biyección entre los subconjuntos tamaño $r$ de $S' = \{1, 2,...,n+r-1\}$ y los subconjuntos tamaño r sin consecutivos de $S = \{1, 2,...,n\}$.
Los saluda
jmd
PD:
El regula falsi (falsa posición) --en su forma original del Papiro Rhind-- resuelve una ecuación adivinando primero una solución y después ajustándola de acuerdo al resultado del primer intento. En este sentido, el regula falsi aprende del error --mejor dicho: toma ventaja del error. Un ejemplo: $x+x/4=15$. Si $x$ fuese $4$ (la forma fácil para no manejar quebrados) se tendría $4+4/4=5$. Pero queríamos 15 (que es 3 por 5). Por tanto ajusto la solución a $x=3(4)=12$. Ver el sitio http://www.egiptologia.org/ciencia/matematicas/papiro_rhind.htm [1]