Сколько существует перестановок из

различных элементов, в которых никакие три из заданных

элементов

не стоят рядом?
Этот вариант можно решить аналогичным образом, используя композиции с ограничениями. Количество вариантов размещений заданных

элементов в группах по 1 или 2 элемента равно количеству композиций числа

, части которых не превышают значения

.
При нахождении числа композиций с ограничениями будем опираться на сходу найденную
статью 1976 г. "Restricted Combinations and Compositions" автора Morton Abramson. С некоторыми переобозначениями формула для числа композиций с ограничениями из этой статьи (см. с. 441, формула E) выглядит так:

Здесь

— количество композиций числа

длины

, части которых не превышают

. В статье принято, что

Для случая

приводится также следующая упрощенная формула:

В данном случае нам нужно разместить оставшиеся

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

, оно равно

. Тогда искомое число перестановок при

будет равно

Не знаю, можно ли упростить эту формулу.
В общем случае (для произвольного

, что соответствует условию
"никакие
из заданных
элементов
не стоят рядом") для искомого числа перестановок получается такая формула:

Здесь подразумевается, что

(

— особый тривиальный случай, при любом

искомое число перестановок для него будет равно

).