caxapa.ru :: Какой формулой из комбинаторики это считается?

Evgeny_CD^{Архитектор} (16.11.2008 00:40, просмотров: 5960)

Какой формулой из комбинаторики это считается? Есть последовательность n бит. Всего 2^n комбинаций. Выбираем комбинации, такие, чтобы число подряд идущих одинаковых бит (0 или 1) было равно N. Как аналитически подсчитать число таких комбинаций?

- Вот как это выглядит для n=5 Evgeny_CD(508 знак., 16.11.2008 01:36)
- Ваще в последнее время как-то странно. Я никогда математику не понимал и не любил. Читал книги по теории кодирования - но как об стену горох. А тут что-то перемкнуло - и многое стало проясняться, что я долгие годы понять не мог. - Evgeny_CD(16.11.2008 01:15)
- Если "подряд N" означает "подряд N или больше", то имхо 2^(n-N)*2*(n-N+1) ... хотя уже начал сомневаться :) - diper(16.11.2008 01:10)
  - Можно и так - N или больше. Но формула что-то не того Evgeny_CD(86 знак., 16.11.2008 01:13)
    - Да дейстивтельно косяк. Рассуждения для n=6 и n=N такие: diper(613 знак., 16.11.2008 02:08)
- А для пяти бит и длине два - 00100 - это "одна комбинация" или "два нуля подряд встретилось два раза". Если второе (т.е. каждая возможная комбинация из подряд идущих бит представляет самостоятельную ценность), то вроде несложно. А если "сколько ReAl(123 знак., 16.11.2008 01:05)
  - Да, именно - каждая возможная комбинация, в которой два нуля идут подряд (для примера из 5 бит), причем сколько раз такая пара встречается - не важно. - Evgeny_CD(16.11.2008 01:10)
    - Так это как раз первый вариант, который "не соображу". Во! Второй вариант - это "сколько раз встретятся последовательности в точности N одинаковых бит подряд (т.е. обрамлённые противоположными значениями либо краем последовательности) во всех ReAl(1400 знак., 16.11.2008 01:43)
      - Считаем Evgeny_CD(269 знак., 16.11.2008 01:44, ссылка)
        
        Ещё раз - я, увы, о другой задаче, просто плохо объясняю о какой. И погрешности нет, теория с практикой совпадает. ReAl(792 знак., 16.11.2008 09:48)
        
        Кстати, в обоих случаях разница теории и практики одинаковая - 6. Наводит на мысли о систематичности погрешности :) - Evgeny_CD(16.11.2008 01:46)

Средства и методы разработки