ReAl (16.11.2008 01:43, просмотров: 174) ответил Evgeny_CD на Да, именно - каждая возможная комбинация, в которой два нуля идут подряд (для примера из 5 бит), причем сколько раз такая пара встречается - не важно.
Так это как раз первый вариант, который "не соображу". Во! Второй вариант - это "сколько раз встретятся последовательности в точности N одинаковых бит подряд (т.е. обрамлённые противоположными значениями либо краем последовательности) во всех возможных комбинациях из M бит" (я дал разные буквы, так как мне тяжело соображать, когда полная длина задана маленькой буквой, а подпоследовательность - большой :-) ).
Пусть M - общее число бит, N - длина одинаковых. N < M (в смысле для N = M окончательная формула неприменима)
Варианты:
подпоследовательность касается краем края последовательности.
Тогда число возможных комбинаций остального
2M-N-1 (так как ещё один бит кроме этих N жёстко задан - он противоположный). Краёв у последовательности два, поэтому вместе 2*2M-N-1 = 2M-N
подпоследовательность не касается края.
Тогда жёстко прибиты на противоположное значение два обрамляющих бита. У остального 2M-N-2 возможных вариантов и подпоследовательность может занимать (M-N-1) возможную позицию. Итого (M-N-1)*2M-N-2
Оба варианта суммируем и умножаем на число возможных значений символа (бита, т.е.2)
2*(2M-N+(M-N-1)*2M-N-2) = 2M-N+1+(M-N-1)*2M-N-1
Но это именно число возможных подпоследовательностей во всём наборе последовательностей, т.е.
сочетание 00100 даст два в копилку. 11011 - ещё два.
Если не глючу. Пора спать...
("если я не глючу" - это по поводу правильности формулы для данного варианта)
(а вот на первый, собственно интересующий вариант - сейчас не соображу... а завтра врядли дадут...)