1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Didn't we just have this question a few hours ago already? $\endgroup$ – Henning Makholm Mar 26 '17 at 20:44
  • $\begingroup$ Indeed - if you want to update your question, don't delete it but edit it. $\endgroup$ – TMM Mar 26 '17 at 20:55
  • $\begingroup$ 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. $\endgroup$ – TMM Mar 26 '17 at 20:58
  • $\begingroup$ 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. $\endgroup$ – user128409235 Mar 26 '17 at 21:00
  • $\begingroup$ 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.) $\endgroup$ – TMM Mar 26 '17 at 21:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.