5 ms·

Right. So the true answer is log2((32*31*30*29)/(4*3*2) + (32*31*30)/2 + (32*31) + (32*31)/2) = 15.675 which is still smaller than 16.

• yorwba 9y ago
  Are you sure you don't mean log2((32*31*30*29)/(4*3*2*1) + (32*31*30)/(3*2*1) + (32*31)/(2*1) + 32/1) = 15.34 using the number of sets of values from {0, 2^5-1} with at most 4 elements? If on the other hand you want to store exactly 4 values, possibly with duplicates (while still ignoring order), you need to count multisets ( https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_multisets https://en.wikipedia.org/wiki/Bag_(mathematics)#Counting_mul... ) log2( (35*34*33*32)/(4*3*2*1) ) = 15.676
  • pishpash 9y ago
    The second answer, 15.676, is the correct one. It can also be arrived at by: log2(32C4 + 32C3 * 3 + 32C2 * 3 + 32C1)
    • bubblethink 9y ago
      I followed the original link as well as this calculation. Why not use this to map them directly (instead of breaking it into 12 bits and 4 bits) ? We'll just have some unused headroom in 16 bits. This would seem more natural than thinking of the 12 + 4 solution.
      • bonzini 9y ago
        It uses more memory.
    • bonzini 9y ago
      What the parent message did is: log2(32+4-1 C 4), because the number of k-sized combinations of n objects with repetitions is (n+k-1)Ck. One way to prove it is that you sort the objects (so you can establish an order among the objects in the combination) and add k-1 dummy objects for "the second is the same as the first, the third is the same as the second,..., the last is the same as the penultimate".