0

So I'm a bit rusty, but given a binary string, I'd like to calculate the permutations that exist which contain an even number of 1's within the range of binary 0 to said binary string.

In other words, for all binary strings for the decimal range 0 - n, as n is the given upper bound. Below, I'll use 20 as an example.

For e.g

10100 (dec: 20), and starting from 0:

11 (dec: 3), 1010 (dec: 10) etc.

I figured the calculation would be:

nCr(5,2) + nCr(5,4) as the length is 5, and evens in that range are 2,4. This yields 15, though the answer should be 10 (I'm pretty sure)

What am I missing?

Jack Rohme
  • 1
  • This is not clear. What does "within the range of binary 0 to said binary string." mean? What's $n$? What's $r$? Can you work an explicit example to show what you mean? – lulu Mar 13 '18 at 14:33
  • I apologize! I will try and make the above comment more clear. Essentially, from the range of 0 to 20 (or 0 to 10100 in binary terms). – Jack Rohme Mar 13 '18 at 14:35

1 Answers1

1

What goes wrong with your method is that $5 \choose 2$ picks out all strings of length $5$ that have two $1$'s ... but that includes a string like $11000$ which is greater than $20$. Same for $5 \choose 4$: a string like $11011$ should not be included.

Bram28
  • 100,612
  • 6
  • 70
  • 118
  • Good note, thank you! So, would it be like;

    nCr(3,1) [ for 1 0 _ _ _ and the 3 remaining to be 1, equaling 2 1's] + nCr(4,2) [ for 0 _ _ _ _ for the binary range of length 4 & 2 1's] + nCr(4,4) [ for 1111]

    or something close to this..?

     – Jack Rohme Mar 13 '18 at 14:37
  • @JackRohme Yes, that works for your specific example .. (and note that 3C1=3, 4C2 = 6, and 4C4=1, so you get 1+6+3=10 ... which I verified is indeed the correct answer). The question is how to generalize this for any number though ... – Bram28 Mar 13 '18 at 14:43