Вероятность и комбинаторика.

[max(Im)]

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

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

Как это правильно делать?

[mihailm]

количество беспорядков

[Whitaker]

Можно посчитать формулой включений-исключений

$$N(\bar{a}_1\bar{a}_2\dots \bar{a}_n)=N-N(a_1)-\dots-N(a_n)+N(a_1a_2)+\dots+N(a_{n-1}a_n)-\dots+(-1)^nN(a_1a_2\dots a_n), $$

где $N(\bar{a}_1\bar{a}_2\dots \bar{a}_n)$ - количество объектов, не обладающие свойствами $a_1, \dots, a_n$
$N$ - общее число, $N(a_ia_j\dots a_k)$ - количество предметов, обладающие свойствами $a_i,a_j,\dots, a_k$ одновременно

(Оффтоп)

В Вашем случае свойства $a_i$: элемент $i$ переходит в себя

[TOTAL]

max(Im) в сообщении #656144 писал(а):

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

Уточните, вероятность чего ищете.