Соответствия, сравнения, количества

Обозначим за количество -элементных неизолированных подмножеств множества Вычислим зная Рассмотрим произвольное подмножество множества Если оно не содержит число то значит мы его посчитали уже в Поэтому, рассмотрим которое содержит число По условию оно также должно содержать число Далее рассмотрим два случая, первый если а второй если В первом случае, оставшиеся числа множества должны быть вида и где — натуральное число, которое меньше, чем Следовательно, в первом случае количество таких множеств равно Во втором же случае мы получим, что оставшиеся числа множества будут иметь вид: где — натуральное число, которое меньше Поэтому в этом случаем количество множеств получается равно Откуда следует, что для Заметим, что Следовательно,

Это можно преобразовать используя формулу суммы чисел от до в такое: