# Sequences with $(n+k)/2$ ones, $(k-n)/2$ zeros and condition on number of consecutive digits.

How many binary sequences of length $n$ are there such that there are $\frac{n + k}{2}$ ones, $\frac{k - n}{2}$ zeros and after each contiguous sequence of zeros there must be contiguous sequence of ones of length at least the same? For example, a correct sequence is $1111001110101000111000011111$.

• Didn't we just have this question a few hours ago already? – Henning Makholm Mar 26 '17 at 20:44
• Indeed - if you want to update your question, don't delete it but edit it. – TMM Mar 26 '17 at 20:55
• As for the question: I don't see the point of the weird formulation with n and k, why not just say x ones and y zeros? And have you tried setting up a recurrence relation for N(x,y,n) = number of length-n sequences with x ones and y zeros? At least in practice it should help you evaluate the result, and maybe the recurrence can be solved. – TMM Mar 26 '17 at 20:58
• Because number of ones must be greater than number of zeros exactly by $k$. It is just like sequence of $1$ and $-1$, where they have to sum up to k. Recurrence would be of the form $f(n, k, p)$ - how many sequences of length $n$ are there sucht that number of ones is greater by $k$ and last digits were $p$ zeros. – user128409235 Mar 26 '17 at 21:00
• It's really easier to use x and y and formulate the condition as x-y=k than to have to work with awkward expressions in terms of n and k all the time. So have you tried writing down such a recurrence? (And once you start writing down the recurrence, you will not always have this condition that x-y=k.) – TMM Mar 26 '17 at 21:18