Перестановки и циклы

[marie-la]

Задача про перестановки.
Найти количество перестановок $n$ элементов, в которых $k$ фиксированных элементов принадлежат одному циклу.
Я записала в виде суммы по длине цикла от $k$ до $n$, но подозреваю, что формула должна быть без суммы. Если не ошиблась, сводится к подсчету
$\sum\limits_{i=k}^{n}$C_{i-1}^{k-1}$

[nnosipov]

Безотносительно к тому, правилен ответ или нет: такая сумма действительно сворачивается.

[marie-la]

nnosipov
О, поняла, количество решений уравнения типа
$x_1+x_2+...+x_{k+1}=n-k$
Получается что-то типа $C_{n}^{k}$
Поняла, как делать, спасибо!

[nnosipov]

marie-la в сообщении #1490444 писал(а):

Получается что-то типа $C_{n+k-1}^{k}$

Я на всякий случай напишу, чему равна Ваша сумма:

$$\sum_{i=k}^n C_{i-1}^{k-1}=\frac{n-k+1}{k}\,C_n^{k-1}.$$

[marie-la]

nnosipov
Спасибо, буду проверять у себя.

PS Ответ у нас с вами одинаковый :)

[nnosipov]

marie-la в сообщении #1490435 писал(а):

Найти количество перестановок $n$ элементов, в которых $k$ фиксированных элементов принадлежат одному циклу.

Если я правильно понял условие задачи, то ответ $n!/k$. Что-то это непохоже на Вашу сумму.

[Odysseus]

А не $(n-k)!k$ ?
$k$ элементов фиксированы и переставляются только внутри своего цикла, т.е. всего $k$ перестановок, а остальные $(n-k)$ элементов независимо переставляются как угодно вне этого цикла.
В данном случае - если я правильно понял условие задачи...

[nnosipov]

Odysseus
Что должно получиться при $k=1$?

[Odysseus]

nnosipov $(n-1)!$, но, опять же, для меня условие задачи звучит как то, что $k$ элементов из цикла не переставляются с остальными элементами, а только переставляются внутри своего цикла, поэтому они в задаче и называются "фиксированными".

[nnosipov]

Odysseus в сообщении #1490454 писал(а):

что $k$ элементов из цикла не переставляются с остальными элементами, а только переставляются внутри своего цикла

Вот эту фразу я не понимаю.

На мой взгляд, речь идет вот о чем. Из множества $\Omega_n=\{1,2,\dots,n\}$ выбрали некоторые $k$ элементов, например элементы $1,2,\dots,k$. Далее рассматриваем произвольную перестановку $\alpha: \Omega_n \to \Omega_n$, раскладываем ее в произведение независимых циклов и, наконец, если все наши выбранные элементы попали в тело одного из этих циклов, то мы такую перестановку $\alpha$ отмечаем. Вопрос в том, сколько будет отмеченных перестановок. Ответ $n!/k$.

[Odysseus]

Я условие задачи понял как то, что выбранные $k$ элементов принадлежат циклу длины $k$, но, видимо, это неверно. Такого ограничения в условии в самом деле нет.

[nnosipov]

Odysseus в сообщении #1490459 писал(а):

выбранные $k$ элементов принадлежат циклу длины $k$

Ну а что, тоже вполне содержательный вопрос (сколько таких перестановок). Но тогда получается $(k-1)!(n-k)!$. (Потому что разных циклов с данным телом длины $k$ имеется $(k-1)!$.)

[Someone]

nnosipov в сообщении #1490462 писал(а):

разных циклов с данным телом длины $k$ имеется $(k-1)!$.

Циклов-то да, но перестановок всё-таки $k!$, а спрашивают не про циклы, а про перестановки.

[nnosipov]

Someone в сообщении #1490468 писал(а):

а спрашивают не про циклы, а про перестановки

А что такое перестановка? Здесь может быть проблема в терминологии. Для меня перестановка в данном топике --- это биекция множества $\Omega_n$ (хотя, честно говоря, я обычно в этом контексте использую термин "подстановка").

Вообще, любые вопросы такого сорта лучше задавать максимально подробно, во избежание разных трактовок.

[Someone]

nnosipov в сообщении #1490469 писал(а):

Для меня перестановка в данном топике --- это биекция множества $\Omega_n$

Да, Вы правы. Если цикл содержит больше одного элемента, то никакой элемент этого цикла не может отображаться в себя, иначе не будет цикла нужной длины. Поэтому $(k-1)!$.

Но всё равно есть некоторая неясность: нужно ли считать, что в цикл входят только указанные $k$ элементов, или же могут быть и другие? Формулировка

marie-la в сообщении #1490435 писал(а):

$k$ фиксированных элементов принадлежат одному циклу

интерпретируется скорее во втором смысле, нежели в первом.