2
$\begingroup$

If we are to have (two, for example) binary numbers, such that their sum is $100111010_2$, and given that the first number has 5 ones, and the second number has 3 ones, can I find the numbers that when added together gave $100111010_2$ (the two numbers are $11010110_2$ and $01100100_2$, by the way)?

My theory is that, the number of partitions of a binary number $n_2$ into $k$ binary parts with the given constraint of ones present in each, there can at most be $k$ ways in which $n_2$ can be partitioned (without order, not necessarily distinct). Anyone here to prove (or disprove) this?

1 Answers 1

1

Not true. For instance, suppose you want to write the number with $kn$ binary digits that are all one as a sum of $k$ binary numbers each having $n$ ones. For each digit you can let all the summands except one have a zero, and you can choose the nonzero summand independently for each digit. There are $k^{kn}$ ways to make these choices. Even if you treat permutations of the summands as equivalent, there are still at least $k^{kn}/k!$ distinct ways to form the sum, which is much greater than $k$ (exponentially so as $n$ increases).