2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Перестановки с ограничениями
Сообщение23.01.2018, 15:25 
Аватара пользователя


07/01/15
1145
Комбинаторные задачи.

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

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

Баян?

 Профиль  
                  
 
 Re: Перестановки с ограничениями
Сообщение23.01.2018, 15:49 
Аватара пользователя


14/12/17
1471
деревня Инет-Кельмында
Если обозначить это число как $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-мя слагаемыми. Как найти замкнутую формулу, не знаю.

 Профиль  
                  
 
 Re: Перестановки с ограничениями
Сообщение23.01.2018, 17:27 
Заслуженный участник


28/04/09
1933
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 этот результат, кажется, соответствует.

 Профиль  
                  
 
 Re: Перестановки с ограничениями
Сообщение24.01.2018, 00:06 
Заслуженный участник


28/04/09
1933
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!$).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group