Изменения

Рассмотрим алгоритм получения случайного битового вектора. В битовом векторе может находиться только два типа элементов: <tex> 0 </tex> и <tex> 1 </tex>, следовательно <tex> k = 2 </tex>. Заметим что для любого префикса длины <tex> l </tex> число возможных комбинаторных объектов одинаково и равно, следовательно на каждм каждом шаге алгоритма небходмо выбирать с равной вероятностью <tex> 0 </tex> или <tex> 1 </tex>

Сложность алгоритма {{---}} <tex>O(n) </tex>, так как в случае двоичных векторов <tex> k </tex> постоянно и равно <tex> 2 </tex>. == Правильные скобочные последовательности ==Рассмотрим алгоритм получения случайной правильной скобочной последовательности. Правильная скобочная пследовательность состоит из двух типов элементов: открывающей и закрывающей скобок, следовательно <tex> k = 2 </tex>.  Рассмотрим "полуправильные" скобочные последовательности т.е. такие что всякой закрывающей скобке соответствует парная открывающая, но не все открытые скобки закрыты. Такую последовтеьность можно охарактеризовать двумя числами: <tex> l </tex> — длина скобочной последовательности и <tex> b </tex> — баланс (т.е. разность между количеством открывающих и закрывающих скобок). Заметим что любой префикс правильной скобочной последовательности является "полупраильной" скобочной последовательностью, и что для любого префикса <tex> P </tex> длины <tex> l </tex> число различных ПСП длины <tex> n </tex> равно числу "полуправильных" скобочных последовательностей длины <tex> n-l </tex> с таким же балансом как у <tex> P </tex>. Научимся считать <tex> number(l, b) </tex> {{---}} число последовательностей длины <tex> l </tex> и баланса <tex> b </tex>).