Nombre de séquences de bits possibles de longueur m avec au moins n 1 consécutifs
J'ai vu des questions similaires à celle-ci, mais elles semblent toutes être des cas particuliers de cette question générale. Répondre à cela serait bénéfique pour mes recherches, mais je ne suis pas un expert en combinatoire, et cette question en apparence simple m'échappe. Existe-t-il une formule simple pour calculer cela? Tout ce que j'ai vu en ligne a été centré sur des choses comme «soit 2 1 consécutifs ou 0» ou «ne contient aucun…».
Si ça aide, je le sais pour $m = 8$ bits et dire que la séquence est notée $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 $$
Fait intéressant, je trouve que $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$ Je n'ai pas testé $S(12,8)$ parce que je ne veux pas que mon ordinateur fond, mais je vois un motif ... Cependant, cela ne semble pas fonctionner pour $m<8$.
Réponses
Grâce à la formule @Ross Millikan, que j'ai recherchée avec Approach Zero , j'ai pu trouver cette réponse , et en utilisant à nouveau Approach Zero avec ce résultat, cette autre belle réponse . Les deux donnent le résultat complémentaire, donc dans votre cas nous avons:
$$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}$$
Voir les liens pour plus de détails.
Si la chaîne est $m$ bits de long et vous exigez une série d'exactement $n\ 1$s nous pouvons trouver une formule pour $n \ge \frac m2$. Appelons ça$T(m,n)$. Si l'exécution est à une extrémité de la chaîne ($2$ choix) vous avez besoin d'un $0$ à la fin de la course et avoir $2^{m-n-1}$choix pour les autres bits. Si l'exécution n'est pas à la fin de la chaîne, il y a$m-n-1$ endroits où il peut commencer et vous avez $2^{m-n-2}$choix pour compléter la chaîne. Si$m-n-2$ est négatif, il n'y a pas d'autres bits à remplir. Donc $$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} $$ et le fait que cela ne dépend que de $m-n$est clair. ensuite$$S(m,n)=\sum_{i=n}^mT(m,i)$$ Je répète que cela ne fonctionne que pour $n \ge \frac m2$. La raison pour laquelle cela ne dépend que de$m-n$ est parce que si vous prenez une chaîne du type $(m,n)$ vous pouvez trouver une chaîne unique de type $(m+1,n+1)$ en prolongeant la course d'un bit supplémentaire.
Je ne donnerai pas de formule, mais juste une relation de récurrence. Soit T (m, n) le nombre de chaînes de longueur m avec une suite de n 1 consécutifs.
Considérez toutes les chaînes de longueur m-1. Exactement T (m-1, n) d'entre eux contiennent déjà une chaîne de «n» chiffres consécutifs. Puisque nous pouvons ajouter un 0 ou un 1, nous obtiendrons le double de cette quantité de chaînes de longueur m.
Cependant, ajouter un 1 à la mième place donnera une nouvelle bonne chaîne si les derniers (n-1) chiffres sont un 1 et le nième au dernier chiffre est un 0 et en plus les chiffres à la place 1, .. ., m - n - 1 ne contiennent pas une série de n 1 consécutifs. c'est-à-dire que la chaîne ressemble à ceci:$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ Il y a 2 ^ {m - n - 1} possibilités pour les chiffres x, mais nous devrions en exclure T (m - n - 1, n) pour éviter le double comptage.
En ajoutant tout, nous trouvons $$ T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} $$
Si $m - n - 1 \leq n$, c'est à dire $m \leq 2n + 1$, la $T(m - n - 1, n)$ terme disparaît et vous devriez être en mesure de résoudre la relation de récurrence.