Number of sequences over {0,1} such that sequence contains at least half ones

Question

How to calculate number of sequences over {0,1} such that each sequence contains at least half ones?

Answer 1

The total number of sequences of length n is 2^n. If n is odd, exactly the half of them (2^(n-1)) have at least half ones. For even n, you have to take into account that there are n!/((n/2)!^2) sequences with exactly half ones. So in this case I think you have in total (1/2)*(2^n + n!/((n/2)!^2)).

Answer 2

Edit: Dang! We (I) should always read the problem carefully!
The following deals with enumerating the number of sequences where the number of 0s and 1s is equal! The actual problem is that the number of zeros should be less or equal to that of 1s !!!

Pierr's formula, n!/(2*(n/2)!) is almost correct, it is actually, n!/((n/2)! * (n/2)!)

but this could use a bit of explanation (pun intended ;-) ).

n being the total length, we know that n has to be even, since the problem requires an equal number of 0s and of 1s.

Let's focus on placing the 0s. For a sequence of length n, we have n/2 zero-bits, to put in one of the n positions of the sequence. We only need to count for the zero-bits, since after that there will be no choices left with regards to the one-bits: all other positions will require a 1 in them.

So... n/2 zero-bits, for n positions... There are n ways to pick the first position, then (n-1) ways to pick the second position (two bits couldn't occupy the same position), etc. This number of choices is therefore

  n! / (n/2)!

for example, for n=6, we have

       6 * 5 * 4 choices,  
       which, by multiplying and dividing by (3*2*1) is equivalent to
    =  6 * 5 * 4 * (3 * 2 * 1) / (3 * 2 * 1)   
    =  6! / 3!
    =  n! / (n/2)!  (a)

Now... some of these choices [of where to put first bit, second bit etc,] result in the same combination, because all zero-bits are the same, and therefore whether one put say the "first" bit in position x and the "2nd" bit in position y, or the first into y and the second into x, we'd have the same combination. There are (n/2)! ways of arranging these n/2 bits. In the example of n = 6, there are 3 ways of picking the position for the "first" bit, 2 ways for the 2nd bit and 1 (i.e. no choice) for the last zero-bit. The complete formula then needs to be (a) divided by (n/2)!, i.e:

  n! / (n/2)! * 1/(n/2)! 
= n! / ((n/2)! * (n/2)!)