Короткие ответы:

Без запрета: число непустых подмножеств множества из (n) элементов равно (\;2^n-1\;).С запретом соседних по круговой нумерации (независимые множества графа (C_n), кроме пустого): их число равно (\;Ln-1 = F{n-1}+F_{n+1}-1\;), где (F_k) — числа Фибоначчи ((F_0=0,F_1=1)), а (L_n) — число Люка.

Три подхода (кратко и по существу).

1) Через биномиальные коэффициенты (подсчёт по мощности)

Для линейного ряда из (n) вершин число (k)-элементных множеств без соседних элементов равно
(\displaystyle \binom{n-k+1}{k}).Для круговой нумерации: фиксируем (k\ge1). Количество (k)-множеств без соседних элементов на цикле (Cn) даётся формулой
(\displaystyle \frac{n}{\,n-k\,}\binom{n-k}{k}\quad(1\le k\le\lfloor n/2\rfloor)).
Суммируя по (k\ge1), получаем общее число непустых допустимых множеств:
(\displaystyle \sum{k=1}^{\lfloor n/2\rfloor}\frac{n}{\,n-k\,}\binom{n-k}{k}=L_n-1.)
(Вывод: распределение «зазоров» между выбранными вершинами даёт указанную формулу.)

2) Через рекуррентные соотношения (Фибоначчи / Люк)

Пусть (a_n) — число независимых множеств (включая пустое) на пути (линейный список) из (n) вершин. Разделение по тому, выбрана ли последняя вершина, даёт
(\displaystyle an=a{n-1}+a_{n-2},\quad a_0=1,a_1=2,)
откуда (an=F{n+2}).Для цикла (bn) (включая пустое): если вершина 1 не выбрана — остаётся путь из (n-1) вершин ((a{n-1}) вариантов); если выбрана — исключаются её соседи и остаётся путь из (n-3) вершин ((a_{n-3}) вариантов). Значит
(\displaystyle bn=a{n-1}+a{n-3}=F{n+1}+F_{n-1}=L_n.)
Вычитаем пустое множество: непустых — (\;L_n-1\;.)

3) Через биективные соответствия (комбинаторная интерпретация)

Представим подмножество как бинарную строку длины (n) с единицами в выбранных позициях; запрет соседних по кругу единиц — это условие «никаких соседних единиц по циклу». Таким образом задача эквивалентна подсчёту циклических двоичных слов без соседних единиц.Биекции:
Удаление одной фиксированной вершины переводит задачу на цикле в задачу на пути (линейную), что даёт связь с (a_{n-1}) и рекуррентом.Разбиение на (k) выбранных единиц и (n-k) нулей с условием, что между единицами хотя бы один ноль, сводится к звёздно-полосной (stars-and-bars) задаче на круге и ведёт к формуле (\frac{n}{n-k}\binom{n-k}{k}).
Эти биекции очевидно показывают эквивалентность формул с рекуррентами и суммами биномиальных коэффициентов и приводят к выражению через числа Фибоначчи/Люка.

Если нужно, могу привести вывод формулы (\frac{n}{n-k}\binom{n-k}{k}) подробно или развернуть рекуррентные выкладки.