Ответ: для n-угольника $n\ge 6$ количество способов выбрать 3 вершины, никакие две из которых не смежны, равно
N = n$n-4$$n-5$ / 6.
(При n < 6 таких троек нет, при n = 6 получаем 2, при n = 7 — 7 и т. д.)

Доказательства несколькими способами.

1) Прямой подсчёт через «щели» $stars-and-barsнакруге$

Расположим по часовой три выбранные вершины; между ними по кругу находятся три промежутка из непомеченных вершин. Если никакие две выбранные не смежны, то в каждом промежутке должно быть ≥1 непомеченной вершины.Пусть a, b, c ≥ 1 и a + b + c = n − 3. Число упорядоченных троек $a,b,c$ — число положительных решений = C$n-4,2$.Зафиксируем одну выбранную вершину как «первая»: для каждой из n возможных позиций этой вершины и для каждой упорядоченной тройки промежутков получаем упорядоченное расположение трёх вершин. Итого упорядоченных циклически троек = n·C$n-4,2$.Каждая $неупорядоченная$ тройка вершин даётся в таком порядке ровно 3 раза $в3-хциклическихначальныхточках$, значит искомое число
N = n·C$n-4,2$/3 = n·$n-4$$n-5$/6.

2) Включения–исключения $черездополнение«естьсмежнаяпара»$

Всего троек вершины C$n,3$.Пусть A_i — событие, что пара $i,i+1$ $покругу$ обе выбраны. Число троек, содержащих заданную смежную пару, равно n−2 $третьювершинуможновыбратьизостальныхn-2$. Сумма по всем парам: S1 = n·$n-2$.Пересечение двух таких событий возможно только если выбираются три подряд идущие вершины $i,i+1,i+2$; таких троек ровно n, поэтому S2 = n. Более высоких пересечений нет.По формуле включений–исключений число троек, содержащих хотя бы одну смежную пару, = S1 − S2 = n$n-3$.Значит желаемое N = C$n,3$ − n$n-3$ = n$n-4$$n-5$/6.

3) Комбинаторика «со сдвигами» / общий метод

Более общая формула для выбора k непоследовательных вершин на круге: число = n/$n-k$ · C$n-k,k$ $приn\ge 2k$. Для k = 3 это даёт n/$n-3$ · C$n-3,3$ = n$n-4$$n-5$/6.Короткое доказательство: посчитать упорядоченные по кругу k-ки $фиксацияпервойвершиныираспределениеn-kневыбранныхвkпромежутковс\ge 1$ и разделить на k. Это обобщение пункта $1$.

Сравнение подходов по «сложности»

Прямой подход через разбиения $1$ даёт быстрый и понятный вывод, небольшая комбинаторная обработка $stars-and-bars$, легко обобщается на произвольное k. По информативности и компактности — предпочтителен.Включения–исключения $2$ интуитивно прост для k = 3 $нужнорассмотретьтолькоодно-идвухкратныепересечения$, но при увеличении k количество членов в сумме растёт и метод становится громоздким. Для общего k требуется учитывать до k-чинных пересечений, что делает метод менее удобным.Метод со сдвигами / ориентацией $3$ — это та же идея, что и $1$, но оформленная в другом виде; даёт удобную общую формулу n/$n-k$·C$n-k,k$. Для алгоритмического вычисления всех значений для разных k он проще и даёт закрытую форму.

Вывод: для трёх вершин наиболее кратки и естественны метод «щелей» и общий сдвиговый метод; включения–исключения полезны для проверки и интуиции, но громоздки при обобщениях.