COM-B1-M01-P024 Перестановки без соседних последовательных чисел

Используйте включение-исключение по запрещённым соседствам \(\{1,2\},\{2,3\},\ldots,\{7,8\}\).

Рассмотрим \(7\) возможных запрещённых соседств. Если выбраны \(k\) соседств, они образуют \(c\) блоков подряд идущих рёбер в цепочке. Такие \(k\) рёбер можно выбрать \(C(k-1,c-1)C(8-k,c)\) способами. Каждый блок можно ориентировать \(2\) способами, значит ориентаций \(2^c\), а после склейки остаётся \(8-k\) объектов, которые можно переставить \((8-k)!\) способами. По включению-исключению получаем сумму \(40320-70560+51840-20400+4608-612+48-2=5242\).

Сильная challenge-задача; можно оставить как задачу для лучших учеников.