string - バイナリ文字列の反転

Question

長さ 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

簡単なリカレント機能です。n-1 の答えがわかっているとします。そして、前のすべてのシーケンスの後に、最初の文字として 0 または 1 を追加します。

最初の文字として 0 を追加すると、反転の数が変更されないことを意味します。したがって、答えは n-1 の場合と同じになります。

最初の文字として 1 を追加すると、反転の数は以前と同じになり、前のすべてのシーケンスに 0 の数に等しい追加の反転が追加されます。

長さのシーケンス内の 0 と 1 の数は次のn-1ようになります。

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

それらの半分はゼロであり、次の結果が得られます

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

これは、次の式があることを意味します。

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