How many bit strings of length 10 do not have four consecutive 1s?


Question and Answers Forum

All Questions Topic List
Permutation and Combination Questions
Previous in All Question Next in All Question
Previous in Permutation and Combination Next in Permutation and Combination
Question Number 203832 by depressiveshrek last updated on 29/Jan/24

$How many bit strings of length 10 do not$ $have four consecutive 1 s ?$
	Answered by nikif99 last updated on 30/Jan/24

	$T o t a l n u m b e r o f b i t s t r i n g s o f l e n g t h 10$ $i s 2^{10} = 1024 (0 - 1023) .$ $O f t h e m, t h e r e a r e 7 b i t s t r i n g s o f$ $e x a c t l y 4^{'} 1^{'} s a t p o s i h i o n s 1 - 7 .$ $00 \underset{}{\underset{⏟}{1111} 0000}$ $F u r t h e r m o r e, t h e r e a r e 3 b i t s t r i n g s$ $o f m o r e t h a n o n e^{'} 1111^{'} :$ $1111011110$ $1111001111$ $0111101111$ $A n s w e r : 1024 - 7 - 3 = 1014$
	Commented by deleteduser1 last updated on 30/Jan/24

	$I t s e e m s 1011110000, 1110111100, e t c s h o u l d$ $a l s o b e v a l i d f o r t h o s e c o n t a i n i n g t h e s t r i n g$ $1111$
	Commented by nikif99 last updated on 30/Jan/24

	$Y o u a r e r i g h t . I s h o u l d r e - e x a m i n e i t .$ $T h a n k y o u .$
	Commented by nikif99 last updated on 30/Jan/24

	$R e - e v a l u a t i n g m y c o m p u t a t i o n s :$ $I n a 10 - b i t s t r i n g, I f i x a s e r i e s o f$ $4 c o n s e c u t i v e^{'} 1^{'} s e n s u r i n g a d j a c e n t$ $b i t s (i f e x i x t) a r e s e t t o 0 . E x a m p l e :$ $0011110000 w h e r e$ $r e d s a r e s e t t o 1, b l u e s a r e s e t t o 0 t o$ $p r o h i b i t e x p a n s i o n o f r e d s a n d b l a c k s$ $d e r i v e a 4 - b i t s e t w i t h v a l u e s 0 t o 15 .$ $S o, w e h a v e n e x t o p t i o n s .$ $a) 11110 \underset{}{\underset{⏟}{00000}} (32 c a s e s)$ $b) 011110 \underset{}{\underset{⏟}{0000}} (16)$ $c) 0011110000 (16)$ $d) 0001111000 (16)$ $e) 0000111100 (16)$ $f) 0000011110 (16)$ $g) 0000001111 (32)$ $t o t a l 32 \times 2 + 16 \times 5 = 144$ $m i n u s 2 f o r 0111101111 a n d 1111001111$ $w h i c h a r e d o u b l e c o u n t e d = 142 w i t h 4$ $c o n c e c u t i v e^{'} 1^{'} s .$ $N o n c o n s e c u t i v e o n e s a r e$ $1024 - 142 = 882$
	Commented by deleteduser1 last updated on 31/Jan/24

	${S h o u l d n}^{'} t t h e s t r i n g s w i t h ⩾ 4 1^{'} s a l s o b e v a l i d ?$ $S i n c e t h e 4 c o n s e c u t i v e 1^{'} s i s a l s o c o n t a i n e d i n i t ?$ $F o r e x a m p l e 0111111100 o r 1111110101$
	Commented by nikif99 last updated on 30/Jan/24

	$T h e q u e s t i o n i s ‘ ‘ d o n o t h a v e 4$ $c o n s e c u h i v e 1 s^{″}, 0111111100 h a s 7,$ $s o I c o n s i d e r i s n o t c o n t a i n e d .$ ${T h a t}^{'} s w h y I b l o c k e d n e i g h b o u r i n g$ $p l a c e s w i t h 0 .$
	Commented by deleteduser1 last updated on 30/Jan/24

	$I t h a s 7 b u t i t s t i l l h a s 4 c o n s e c u t i v e 1^{'} s$ $c o n t a i n e d i n i t$
	Answered by deleteduser1 last updated on 31/Jan/24

	$C a s e 1 : 1111______\Rightarrow 2^{6} w a y s$ $C a s e 2 :__{1} 1111_____\Rightarrow 2^{5} \times 1 w a y s a n d__{1} = 0$ $C a s e 3 :__{1}__{2} 1111____$ $P o s s i b l e f o r (__{1},__{2}) = (1, 1), (1, 0), (0, 1), (0, 0)$ $O f t h i s, o n l y (1, 0) \land (0, 0) {h a v e n}^{'} t b e e n a c c o u n t e d$ $You can't use 'macro parameter character #' in math mode$ $C a s e 4 :__{1}__{2}__{3} 1111___$ $P o s s i b l e : (0, 0, 0), (0, 0, 1), (0, 1, 0), (1, 0, 0), (0, 1, 1)$ $(1, 0, 1), (1, 1, 0)$ $You can't use 'macro parameter character #' in math mode$ $C a s e 5 :__{1}__{2}__{3}__{4} 1111__\Rightarrow 2^{3} \times 2^{2} = 2^{5} w a y s$ $C a s e 6 :__{1}__{2}__{3}__{4}__{5} 1111_$ $O t h e r t h a n c a s e 1,__{5} a l w a y s c o n t a i n e d 1$ $You can't use 'macro parameter character #' in math mode$ $C a s e 7 :__{1}__{2}__{3}__{4}__{5}__{6} 1111$ $__{6} = 0 a n d__{1}__{2}__{3}__{4}__{5} i s s u c h t h a t i t c o n t a i n s n o$ $4 c o n s e c u t i v e 1^{'} s (11110, 01111, 11111)$ $You can't use 'macro parameter character #' in math mode$ $You can't use 'macro parameter character #' in math mode$ $You can't use 'macro parameter character #' in math mode$ $= 773$
	Commented by nikif99 last updated on 31/Jan/24

	$G o o d a n d c l e a r e x p l a n a t i o n .$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum