Задача по дискр. матем.

[Tatyana_math]

Найти число подстановок степени n, имеющих ровно k единичных циклов.

Я решала так: 1. сочетание из n по к
$\left(\begin{array}{c} n \\ k \end{array} \right) $ - это число нужных нам подстановок, если не учитывать порядок оставшихся $(n-k)$ элементов.
2. Осталось найти число подстановок степени $(n-k)$, cостоящих из одного цикла длины $(n-k)$ и умножить на сочетание $\left(\begin{array}{c} n \\ k \end{array} \right) $

Число всех перестановок оставшихся $(n-k)$ элементов равно $(n-k)!$
Из него вычитаем все подстановки, имеющие более одного цикла
$\sum\limits_{m=1}^{n-k}\left(\begin{array}{c} n-k \\ m\end{array} \right) $

В итоге получила решение:
$\left(\begin{array}{c} n \\ k \end{array} \right) $ $((n-k)!-\sum\limits_{m=1}^{n-k}\left(\begin{array}{c} n-k \\ m \end{array} \right)) $

где я ошиблась? задачу не зачли.

[patzer2097]

Ошиблись вот тут:

Tatyana_math в сообщении #805293 писал(а):

2. Осталось найти число подстановок степени $(n-k)$, cостоящих из одного цикла

На самом деле, осталось найти число "беспорядков" степени $n-k$, т.е., перестановок, которые ни один из элементов не оставляют на месте. А это стандартная задача на формулу включений-исключений: нужно найти с ее помощью число элементов множества $\bigcup_{i=1}^t F_i$ и применить полученный результат к (тривиально получаемому) равенству

$$B_t=S_t\setminus\left(\bigcup_{i=1}^t F_i\right),$$

где $B_t$ -- множество беспорядков степени $t$,
$S_t$ -- множество всех перестановок степени $t$, а
$F_i$ -- множество тех перестановок $\sigma\in S_t$, для которых $\sigma(i)=i$.

Кстати, в задаче о беспорядках ответ красивый получается. Порадуемся ему вместе, если все получится

[Tatyana_math]

помогите пожалуйста разобраться до конца.
множество всех перестановок степени t: в нашем случае степени $(n-k)$ будет равно $(n-k)!$
А как в формуле, которую вы привели найти объединение $F_i$?

или то что нам нужно это просто $\sum^{\infty}_{k=0} \frac {(-1)^k}{k!}={e^{-1}} ,
то что до знака = , и в пределе до n-k ?

[Tatyana_math]

задачу решила.

[patzer2097]

Tatyana_math в сообщении #806663 писал(а):

или то что нам нужно это просто $\sum^{\infty}_{k=0} \frac {(-1)^k}{k!}={e^{-1}} ,
то что до знака = , и в пределе до n-k ?

ну прямо $e^{-1}$ не может получиться, - это число иррациональное.. да еще и меньше $1$.. напишите решение подробнее, если хотите, чтобы кто-то ответил по существу

(Оффтоп)

Tatyana_math в сообщении #806889 писал(а):

задачу решила.

а не хотите - как хотите

[--mS--]

(Про ТеХ)

Биномиальные коэффициенты набираются так: $\binom{n}{k}$

\binom{n}{k}