Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 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).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.