Search code examples
stringalgorithmbinaryinversion

Inversions in a binary string

How many inversions are there in a binary string of length n ?

For example , n = 3
000->0
001->0
010->1
011->0
100->2
101->1
110->2
111->0
So total inversions are 6
Solution

  • The question looks like a homework, that's why let me omit the details. You can:

    1. Solve the problem as a recurrency (see Толя's answer)
    2. Make up and solve the characteristic equation, get the solution as a close formula with some arbitrary constants (c1, c2, ..., cn); as the matter of fact you'll get just one unknown constant.
    3. Put some known solutions (e.g. f(1) = 0, f(3) = 6) into the formula and find out all the unknown coefficients

    The final answer you should get is 

     f(n) = n*(n-1)*2**(n-3)

    where ** means raising into power (2**(n-3) is 2 in n-3 power). In case you don't want to deal with recurrency and the like stuff, you can just prove the formula by induction.