Перестановки с ограничениями

[SomePupil]

Комбинаторные задачи.

Сколько существует перестановок из $n$ различных элементов, в которых никакие два из заданных $k$ элементов $e_1, \ldots, e_k$ не стоят рядом?

Сколько существует перестановок из $n$ различных элементов, в которых никакие три из заданных $k$ элементов $e_1, \ldots, e_k$ не стоят рядом?

Баян?

[eugensk]

Если обозначить это число как $S^k_n$,
то для 1-ой задачи (никакие 2 из k выделенных не стоят рядом):

\align{S^k_n=(n-k)S^k_{n-1}+k(n-k)S^{k-1}_{n-2}}

\align{S^1_1=1, S^0_1=1, S^0_0=1}

Для второй задачи в том же духе, с 3-мя слагаемыми. Как найти замкнутую формулу, не знаю.

[EtCetera]

SomePupil в сообщении #1286808 писал(а):

Сколько существует перестановок из $n$ различных элементов, в которых никакие два из заданных $k$ элементов $e_1, \ldots, e_k$ не стоят рядом?

Через число композиций вроде бы довольно легко считается. Обозначим $m=n-k$ — число элементов, которые нужно разместить так, чтобы между соседними заданными элементами всегда был по меньшей мере один элемент. Количество таких способов размещения равно

$$\binom{m-1}{k-2}+2\binom{m-1}{k-1}+\binom{m-1}{k}=\binom{m+1}{k}$$

Искомое число перестановок равно

$$\binom{m+1}{k}m!k!=\frac{m!(m+1)!}{(m+1-k)!}=\frac{(n-k)!(n+1-k)!}{(n+1-2k)!}\qquad(1)$$

Рекуррентной формуле eugensk этот результат, кажется, соответствует.

[EtCetera]

SomePupil в сообщении #1286808 писал(а):

Сколько существует перестановок из $n$ различных элементов, в которых никакие три из заданных $k$ элементов $e_1, \ldots, e_k$ не стоят рядом?

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

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

$$C(k,\ell, w)=\sum_{j=0}^{\ell}(-1)^j\binom{\ell}{j}\binom{k-jw-1}{\ell-1}$$

Здесь $C(k,\ell, w)$ — количество композиций числа $k$ длины $\ell$, части которых не превышают $w$. В статье принято, что

$$\binom{n}{k}=\begin{cases}\frac{n!}{k!(n-k)!},& \text{если}\ 0\le k\le n\\0, &\text{иначе}\end{cases}$$

Для случая $w=2$ приводится также следующая упрощенная формула:

$$C(k,\ell,2)=\binom{\ell}{k-\ell}$$

В данном случае нам нужно разместить оставшиеся $m=n-k$ элементов так, чтобы между соседними группами из заданных элементов всегда был по меньшей мере один элемент. Количество таких способов было уже посчитано для случая $w=1$, оно равно $\binom{m+1}{\ell}$. Тогда искомое число перестановок при $w=2$ будет равно

$$m!k!\sum_{\ell=\left\lceil\frac{k}{2}\right\rceil}^k \binom{m+1}{\ell}\binom{\ell}{k-\ell}=(n-k)!k!\sum_{\ell=\left\lceil\frac{k}{2}\right\rceil}^k \binom{n+1-k}{\ell}\binom{\ell}{k-\ell}$$

Не знаю, можно ли упростить эту формулу.

В общем случае (для произвольного $w>0$, что соответствует условию "никакие $w+1$ из заданных $k$ элементов $e_1, \ldots, e_k$ не стоят рядом") для искомого числа перестановок получается такая формула:

$$(n-k)!k!\sum_{\ell=\left\lceil\frac{k}{w}\right\rceil}^k \binom{n+1-k}{\ell}\sum_{j=0}^{\ell}(-1)^j\binom{\ell}{j}\binom{k-jw-1}{\ell-1}$$

Здесь подразумевается, что $k>0$ ($k=0$ — особый тривиальный случай, при любом $w$ искомое число перестановок для него будет равно $n!$).