Número de possíveis sequências de bits de comprimento m com pelo menos n 1's consecutivos nelas
Já vi perguntas semelhantes a esta, mas cada uma delas parece ser um caso especial desta questão geral. Responder a isso seria benéfico para minha pesquisa, mas não sou um especialista em combinatória, e essa pergunta aparentemente simples me escapa. Existe uma fórmula simples para calcular isso? Tudo o que tenho visto online gira em torno de coisas como "2 1s ou 0s consecutivos" ou "não contém ...".
Se ajuda, eu sei disso $m = 8$ bits e dizer que a sequência é denotada $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 $$
Curiosamente, estou descobrindo que $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$ Eu não testei $S(12,8)$ porque não quero que meu computador derreta, mas estou vendo um padrão ... No entanto, isso não parece funcionar para $m<8$.
Respostas
Graças à fórmula @Ross Millikan, que pesquisei com o Approach Zero , pude encontrar essa resposta , e usando novamente o Approach Zero com esse resultado, essa outra bela resposta . Ambos fornecem o resultado complementar, portanto, no seu caso, temos:
$$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}$$
Veja os links para detalhes.
Se a corda for $m$ bits de comprimento e você exige uma execução de exatamente $n\ 1$podemos encontrar uma fórmula para $n \ge \frac m2$. Vamos chamar isso de$T(m,n)$. Se a corrida for em uma extremidade da string ($2$ escolhas) você precisa de um $0$ no final da corrida e ter $2^{m-n-1}$escolhas para os outros bits. Se a corrida não for no final da string, há$m-n-1$ lugares que pode começar e você tem $2^{m-n-2}$opções para completar a string. E se$m-n-2$ é negativo, não há outros bits para preencher. $$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} $$ e o fato de que só depende de $m-n$está claro. Então$$S(m,n)=\sum_{i=n}^mT(m,i)$$ Repito que isso só funciona para $n \ge \frac m2$. A razão pela qual só depende de$m-n$ é porque se você pegar uma string do tipo $(m,n)$ você pode encontrar uma string única de tipo $(m+1,n+1)$ estendendo a execução em mais um bit.
Não vou dar uma fórmula, mas apenas uma relação de recorrência. Seja T (m, n) o número de strings de comprimento m com uma sequência de n 1's consecutivos.
Considere todas as cordas de comprimento m-1. Exatamente T (m-1, n) deles já contém uma string de 'n' dígitos consecutivos. Como podemos adicionar 0 ou 1, obteremos o dobro dessa quantidade de m strings de comprimento.
No entanto, adicionar 1 na m'ésima casa fornecerá uma nova string válida se os últimos (n-1) dígitos forem 1 e o enésimo ao último dígito for 0 e, além disso, os dígitos no lugar 1, .. ., m - n - 1 não contém uma sequência de n 1s consecutivos. ou seja, a string tem a seguinte aparência:$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ Existem 2 ^ {m - n - 1} possibilidades para os dígitos x, mas devemos excluir T (m - n - 1, n) deles para evitar a contagem dupla.
Somando tudo, encontramos $$ T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} $$
E se $m - n - 1 \leq n$, ie $m \leq 2n + 1$, a $T(m - n - 1, n)$ o termo desaparece e você deve ser capaz de resolver a relação de recorrência.