Изменения
Нет описания правки
: при <tex> i = k </tex>:
: <tex> a[\;] = \langle a_{1}, a_{2}, ..., a_{k-1}, k, ... \rangle </tex>
: после swap(i, random(1..i)) вероятность какого-то числа оказаться на k-ом месте равна <tex>\frac{1}{k}</tex>, вероятность . Вероятность же какой-то перестановки первых (k-1) элементов при известном <tex>a_{k}</tex> останется <tex> \frac {1}{(k-1)!}</tex>, что в результате дает, что вероятность перестановки первых k элементов равна <tex> \frac {1}{k!}</tex>
<br/>
Другой способ обоснования заключается в том, что каждая перестановка в результате работы этого алгоритма может получиться ровно одним способом, причем всегда ровно за <tex> n </tex> шагов, таким образом автоматически получается, что все <tex> n!</tex> перестановок равновероятны.<br/>
