逆序对

有两种方法理解，但结论都是一样的f(n) = 2^(n-3) * n * (n-1)，这里只写一种，另一种就是大佬们的组合数学，前面很多人写，这里就不赘述

我们很容易知道f(n)的数值可分为两方面

一：f(n-1)也就是上一个的个数，因为其实就是在n-1的基础上在其前面加0或1，也就说原来的次数就变成了2倍，也就是2*f(n-1)

二：在n-1的前面新加一个1产生的影响，不难发现就是n-1的所有的0的个数，设为g(n-1)

g(n) = n*2^(n-1), 就是所有串1和0的总和除以2.

这里就可以推出来f(n) = g(n-1) + 2*f(n-2)，大部分人都可以推到这一步，其实再展开一下就行了

下面是我手推的