For a 2n-bit binary number, how many possible values are there such that half the bits are set to 1 (including leading zeros)??

Question

So for n = 1 you'd have 01 and 10. (2 possibilities)

For n = 2 you'd have 0011, 0101, 0110, 1001, 1010, 1100. (6 possibilities)

How do I find the general formula for any positive integer value of n?

Hint: you want to choose $n$ of the $2n$ bits to be 1s – HallaSurvivor Jan 20 '21 at 06:57 — HallaSurvivor, Jan 20 '21 at 06:57

score 2 · Answer 1 · answered Jan 20 '21 at 06:57

2

You choose $n$ out of $2n$ positions to write a $1$, so $2n\choose n$.

answered Jan 20 '21 at 06:57

Hagen von Eitzen

thanks that makes sense. but i don't get why you have to use binomial coefficients. isn't the formula for the possibilities for arranging k elements in a row just k! ? so that means that if i have a string "0011", then the amount of permutations of that string should be 4! ? – O.S. Jan 20 '21 at 07:06
1

@Reneo No, that causes over-counting. For example, label the digits 0-a,0-b,1-a,1-b. The 4! enumeration would wrongly distinguish between (for example) 0-a,0-b,1-a,1-b and 0-a,0-b,1-b,1-a. In general, if you start with $(2n)!$ permutations, then you have to adjust re each combination of the $n$ 1's will be wrongly counted $n!$ times. Similarly, you have to adjust for each combination of the $n$ 0's being wrongly overcounted. This explains the fraction $$\frac{(2n)!}{(n!)(n!)}.$$ – user2661923 Jan 20 '21 at 07:10

1 Answers1