Jumlah urutan bit yang mungkin dengan panjang m dengan setidaknya n berturut-turut 1 di dalamnya
Saya telah melihat pertanyaan serupa untuk ini tetapi masing-masing tampaknya merupakan kasus khusus dari pertanyaan umum ini. Menjawab ini akan bermanfaat bagi penelitian saya, tetapi saya bukan ahli kombinatorik, dan pertanyaan yang tampaknya sederhana ini luput dari perhatian saya. Apakah ada rumus sederhana untuk menghitung ini? Semua yang saya lihat secara online berpusat pada hal-hal seperti "baik 2 berturut-turut 1 atau 0" atau "tidak mengandung ..".
Jika itu membantu, saya tahu itu untuk $m = 8$ bit dan mengatakan urutan dilambangkan $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 $$
Menariknya saya menemukan itu $S(8,4)=S(9,5)=S(10,6)=S(11,7)=48$ Saya belum menguji $S(12,8)$ karena saya tidak ingin komputer saya meleleh tetapi saya melihat pola ... Namun tampaknya ini tidak berhasil $m<8$.
Jawaban
Berkat rumus @Ross Millikan, yang saya cari dengan Approach Zero , saya bisa menemukan jawaban ini , dan menggunakan lagi Approach Zero dengan hasil itu, jawaban indah lainnya ini . Keduanya memberikan hasil yang saling melengkapi, jadi dalam kasus Anda, kami memiliki:
$$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}$$
Lihat tautan untuk detailnya.
Jika stringnya $m$ bit panjang dan Anda menuntut dijalankan dengan tepat $n\ 1$s kita dapat menemukan rumus untuk $n \ge \frac m2$. Mari kita sebut ini$T(m,n)$. Jika run berada di salah satu ujung string ($2$ pilihan) Anda membutuhkan $0$ di akhir menjalankan dan memiliki $2^{m-n-1}$pilihan untuk bit lainnya. Jika run tidak di akhir string, ada$m-n-1$ tempat yang dapat dimulai dan Anda miliki $2^{m-n-2}$pilihan untuk melengkapi string. Jika$m-n-2$ negatif tidak ada bit lain untuk diisi. Jadi $$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} $$ dan fakta bahwa itu hanya bergantung pada $m-n$jelas. Kemudian$$S(m,n)=\sum_{i=n}^mT(m,i)$$ Saya ulangi bahwa ini hanya berfungsi untuk $n \ge \frac m2$. Alasannya hanya tergantung$m-n$ karena jika Anda mengambil string dari tipe tersebut $(m,n)$ Anda dapat menemukan jenis string yang unik $(m+1,n+1)$ dengan memperpanjang prosesnya satu bit lagi.
Saya tidak akan memberikan rumus, tetapi hanya relasi pengulangan. Misal T (m, n) adalah banyaknya string dengan panjang m dengan run n berturut-turut 1.
Perhatikan semua senar dengan panjang m-1. Tepatnya T (m-1, n) di antaranya sudah berisi string 'n' digit yang berurutan. Karena kita dapat menambahkan 0 atau 1 kita akan mendapatkan dua kali lipat jumlah string m panjang ini.
Namun menambahkan 1 di tempat m'th akan memberikan string baru yang bagus jika angka terakhir (n-1) adalah 1 dan angka n hingga terakhir adalah 0 dan sebagai tambahan angka di tempat 1, .. ., m - n - 1 tidak mengandung n berturut-turut 1. yaitu stringnya terlihat seperti ini:$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ Ada 2 ^ {m - n - 1} kemungkinan untuk x-digit, tapi kita harus mengecualikan T (m - n - 1, n) dari mereka untuk menghindari penghitungan ganda.
Menambahkan semuanya, kami temukan $$ T(m, n) = 2\cdot T(m - 1, n) - T(m - n - 1, n) + 2^{(m - n - 1)} $$
Jika $m - n - 1 \leq n$, yaitu $m \leq 2n + 1$, itu $T(m - n - 1, n)$ istilah menghilang dan Anda harus bisa menyelesaikan hubungan pengulangan.