# Number of possible binary strings of length k

One of my friends was asked this question recently:

You have to count how many binary strings are possible of length "K". Constraint: Every 0 has a 1 in its immediate left.

-

This question can be reworded: How many binary sequences of length K are posible if there are no two consecutive 0s, but the first element should be 1 (else the constrains fails). Let us forget about the first element (we can do it bcause it is always fixed). Then we got a very famous task that sounds like this: "What is the number of binary sequences of length K-1 that have no consecutive 0's." The explanation can be found, for example, here

Then the answer will be F(K+1) where F(K) is the K`th fibonacci number starting from (1 1 2 ...).

-
How does this relate to Fibonacci, can you provide some intuition behind it? – Chander Shivdasani Aug 14 '12 at 8:11
@Chander Shivdasani: Edited an answer. If you do not undersand the referenced explanation I can do it here – dvvrd Aug 14 '12 at 8:19
Got it, Thanks! – Chander Shivdasani Aug 14 '12 at 8:24

`∑ From n=0 to ⌊K/2⌋ of (K-n)Cn`; n is the number of zeros in the string

The idea is to group every 0 with a 1 and find the number of combinations of the string, for n zeros there will be n ones grouped to them so the string becomes (k-n) elements long. There can be no more than of K/2 zeros as there would not have enough ones to be to the immediate left of each zero.
E.g. `111111[10][10]1[10]` for K = 13, n = 3

-
{"found_math": false, "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": 0, "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}