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 y : poniendo los subconjuntos de tres consecutivos en orden lexicográfico se ve que son 18  ().
Cardinalidad de : escogemos los dos mayores de 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 es

Solución alternativa

Ordenando previamente sus elementos, cada subconjunto de tamaño 3 de   se puede transformar en una tripleta (a,b-1,c-2) con elementos, en orden no decreciente y posiblemente repetidos, del conjunto ; 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 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 y sin consectivos de )

Después de ordenar sus elementos, cada k-subconjunto de se puede transformar en una k-ordenación --con elementos en orden no decreciente y repeticiones permitidas-- de ; 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   es