Suppose there are $n$ zero's and $n$ one's. And you have arrange it in a $2n$ digit binary sequence such that if you took first $k$ numbers from starting then sum of digits of this $k$ digit numbers should be greater than or equal to $\frac{k}{2}$ $\forall k\leq 2n$.
This problem can be reduced to number of one's should be $\geq$ number of zero's . Then I tried making recurrence. Let $a_n$ denotes number of arrangement for $2n$ numbers in this manner. Now to convert $a_n$ to $a_{n+1}$ we can either place $10$ pair at the end of $a_n$ numbers or we can replace any one zero from a $a_n$ sequence from the new one and two zeros at last. But can't do this with $1$.
- $a_1=1; (10)$
- $a_2=2; (1010, 1100)$
- $a_3=5; (101010, \underline{111000}, 101100),(110010,\underline{111000},110100)$ repetition of $111000$ two times
- $a_4=14; (10101010,\underline{1110100},\underline{10111000},10101100),(11100010,\underline{11110000},\underline{1110100},11100100),(10110010,\underline{11110000},\underline{10111000},10110100),(11001010,\underline{1110100},\underline{11011000},11001100),(11010010,\underline{11110000},\underline{11011000},11010100)$ Repetion of $11110000$ $3$ times and repetition of $10111000$ $2$ times, repetition of $1110100$ $3$ times, repetition of $11011000$ $2$ times.
I became even difficult to calculate $a_5$, and I was unable to catch a pattern in repetition. How could I solve this? Can it be solved using recurrence?