柒葉灬 的博客

柒葉灬 的博客

数学推导(个人笔记10)

posted on 2018-09-18 20:38:38 | under 数学 |

$C_n^1*1+C_n^2*2+C_n^3*3...+C_n^n*n=?$


原式=ans

    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