二进制字符串中的反转

Inversions in a binary string

一个长度为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

很简单的循环函数。 假设我们知道 n-1 的答案。 在所有前面的序列之后，我们添加 0 或 1 作为第一个字符。

如果我们添加 0 作为第一个字符，这意味着反转计数不会改变：因此答案将与 n-1 相同。

如果我们添加 1 作为第一个字符，这意味着反转计数将与以前相同，并且将在所有先前序列中添加等于 0 计数的额外反转。

长度为 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)

这个问题看起来像是作业，这就是为什么让我省略细节的原因。您可以：

  1. 以循环方式解决问题（参见 Толя 的回答）
  2. 构造并求解特征方程，得到闭式的解，其中包含一些任意常数（c1、c2、... , cn);事实上，您只会得到 一个 未知常数。
  3. 将一些已知的解（如f(1) = 0、f(3) = 6）代入公式，求出所有未知系数

你应该得到的最终答案是

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

其中 ** 表示提升到权力（2**(n-3) 是 2 在 n-3 权力）。如果你不想处理递归之类的东西，你可以通过 induction.

证明公式