0
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Hint: you want to choose $n$ of the $2n$ bits to be 1s $\endgroup$
    – HallaSurvivor
    Jan 20, 2021 at 6:57

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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! ? $\endgroup$
    – O.S.
    Jan 20, 2021 at 7:06
  • 1
    $\begingroup$ @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!)}.$$ $\endgroup$
    – user2661923
    Jan 20, 2021 at 7:10

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