Sum of Inversions in Bitmask of Length N

Revision en1, by vamaddur, 2017-07-20 14:14:14

Given a positive integer N, calculate the sum of inversions in every bitmask of length N.

For example, if N = 2, our masks are 00 (0 inversions), 01 (0 inversions), 10 (1 inversion), and 11 (0 inversions). We output 1.

For example, if N = 3, our masks are 000 (0 inversions), 001 (0 inversions), 010 (1 inversion), 011 (0 inversions), 100 (2 inversions), 101 (1 inversion), 110 (2 inversions), and 111 (0 inversions). We output 0+0+1+0+2+1+2 = 6.

How can I do this efficiently?

Please help, and thanks in advance!

Tags combinatorics, bitmask

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English vamaddur 2017-07-20 14:16:31 2 Tiny change: '+1+0+2+1+2 = 6.\n\nH' -> '+1+0+2+1+2+0 = 6.\n\nH'
en1 English vamaddur 2017-07-20 14:14:14 565 Initial revision (published)