उनमें से कम से कम n लगातार 1 के साथ लंबाई मीटर के संभावित बिट अनुक्रमों की संख्या

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

@ रोस मिलिकन फॉर्मूले के लिए धन्यवाद, जिसे मैंने एप्रोच जीरो के साथ खोजा , मुझे यह उत्तर मिल सकता है , और एप्रोच जीरो को उस परिणाम के साथ फिर से उपयोग करते हुए, यह अन्य सुंदर उत्तर । दोनों पूरक परिणाम देते हैं, इसलिए आपके मामले में हमारे पास है:

$$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) n मी 1 के रन के साथ लंबाई m के तारों की संख्या है।

लंबाई एम -1 के सभी तारों पर विचार करें। वास्तव में उनमें से टी (एम -1, एन) में पहले से ही लगातार 'एन' का एक स्ट्रिंग होता है। चूँकि हम एक 0 या 1 जोड़ सकते हैं, इसलिए हमें लंबाई m स्ट्रिंग्स स्ट्रिंग्स की दोगुनी राशि मिलेगी।

हालाँकि m'th जगह में 1 जोड़ने पर एक नई अच्छी स्ट्रिंग मिलेगी यदि अंतिम (n-1) अंक 1 हैं और n'th से अंतिम अंक एक 0 है और इसके अलावा अंक 1, ।। ।, m - n - 1 में n लगातार 1 का रन नहीं है। यानी स्ट्रिंग इस तरह दिखता है:$$ \underbrace{xx..xx}_{m - n - 1}0\underbrace{11..11}_{n - 1} $$ एक्स-अंक के लिए 2 ^ {m - n - 1} संभावनाएं हैं, लेकिन हमें दोहरी गिनती से बचने के लिए उनमें से टी (एम - एन - 1, एन) को बाहर करना चाहिए।

इसे जोड़कर हम पाते हैं $$ 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)$ शब्द गायब हो जाता है और आपको पुनरावृत्ति संबंध को हल करने में सक्षम होना चाहिए।