1
$\begingroup$

As part of an exercise I'm doing, I would like to use the following claim:

The number of sequences with a length of $2n+1$ of zeroes and ones only, the number of sequences whereas there are more zeroes than ones is $ \frac{2^{2n+1}}{2}$

For some reason it looks pretty trivial, but I do not have a clue how to prove this claim.

I thought about using induction, but without any success.

Is this really a trivial clain, or is there a clever way of proving it?

Thanks.

$\endgroup$
1
  • 1
    $\begingroup$ It's trivial....just remark that ties are impossible and there is an equal chance that $H>T$ or $T>H$. $\endgroup$
    – lulu
    Apr 9, 2017 at 15:12

2 Answers 2

Reset to default
3
$\begingroup$

There are $2^{2n+1}$ sequences of $0$s and $1$s. Half of them are going to have more ones and zeros and half of them and going to have more zeros than ones. Hence $\frac{2^{2n+1}}{2}$ is your answer.

$\endgroup$
1
  • $\begingroup$ Thanks, but is this sufficent? no need to formally prove that? $\endgroup$
    – superuser123
    Apr 9, 2017 at 15:32
1
$\begingroup$

Let $A$ be the set of sequences with a majority of $0$'s and $B$ the set of sequences with a majority of $1$'s. Define a function $f:A\rightarrow B$ that picks a sequence and exchanges all $0$'s for $1$'s and vice versa. That's a bijection. Therefore $|A| = |B|$. Since the number of items in the sequence is odd you can't have an equal number of $0$'s and $1$'s. Therefore all the sequences belong to either $A$ or $B$. Also note that $A\cap B = ø$. Finally we can write $$|A|+|B| = 2^{2n+1}$$ $$2|A| = 2^{2n+1}$$ $$|A| = \frac{2^{2n+1}}{2}$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .