|
|
|
|
|
|
by gjm11
5128 days ago
|
|
|
A shorter explanation with no binomial coefficients in it: Write down those 2^n numbers once in order, and once in reverse order, and pair them off. Note that each x gets paired with 2^(n-1) XOR x. So each number and its partner have exactly n 1-bits between them. In other words, twice the number we're looking for is 2^n.n; so the number we're looking for is 2^(n-1).n. (More informally: Each bit is 0 half the time and 1 half the time, because you can pair off x and 2^(n-1) XOR x. Therefore the total number of 1-bits is half the total number of bits, QED.) |
|
|