Количество возможных битовых последовательностей длины m, содержащих не менее n последовательных единиц в них

Dec 12 2020

Я видел похожие вопросы к этому, но каждый из них кажется частным случаем этого общего вопроса. Ответ на этот вопрос был бы полезен для моего исследования, но я не специалист по комбинаторике, и этот, казалось бы, простой вопрос ускользает от меня. Есть ли простая формула для этого? Все, что я видел в сети, было сосредоточено на таких вещах, как «2 последовательных 1 или 0» или «не содержит ..».

Если это поможет, я знаю это для $m = 8$ биты и говорят, что последовательность обозначается $S(m,n)$ $$ S(m = 8, n = 1) = 255 \\ S(8,2) = 201 \\ S(8,3) = 107 \\ S(8,4) = 48 \\ S(8,5) = 20 \\ S(8,6) = 8 \\ S(8,7) = 3 \\ S(8,8) = 1 $$

Интересно я нахожу, что $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$ Я не тестировал $S(12,8)$ потому что я не хочу, чтобы мой компьютер плавился, но я вижу закономерность ... Однако, похоже, это не работает для $m<8$.

Ответы

2 BillyJoe Dec 12 2020 at 21:25

Благодаря формуле @Ross Millikan, которую я искал с помощью Approach Zero , я смог найти этот ответ и снова использовал Approach Zero с этим результатом, другим прекрасным ответом . Оба дают дополнительный результат, поэтому в вашем случае у нас есть:

$$S(m,n) = 2^m-\sum_{q=0}^{\lfloor m/n\rfloor} {m-nq\choose q} (-1)^q 2^{m-(n+1)q} + \sum_{q=0}^{\lfloor m/n\rfloor - 1} {m-n(q+1)\choose q} (-1)^q 2^{m-n-(n+1)q}$$

Подробности смотрите по ссылкам.

2 RossMillikan Dec 12 2020 at 20:23

Если строка $m$ бит, и вам потребуется ровно $n\ 1$s мы можем найти формулу для $n \ge \frac m2$. Назовем это$T(m,n)$. Если пробег находится на одном конце строки ($2$ варианты) вам нужен $0$ в конце пробега и иметь $2^{m-n-1}$варианты для других бит. Если пробег не в конце строки, есть$m-n-1$ места, где это может начаться, и у вас есть $2^{m-n-2}$варианты завершения строки. Если$m-n-2$ отрицательный, другие биты заполнять не нужно. $$T(m,n)=\begin {cases} 1&n=m\\2&n+1=m\\2^{m-n}+(m-n-1)2^{m-n-2}&n+2 \le m \end {cases} $$ и тот факт, что это зависит только от $m-n$чисто. потом$$S(m,n)=\sum_{i=n}^mT(m,i)$$ Повторяю, это работает только для $n \ge \frac m2$. Причина, по которой это зависит только от$m-n$ потому что если вы возьмете строку типа $(m,n)$ вы можете найти уникальную строку типа $(m+1,n+1)$ увеличив пробег еще на один бит.

LisanneTaams Dec 12 2020 at 21:11

Я не буду приводить формулу, а просто повторяю соотношение. Пусть T (m, n) будет количеством строк длины m с последовательностью n последовательных единиц.

Рассмотрим все струны длиной m-1. Ровно T (m-1, n) из них уже содержат строку из n последовательных цифр. Так как мы можем добавить 0 или 1, мы получим вдвое большее количество строк длиной m.

Однако добавление 1 на m-е место даст новую хорошую строку, если последние (n-1) цифры равны 1, а n-я к последней цифре - 0, а кроме того цифры на месте 1, .. ., m - n - 1 не содержат серии из n последовательных единиц. т.е. строка выглядит так:$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ Есть 2 ^ {m - n - 1} возможностей для x-цифр, но мы должны исключить T (m - n - 1, n) из них, чтобы избежать двойного счета.

Сложив все это, мы находим $$ T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} $$

Если $m - n - 1 \leq n$, т.е. $m \leq 2n + 1$, то $T(m - n - 1, n)$ член исчезает, и вы сможете решить рекуррентное отношение.