== Доказательство корректности ==
Докажем, что с помощью данного алгоритма действительно можно получать случайный комбинаторный размера <tex> n </tex>, причем вероятность получения одинакова для каждого результата.
{{Лемма
|statement=Вероятность получить в процессе работы алгоритма некоторый перфикс <tex> P </tex> равна <tex> S(P)\over{C(n)} </tex>, где <tex> C(n) </tex> {{---}} число различных комбинаторных объектов данного типа длины <tex> n </tex>, а <tex> S(P) </tex> {{---}} число различных комбинаторных обьектов длины <tex> n </tex> с таким префиксом.
}}
Результат {{Утверждение|statement=Результатом работы данного алгоритма является префиксом случайный комбинаторный объект размера <tex> n </tex> , а причем вероятность получения одинакова для любого такого префикса существует только один комбинаторный объект каждого результата.|proof=Заметим, что результатом работы данного алгоритма является любой из возможных префиксов размера <tex> n </tex>. Любой такой префикс является комбинаторным объектом размера <tex> n </tex> {{---}} совпадающий и наоборот, следовательно число объектов с этим таким префиксом (т.е. равно <tex> S(result)=1 </tex>). Из чего по доказанной лемме следует, что вероятность получения одинакова для всех различных результатов и равна <tex> 1\over{C(n)} </tex>.}}
== Примеры решения задач ==
