Изменения

Докажем по индукции, что вероятность получить любой перфикс <tex> P </tex> равна <tex> CS(nP)\over{SC(Pn)} </tex>, где <tex> C(n) </tex> - число различных комбинаторных данного типа длины <tex> n </tex>, а <tex> S(P) </tex> - число различных комбинаторных обьектов с таким префиксом.*Любой комбинаторный объеут имеет пустой перфикс, следовательно <tex> S(\varnothing)=C(n) </tex>. Вероятность получить любой префикс <tex> P </tex> длины <tex> 1 </tex> равна <tex> S(\varnothingP)\over{S(P\varnothing)} </tex>, что равно <tex> CS(nP)\over{SC(Pn)} </tex>.*Пусть вероятность получить префикс <tex> P </tex> длины <tex> l </tex> равна <tex> CS(nP)\over{SC(Pn)} </tex>*Тогда вероятность получить из <tex> P </tex> любой префикс <tex> P' </tex> длины <tex> l+1 </tex> равна <tex> CS(nP)\over{SC(Pn)} </tex><tex>\cdot</tex><tex> S(P')\over{S(P')} </tex> , что равно <tex> S(P')\over{C(n)} </tex>Результат работы алгоритма является префиксом <tex> P </tex> размера <tex> n </tex> и для любого такого префикса существует только один комбинаторный объект размера размера <tex> n </tex> , следовательно вероятность получения одинакова для всех различных результатов и равна <tex> 1\over{SC(P'n)} </tex>.