2014 dxdy logo

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

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




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

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

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

 
 
 
 Re: Вероятность и комбинаторика.
Сообщение09.12.2012, 13:41 
количество беспорядков

 
 
 
 Re: Вероятность и комбинаторика.
Сообщение09.12.2012, 14:12 
Аватара пользователя
Можно посчитать формулой включений-исключений $$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$ переходит в себя

 
 
 
 Re: Вероятность и комбинаторика.
Сообщение09.12.2012, 14:38 
Аватара пользователя
max(Im) в сообщении #656144 писал(а):
Какова вероятность того, что случайная перестановка из $S_n$ не содержит петли в своем графе? Ну то есть нет элемента, который переходит сам в себя..
.............................
тот, в который перешел этот - не в те, в которые уже переходили.

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

 
 
 [ Сообщений: 4 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group