Перед сценой полукругом расположены 33 мягких кресла для VIP-персон. На концерт пришло только 16 VIP-персон, и они пожелали рассесться так, чтобы у каждого не оказалось рядом занятого кресла. Сколькими способами они могут занять места? (Важно, какие места заняты, но неважно, кто именно там сидит.)

Поскольку кресла расположены полукругом, считаем их как обычный ряд из 33 мест: у каждого кресла есть сосед слева и справа, кроме двух крайних.

Нужно выбрать 16 кресел из 33 так, чтобы никакие два выбранных кресла не стояли рядом.

Представим сначала, что 16 VIP-персон уже заняли какие-то кресла. Чтобы между любыми двумя занятыми креслами было хотя бы одно свободное, минимально нужна такая схема:

Между 16 занятыми креслами должно быть 15 обязательных свободных кресел.

То есть минимально для такой рассадки нужно:

кресло.

Всего кресел 33, значит остаётся ещё:

свободных кресла, которые можно распределить по промежуткам:

• перед первым занятым креслом;

• между занятыми креслами дополнительно к уже обязательным свободным;

• после последнего занятого кресла.

Таких промежутков всего:

Нужно распределить 2 одинаковых свободных кресла по 17 промежуткам. Число способов равно числу решений уравнения

в неотрицательных целых числах. По формуле сочетаний с повторениями:

Значит, VIP-персоны могут занять места 153 способами.