Tuesday 14 August 2018

How many binary numbers have the same number of zeros and ones?



On August 14, I wrote:"The binary expression for 226 has the same number of ones and zeros. " It made me wonder how frequently that happened. For instance out of the 10 or less digit binary numbers, how many, or what percentage have the same number of zeros and ones?

There are 2 one digit binary numbers (0-1) and neither of them (of course, one digit) have an equal number of zeros and ones.

There are 2 two digit numbers (2 and 3) and one of them, (10 in binary) has and equal number of ones and zeros

The 4 three digit numbers (4-7) can't have equal numbers as they are odd.,.(I will skip the odds from now on)


The 8 four digit numbers (8-15) have three that have an equal number of ones and zeros: (1001), (1010), (1100)

The 32 six digit numbers (32-63) have ten with an even number of ones and zeros,

the 128  eight digit numbers (128-255) have 35 numbers with an even number of ones and zeros

and the 512 ten digit numbers (512-1023) there are 126.

If we add them all up, there are 1+3+5+10+ 35 + 126 = 175 binary numbers with ten or less digits with an equal number of ones and zeros, and since there are 1024-1 numbers with ten or less digits, we see that the fraction of binary numbers with equal numbers of zero and ones is \( \frac{175}{1023}\) numbers or about 17.1% of them that have an equal number of  both digits.

It seems that the fraction keeps dropping pretty fast and I expect, but have not confirmed, that it will approach zero as n goes to infinity.
OK, Pretty fun stuff. But if you look at the numbers 1, 3, 10, 35, 126....

They have that sequence at OEIS, and they mention dozens of things it represents, but unless I missed something, they don't mention this.

Now where do those numbers come from?

If you check your Pascal's Arithmetic Triangle, you will see that if you take the digit in 1 choose zero, and go straight down you get these same numbers.

But surely that looks familiar:

Ah yes, those are the numbers with \( {n}\choose {(n-1)/2} \).  All the n digit numbers  go from 2n to 2n+1, for example the smallest eight digit binary number is 27or 10000000[2] and the largest is  28 -1, or 255, so there are 255 binary numbers with eight digits or less.  The reason for the calculation of 8 digit numbers with equal numbers of ones and zeros involves 7 choose 3, is because the first digit has to be a one.  Out of the 7 remaining, to make the zeros and ones even, we have to have three of them be ones, and any three will do. But notice we are computing with in our formula when we are talking about eight digits. If we want to calculate directly using n as the number of digits we just adjust to \( {n-1}\choose {(n-2)/2} \).

 If we add all these numbers in the arithmetic triangle to get the total of the first n (n-even) with n or less decimal digits and  divide by 2n+1 -1 (the highest n digit binary number)  we get the series of the fraction of numbers with equal numbers of one and zeros. 1/3 of one and two digit numbers. 4/15 of all binary numbers  1/3,  4/16, 14/63, 49/263, ...   or in general for  S(n)=\( {\sum _{k=1}^{n/2} \binom{2k-1} {k-1}}\) / \( (2^{2k}-1) \); for even numbers, and for odd n numbers use \( S(n) = \frac {S(n-1)} {2^n-1}\) .  [if you want to check any of these in Wolfram alpha, use (sum (binomial (2j-1,j-1)  , j=1 to 25))/((2^50)-1) where the numbers in italics are n/2  and n for the number of terms you want to sum]

As far as the percentage of ALL binary numbers with the same number of ones and zeros, I checked S(50) and it was apprx. .0753  and S(100) about .05324, and S(200) abt .0376.

After writing this, I realized that all year days (1-366)  are less than 512 = 29, so all the days that possibly have binary expressions with equal numbers of zeros and ones, must be less than 2^8 = 256, and this was day 226, so only 29 days after today were candidates.  226[10]= 11100010[2] so the only bigger numbers binary numbers were 11100100, 11101000, and 11110000 would be the last of the year.  Those numbers in decimal are 226, 228, 232, and 240.  And since we know that there are only  49 binary numbers with 8 digits or less that have the equality we seek, 226 must be the 46th, and there are a total of 49 in the year. 


No comments: