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={b1,b2,...,br} 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={b1,b2,...,br} 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 bi→bi+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