# Math Help - Derive a formula

1. ## Derive a formula

Hi
Could anyone help me with that problem:

A bit string is a string over the alphabet {0,1}. Let n be a natural number. Derive a formula for the number of bit strings of length 2n that contain 01 as a substring. Explain your answer clearly.

Thx

2. Originally Posted by mauro21pl
Hi
Could anyone help me with that problem:

A bit string is a string over the alphabet {0,1}. Let n be a natural number. Derive a formula for the number of bit strings of length 2n that contain 01 as a substring. Explain your answer clearly.
The total number of strings of length n is $2^n$. We must subtract from that the number of strings that do not contain 01 as a substring.

But if a string does not contain 01 then it must never have a 0 followed by a 1. So all the 1s must come at the beginning of the string, followed by all the 0s, like 111...100...0. There are n+1 such strings of length n. The formula is therefore $2^n-n-1$.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 2, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.7431482076644897, "perplexity": 177.8449559393568}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2015-11/segments/1424936463093.76/warc/CC-MAIN-20150226074103-00229-ip-10-28-5-156.ec2.internal.warc.gz"}