数学推导（个人笔记10）
柒葉灬
2018-09-18 20:38:38
## $C_n^1*1+C_n^2*2+C_n^3*3...+C_n^n*n=?$
--------
原式=ans
```cpp
for(int i=0;i<(1<<n);i++){
int tmp=i;
while(tmp){
ans++;
tmp&=tmp-1;
}
}
```
------------
czj的推导：
因为 $ C_n^i = C_n^{n-i} $
所以，原式可化简成：
$$ C_n^1*1+C_n^2*2+C_n^3*3...+C_n^1*(n-1)+C_n^0*n $$
可以合并，
$$ C_n^1*n+C_n^2*n+..+C_n^{n/2}*n$$
$$ (C_n^0+C_n^1+C_n^2+..+C_n^{n/2})*n$$
$$ \frac{C_n^0+C_n^1+C_n^2+...+C_n^n}{2}*n $$
$$ \frac{2^n}{2}*n $$
$$ n*2^{n-1} $$
--------
2469c的推导:
我们可以算每一个位置被取的情况有多少种，显然，有 $2_n^{n-1}$ 的情况，每个数的贡献都是 $2_n^{n-1}$ 所以答案就是 $ n*2_n^{n-1} $.
--------
123hei（最弱的我）的推导：
设 $ f(x) $ 是 $n=x$ 的答案
我们设第 $x$ 位不取，则贡献是
$$f(x-1)$$
若 $x$ 位取，则贡献是
$$f(x-1)+2^{x-1}$$
得到了递推式子：
$$ f(x)=f(x-1)*2+2^{x-1} $$
其中 $ f(1)=1$
慢慢拆开
$$ f(x)=f(x-2)*4+2^{x-1}*2 $$
$$ f(x)=f(x-3)*8+2^{x-1}*3 $$
$$ \vdots $$
可以发现：
$$ f(x)=f(x-i)*2^i+2^{x-1}*i $$
把 $ f(1)=1 $ 带入
$$ f(x)=f(1)*2^{x-1}+2^{x-1}*(x-1) $$
$$ f(x)=2^{x-1}*x $$
----
END