길이가 m 인 가능한 비트 시퀀스의 수 (최소 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

내가 함께 검색 @Ross 밀리칸 공식 덕분에, 접근 제로 , 내가 찾을 수있는 이 답변을 하고, 그 결과이 다른 제로에 접근을 다시 사용하여 아름다운 대답을 . 둘 다 보완적인 결과를 제공하므로 귀하의 경우에는 다음이 있습니다.

$$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)을 길이가 m 인 문자열의 개수이며 n 개의 연속 된 1이 실행되도록합니다.

길이가 m-1 인 모든 문자열을 고려하십시오. 정확히 T (m-1, n)에는 이미 'n'개의 연속 숫자 문자열이 포함되어 있습니다. 0 또는 1을 추가 할 수 있기 때문에이 길이의 두 배인 m 문자열 문자열을 얻을 수 있습니다.

그러나 m 번째 자리에 1을 추가하면 마지막 (n-1) 자리가 1이고 마지막 n 번째 자리에서 마지막 자리까지가 0이고 추가로 자리 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)를 제외해야합니다.