Inversions in a binary string

Question

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

Answer 1

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.

Answer 2

It is easy recurrent function. Assume that we know answer for n-1. And after ato all previous sequences we add 0 or 1 as first character.

if we adding 0 as first character that mean that count of inversions will not be changed: hence answer will be same as for n-1.

if we adding 1 as first character that mean count of inversions will be same as before and will be added extra inversion equals to count of 0 into all previous sequences.

Count of zeros ans ones in sequences of length n-1 will be:

(n-1)*2^(n-1)

Half of them is zeros it will give following result

(n-1)*2^(n-2)

It means that we have following formula:

f(1) = 0
f(n) = 2*f(n-1) + (n-1)*2^(n-2)