少なくともn個の連続した1を含む長さmの可能なビットシーケンスの数

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

アプローチゼロで検索した@RossMillikanの式のおかげで、この答えを見つけることができました。また、アプローチゼロを使用して、この別の美しい答えを得ることができました。どちらも補完的な結果をもたらすので、あなたの場合は次のようになります。

$$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$■次の式を見つけることができます $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)$ 実行をもう1ビット拡張します。

LisanneTaams Dec 12 2020 at 21:11

式は与えませんが、漸化式だけを与えます。T（m、n）を、n個の連続する1が実行される長さmの文字列の数とします。

長さm-1のすべての文字列について考えてみます。それらの正確にT（m-1、n）には、すでに「n」個の連続した数字の文字列が含まれています。0または1を追加できるので、この長さmの文字列の2倍の量が得られます。

ただし、最後の（n-1）桁が1で、最後からn番目の桁が0で、さらに1の桁が1の場合、m番目の場所に1を追加すると、新しい適切な文字列が得られます。。、m --n -1には、n個の連続する1の実行は含まれません。つまり、文字列は次のようになります。$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ x桁には2 ^ {m --n -1}の可能性がありますが、二重カウントを避けるために、それらのT（m --n -1、n）を除外する必要があります。