Subconjuntos sin consecutivos

Los subconjuntos con dos elementos consecutivos se pueden clasificar en los que tienen dos elementos consecutivos al principio (los dos menores son consecutivos) y los subconjuntos que tienen los dos elementos consecutivos al final. Sean A y B, respectivamente, tales clases.

Pero estas clases no son disjuntas, pues hay subconjuntos que tienen los tres elementos consecutivos. Entonces, vamos a calcular el número de subconjuntos con dos consecutivos como la cardinalidad de A más la cardinalidad de B menos la de la intersección (pues los de 3 consecutivos se contaron dos veces).

Cardinalidad de la intersección de $A$ y $B$: poniendo los subconjuntos de tres consecutivos en orden lexicográfico se ve que son 18  ($123,234,\ldots,181920$).
Cardinalidad de $A$: escogemos los dos mayores de $\{2,3,\ldots,20\}$ y el tercero es único --es el anterior al menor--, por lo tanto hay C(19,2).
Cardinalidad de B: un argumento similar pone en evidencia que hay C(19,2) subconjuntos de ese tipo.

En resumen, el número de subconjuntos de tamaño 3 de $\{1,2,\ldots,20\}$ es $C(20,3)-2C(19,2)+18=C(20,3)-18^2$

Solución alternativa

Ordenando previamente sus elementos, cada subconjunto $\{a,b,c\}$ de tamaño 3 de $\{1,2,\ldots,20\}$  se puede transformar en una tripleta (a,b-1,c-2) con elementos, en orden no decreciente y posiblemente repetidos, del conjunto $\{1,2,\ldots,18\}$; y la transformación es reversible.

Esto establece una biyección entre los subconjuntos y las tripletas. Y un subconjunto carece de elementos consecutivos si y sólo si en la tripleta correspondiente todos sus componentes son diferentes. De aquí que el número de subconjuntos de tamaño 3 y sin consecutivos de $\{1,2,\ldots,20\}$ es C(18,3) --elijo la tripleta y
le aplico la transformación inversa para obtener el subconjunto sin consecutivos.

Generalización

(Subconjuntos de tamaño $k$ y sin consectivos de $\{1,2,\ldots,n\}$)

Después de ordenar sus elementos, cada k-subconjunto $\{a,b,c,\ldots\}$ de $\{1,2,\ldots,n\}$ se puede transformar en una k-ordenación $(a,b-1,c-2,\ldots)$ --con elementos en orden no decreciente y repeticiones permitidas-- de $\{1,2,\ldots,n-k+1\}$; y la transformación es reversible.

Además, un k-subconjunto carece de consecutivos si y sólo si los elementos de la k-ordenación correspondiente están en orden creciente. Por tanto, el número de k-subconjuntos de sin consectivos de $\{1,2,\ldots,n\}$  es $C(n-k+1,k).$