精华内容
下载资源
问答
  • 一、组合恒等式 ( 变下项求和 ) 变系数求和 1 、 二、组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 + 求导 ) 、 三、组合恒等式 ( 变下项求和 ) 变系数求和 2 、 四、组合恒等式 ( 变下项求和 ) 变...





    一、组合恒等式 ( 变下项求和 ) 变系数求和 1



    组合恒等式 ( 变下项求和 ) 变系数求和 :

    k=0nk(nk)=n2n1\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}


    kk 随着求和的项不断变化 , 变化范围 00 ~ nn ;



    1. 证明方法 :

    • 二项式定理 : 使用 二项式定理 + 求导 可以证明该组合恒等式 ;
    • 组合恒等式代入 : 使用 已知组合恒等式代入 , 消去变系数 ; 即使用之前的 33 个递推式 , 简单和 , 交错和 , 55 个组合恒等式 代入 ;




    二、组合恒等式 ( 变下项求和 ) 变系数求和 1 证明 ( 二项式定理 + 求导 )



    使用二项式定理 + 求导方法证明下面的恒等式 :

    k=0nk(nk)=n2n1\sum_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}



    二项式定理 : (x+y)n=k=0n(nk)xkynk(x + y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k}


    1. y=1y = 1 时有该情况 : (x+1)n=k=0n(nk)xk(x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k , 上述公式中 , 将常数项 k=0k= 0 的情况单独计算出来 , (n0)x0=1\dbinom{n}{0}x^0 = 1 , 计算过程如下 :

    (x+1)n=k=0n(nk)xk=(n0)x0+k=1n(nk)xk=1+k=1n(nk)xk(x +1)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k = \dbinom{n}{0}x^0 + \sum\limits_{k=1}^n \dbinom{n}{k}x^k = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k


    2. 引入求导 : 要在加和式 k=1n(nk)xk\sum\limits_{k=1}^n \dbinom{n}{k}x^k 中出现 kk 变化数 , 需要对 xx 进行求导 ;


    这里直接对 (x+1)n=1+k=1n(nk)xk(x +1)^n = 1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k 等式两边进行求导 ;

    ( 1 ) 左边组合式 ( 根据下面的幂函数导数公式 计算 ) : (x+1)n(x +1)^n 导数为 n(x+1)n1n(x+1)^{n-1}

    ( 2 ) 右边组合式 ( 根据下面的 导数运算规则 和 幂函数导数公式 计算 ) : 1+k=1n(nk)xk1+ \sum\limits_{k=1}^n \dbinom{n}{k}x^k 导数为 , 11 的导数 为 00 , 加上 k=1n(nk)xk\sum\limits_{k=1}^n \dbinom{n}{k}x^k 的导数 k=1nk(nk)xk1\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1} , 最终结果是 k=1nk(nk)xk1\sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

    ( 3 ) 左右两边的导数是相等的 :

    n(x+1)n1=k=1nk(nk)xk1n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

    幂函数求导 : ( 很重要 )

    • 原函数 : y=xny = x^n
    • 对应导数 : y=nxn1y' = nx^{n-1}\

    /
    常数的导数是 00 ;
    /
    导数四则运算 : (u±v)=u±v(u \pm v)' = u' \pm v'
    /
    参考 : 导数 - 百度百科



    3. 求导后的结果如下 :

    n(x+1)n1=k=1nk(nk)xk1n(x+1)^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}x^{k-1}

    假设求导结果中的 x=1x = 1 , 有如下结果 :

    n2n1=k=1nk(nk)n2^{n-1} = \sum\limits_{k=1}^n k \dbinom{n}{k}

    k=0k = 0 时 , 有 k(nk)=0×(n0)=0k \dbinom{n}{k} = 0 \times \dbinom{n}{0} = 0 ,

    因此加上 k=0k=0 的情况 , 即 kk00 开始累加 , 也不影响上述结果 :

    n2n1=k=0nk(nk)n2^{n-1} = \sum\limits_{k=0}^n k \dbinom{n}{k}





    三、组合恒等式 ( 变下项求和 ) 变系数求和 2



    组合恒等式 ( 变下项求和 ) 变系数求和 :

    k=0nk2(nk)=n(n+1)2n2\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}


    kk 随着求和的项不断变化 , 变化范围 00 ~ nn ;


    证明方法 :

    • 二项式定理 : 使用 二项式定理 + 求导 可以证明该组合恒等式 ;
    • 组合恒等式代入 : 使用 已知组合恒等式代入 , 消去变系数 ; 即使用之前的 33 个递推式 , 简单和 , 交错和 , 55 个组合恒等式 代入 ;




    四、组合恒等式 ( 变下项求和 ) 变系数求和 2 证明 ( 使用已知恒等式证明 )



    使用 已知恒等式 证明下面的恒等式 :

    k=0nk2(nk)=n(n+1)2n2\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}



    1. 已知恒等式列举 :

    • ① 递推式 11 : (nk)=(nnk)\dbinom{n}{k} = \dbinom{n}{n-k}
    • ② 递推式 22 : (nk)=nk(n1k1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}
    • ③ 递推式 33 帕斯卡 / 杨辉三角公式 : (nk)=(n1k)+(n1k1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}
    • ④ 变下项求和 1 简单和 : k=0n(nk)=2n\sum_{k=0}^{n}\dbinom{n}{k} = 2^n
    • ⑤ 变下项求和 2 交错和 : k=0n(1)k(nk)=0\sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0


    2. 变下限 : k=0nk2(nk)\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} 开始推导 , k=0k=0 时 , k2(nk)=0k^2 \dbinom{n}{k} = 0 , 可以忽略 , 这里可以从 11 开始累加 ;


    k=0nk2(nk)=k=1nk2(nk)\sum\limits_{k=0}^{n} k^2 \dbinom{n}{k} = \sum\limits_{k=1}^{n} k^2 \dbinom{n}{k}


    使用 (nk)=nk(n1k1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} 恒等式替换其中的 (nk)\dbinom{n}{k} :


    =k=1nk2nk(n1k1)= \sum\limits_{k=1}^{n} k^2 \dfrac{n}{k} \dbinom{n - 1}{k - 1}


    3. 消去变系数 : 消去一个 kk 后 , 变成如下公式 :

    =k=1nkn(n1k1)=\sum\limits_{k=1}^{n} k n \dbinom{n - 1}{k - 1}


    4. 常量外提 : 其中的 nn 相对于求和来说 , 是一个常量 , 可以提到求和符号之外 :


    =nk=1nk(n1k1)=n\sum\limits_{k=1}^{n} k \dbinom{n - 1}{k - 1}


    5. 变形及拆解 : 在组合数中有 (n1k1)\dbinom{n - 1}{k - 1} , 为了与 k1k-1 进行匹配 , 这里将 kk 进行变形 , k=(k1)+1k = (k - 1) + 1 , 可以凑出一个 k1k-1 来 ;


    =nk=1n[(k1)+1](n1k1)=n\sum\limits_{k=1}^{n} [( k - 1 ) +1] \dbinom{n - 1}{k - 1}


    利用求和公式 , 将上述式子拆解成两个和式 ,


    =nk=1n(k1)(n1k1)+nk=1n(n1k1)=n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}


    6. 第一个组合式转换 : nk=1n(k1)(n1k1)n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} 求和 ,

    k=1k=1 时 , 组合数的下项 , 加和式中的系数 k1=0k-1=0 , 将 kk 作下限的变换 , kk 取值是 11 ~ nn , 则 k1k-1 取值是 00 ~ (n1)(n-1) ,

    相当于使用 k=k1k' = k-1 替代之前的 kk , kk' 取值范围 00 ~ (n1)(n-1) ,

    因此最终可以变为 nk=0n1(k)(n1k)n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'}

    使用 k=0nk(nk)=n2n1\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1} 组合恒等式 ,

    上述 k=0n1(k)(n1k)\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} 的结果是 (n1)2n2(n-1)2^{n-2} ,

    前面乘以 nn , 最终的 nk=0n1(k)(n1k)=n(n1)2n2n\sum\limits_{k'=0}^{n-1} ( k' ) \dbinom{n - 1}{k'} = n(n-1)2^{n-2}


    7. 第二个组合式转换 : nk=1n(n1k1)n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1} 该组合式中 kk 取值是 11 ~ nn , 将 kk 变为从 00 开始 , 即使用 k=k1k' = k-1 替代 kk ,

    则有 nk=0n1(n1k)n\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'} , 该求和可以转变成基本求和 ,

    使用 简单和 组合恒等式 k=0n(nk)=2n\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n ,

    k=0n1(n1k)\sum\limits_{k'=0}^{n-1} \dbinom{n - 1}{k'} 就是 2n12^{n-1} , 前面乘以 nn , nk=1n(n1k1)n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1} 就是 n2n1n2^{n-1}


    =nk=1n(k1)(n1k1)+nk=1n(n1k1)=n\sum\limits_{k=1}^{n} ( k - 1 ) \dbinom{n - 1}{k - 1} + n\sum\limits_{k=1}^{n} \dbinom{n - 1}{k - 1}

    =n(n1)2n2+n2n1=n(n-1)2^{n-2} + n2^{n-1}

    =n(n1)2n2+n2×2n2=n(n-1)2^{n-2} + n 2 \times2^{n-2}

    =n(n+1)2n2=n(n+1)2^{n-2}


    总结 :
    先利用 递推式 , 消掉变系数 kk ,
    将求和的每个式子凑成基本求和公式 , 或 已知求和公式 ,
    然后进行求和变限 , 即使用 k=k1k' = k-1 替换 kk ,
    通过上述技巧 , 完成证明 ;

    展开全文
  • 一、组合恒等式 ( 递推式 ) 、 二、组合恒等式 ( 变下项求和 ) 简单和 、 二、组合恒等式 ( 变下项求和 ) 交错和 、





    一、组合恒等式 ( 递推式 )



    组合恒等式 ( 递推式 ) :

    1 . (nk)=(nnk)\dbinom{n}{k} = \dbinom{n}{n-k} , 作用 : 化简

    2 . (nk)=nk(n1k1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1} , 作用 : 求和时消去变系数 ;

    3 . (nk)=(n1k)+(n1k1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} , 作用 : 求和时拆项 , 将一个组合数拆分成两项之和 , 或两项之差 , 然后合并 ;





    二、组合恒等式 ( 变下项求和 ) 简单和



    简单和 :

    k=0n(nk)=2n\sum_{k=0}^{n}\dbinom{n}{k} = 2^n


    1. 证明 ( 二项式定理 ) : 通过二项式定理可以证明 , (x+y)n=k=0n(nk)xkynk(x + y)^n = \sum\limits_{k=0}^n \dbinom{n}{k}x^k y^{n-k} 中 , 使 x=y=1x=y=1 , 即可得到上面的 简单和 组合恒等式 ;



    2. 证明 ( 组合分析 ) : 将等号 左边右边 各看做某个 组合计数问题的解 ,

    ( 1 ) 左侧 组合计数问题 : k=0n(nk)\sum\limits_{k=0}^{n}\dbinom{n}{k} 可以看做 nn 个元素的所有子集个数 ; ( 这也是集合中的幂集个数 ) ;

    这是分类计数 , 最后将所有的类个数相加 , 即包含 00 个元素个数 , 包含 11 个元素子集个数 , \cdots , 包含 nn 个元素子集个数 ;


    ( 2 ) 右侧 组合计数问题 : nn 个元素中 , 每个元素都有 放入子集中 , 不放入子集中 , 两种选择 , 那么所有元素的选择有 , 2×2××2n=2n\begin{matrix} \underbrace{ 2 \times 2 \times \cdots \times 2 } \\ n 个\end{matrix} = 2^n 个选择 , 这是 分步计数的乘法法则 ,

    这是分步计数 , 最后将所有的分步结果相乘 , 即第 11 个元素选择个数 , 第 22 个元素选择个数 , \cdots , 第 nn 个元素选择个数 ;



    3. 应用场景 : 在序列求和场景使用 ;





    二、组合恒等式 ( 变下项求和 ) 交错和



    交错和 :

    k=0n(1)k(nk)=0\sum_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0


    1. 证明 ( 二项式定理 ) : 通过二项式定理可以证明 , (x+y)n=k=0n(nk)xkynk(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k} 中 , 使 x=1,y=1x= -1 , y=1 , 即可得到上面的 交错和 组合恒等式 ;



    2. 证明 ( 组合分析 ) : 将等号 左边右边 各看做某个 组合计数问题的解 , 完全展开上述组合数 , 这里需要先移项 , 将 kk 为奇数的情况下 , (1)k(-1)^k1-1 , 将这种情况的分项移到右边 , 就有了如下公式 :

    k=0(nk)=k=1(nk)\sum_{k=0}^{偶数} \dbinom{n}{k} = \sum_{k=1}^{奇数} \dbinom{n}{k}

    ( 1 ) 左侧 组合计数问题 : k=0(nk)\sum_{k=0}^{偶数} \dbinom{n}{k} 可以看做 nn 个元素的所有 偶数个 子集个数 ;

    ( 2 ) 右侧 组合计数问题 : k=1(nk)\sum_{k=1}^{奇数} \dbinom{n}{k} 可以看做 nn 个元素的所有 奇数个 子集个数 ;

    上述 奇数子集个数 与 偶数子集个数 是相等的 ;



    3. 应用场景 : 在序列求和场景使用 ;

    展开全文
  • 一、十一个组合恒等式 、 二、组合恒等式 证明方法 、 三、组合数 求和 ∑ 方法



    组合恒等式参考博客 :






    一、十一个组合恒等式



    1 . 组合恒等式 ( 递推式 ) :

    ( 1 ) 递推式 1 :


    (nk)=(nnk)\dbinom{n}{k} = \dbinom{n}{n-k}


    ( 2 ) 递推式 2 :


    (nk)=nk(n1k1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}


    ( 3 ) 递推式 3 ( 帕斯卡 / 杨辉三角公式 ) :


    (nk)=(n1k)+(n1k1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}



    2 . 回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数 (nk)\dbinom{n}{k} , 是下项 kk 一直在累加改变 , 具有 k=0n\sum\limits_{k=0}^{n} 累加性质 , 上项 nn 是不变的 ;


    ( 1 ) 简单和 :


    k=0n(nk)=2n\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n


    ( 2 ) 交错和 :


    k=0n(1)k(nk)=0\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0


    ( 3 ) 变下项求和 3 :


    k=0nk(nk)=n2n1\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}


    ( 4 ) 变下项求和 4 :


    k=0nk2(nk)=n(n+1)2n2\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}



    3 . 变上项求和 :


    l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}



    4 . 积 :


    l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}



    5 . 积之和 :


    ( 1 ) 组合恒等式 ( 积之和 ) 1 :


    k=0r(mk)(nrk)=(m+nr),      r=min{m,n}\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}


    ( 2 ) 组合恒等式 ( 积之和 ) 2 :


    k=0r(mk)(nk)=(m+nm)\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}





    二、组合恒等式 证明方法



    1 . 已知组合恒等式代入 : 已知的 1111 个组合恒等式代入



    2 . 二项式定理

    nn 是正整数 , 对于一切 xxyy , 有以下定理 :

    (x+y)n=k=0n(nk)xkynk(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}


    (nk)\dbinom{n}{k} 表示 nn 元集中取 kk 个元素的组合数 , 是 集合组合数 C(n,k)C(n,k) 的另一种写法 ;


    另一个常用形式 ( y=1y = 1 ) :

    (1+x)n=k=0n(nk)xk(1 + x)^n = \sum_{k=0}^n \dbinom{n}{k}x^k


    基本求和公式 ( x=y=1x = y =1 ) :

    2n=k=0n(nk)2^n = \sum_{k=0}^n \dbinom{n}{k}



    3 . 幂级数求导、积分


    幂函数求导 : ( 很重要 )

    • 原函数 : y=xny = x^n
    • 对应导数 : y=nxn1y' = nx^{n-1}

    常数的导数是 00 ;

    导数四则运算 : (u±v)=u±v(u \pm v)' = u' \pm v'


    参考 :



    4 . 归纳法

    数学归纳法 描述 一个与自然数相关的命题 P(n)P(n) ,

    根据不同的问题 , 设定 nn 最小的值 , 一般情况下从 00 开始 ,


    ( 1 ) 证明时分为以下两个步骤 :

    ① 归纳基础 : 先证明 归纳基础 , 如证明 P(0)P(0) 为真 ;

    ② 归纳步骤 : 根据 数学归纳法的种类 , 进行不同方式的证明 , 这里有 第一数学归纳法第二数学归纳法 两种归纳法 ;


    ( 1 ) 数学归纳法 :

    ① 第一数学归纳法 :P(n)P(n) 推导 P(n+1)P(n + 1)

    P(0)P(0) 为真

    假设 P(n)P(n) 为真 , 证明 P(n+1)P(n + 1) 也为真


    ② 第二数学归纳法 : 所有小于 nnP(0),P(1),,P(n1)P(0) , P(1), \cdots , P(n-1) 都为真 , 推导 P(n)P(n) 为真 ;

    P(0)P(0) 为真

    假设所有小于 nn 的自然数 kk , 命题 P(k)P(k) 都为真 , 即 P(0),P(1),,P(n1)P(0) , P(1), \cdots , P(n-1) 都为真 , 推导 P(n)P(n) 为真 ;

    符号化表示为 : P(0)P(1)P(n1)P(n)P(0) \land P(1) \land \cdots \land P(n-1) \to P(n)


    参考 : 【组合数学】组合数学简介 ( 组合思想 2 : 数学归纳法 | 数学归纳法推广 | 多重归纳思想 )



    5 . 组合分析

    使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;

    ( 1 ) 指定集合 : 指定计数是在什么样的集合中产生的 ;

    ( 2 ) 指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;

    • ① 问题 1 : 等号左侧代表的计数问题 ;
    • ② 问题 2 : 等号右侧代表的计数问题 ;

    ( 3 ) 等价说明 : 说明两个计数问题是同一个问题 ;

    参考 :



    上述证明方法 , 可以根据具体的证明要求 , 选择合适的证明方法 ;





    三、组合数 求和 \sum 方法



    针对含有组合数的式子的 求和 \sum 方法


    1 . 使用帕斯卡公式 :


    递推式 3 ( 帕斯卡 / 杨辉三角公式 ) :


    (nk)=(n1k)+(n1k1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}


    ( 1 ) 合并项 : (nk)\dbinom{n}{k} 可以规约成 (n1k)+(n1k1)\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} 之和 ;


    ( 2 ) 该递推式 , 用于拆项 :


    可以将 (nk)\dbinom{n}{k} 拆成 (n1k)+(n1k1)\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} 之和 ; 在实际使用时 , 经常遇到某些项列出后 , 有 (n1k)+(n1k1)\dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1} 形式的组合数 , 可以合并成一项 (nk)\dbinom{n}{k} ;


    ( 3 ) 也可以变形使用 , 将其中的一项 , 变成其中两项的差 ;


    (n1k)\dbinom{n - 1}{k} 拆成 (nk)(n1k1)\dbinom{n}{k} -\dbinom{n - 1}{k - 1} 之差 ;


    将 将 (n1k1)\dbinom{n - 1}{k - 1} 拆成 (nk)(n1k)\dbinom{n}{k} -\dbinom{n - 1}{k} 之差;


    在一堆求和的组合数中 , 拆分成两个数之差 , 可以抵消很多组合数 ;

    经常在大的求和公式中进行化简时使用 ;



    2 . 级数求和 :




    3 . 观察和的结果 , 使用数学归纳法证明 :


    猜想一个和的结果 , 然后使用归纳法证明 ;



    4 . 利用已知公式求和 :


    展开全文
  • 一、组合恒等式 ( 变上项求和 1 ) 、 二、组合恒等式证明方法 ( 三种 ) 、 三、组合恒等式 ( 变上项求和 1 ) 证明



    组合恒等式参考博客 :


    回顾四个变下项求和的组合恒等式 : 之前介绍的组合恒等式 中的组合数 (nk)\dbinom{n}{k} , 是下项 kk 一直在累加改变 , 具有 k=0n\sum\limits_{k=0}^{n} 累加性质 , 上项 nn 是不变的 ;

    ( 1 ) 简单和 : k=0n(nk)=2n\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n

    ( 2 ) 交错和 : k=0n(1)k(nk)=0\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0


    ( 3 ) 变下项求和 3 : k=0nk(nk)=n2n1\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}

    ( 4 ) 变下项求和 4 : k=0nk2(nk)=n(n+1)2n2\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}





    一、组合恒等式 ( 变上项求和 1 )



    变上项求和 1 :

    l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}


    上述公式中 , 组合数 (lk)\dbinom{l}{k} 中 , 下项 kk 是不变的 , 上项 ll 一直是改变的 , 其取值范围是 00 ~ nn ;


    该表达式中有若干项都是 00 :

    • l<kl < k 时 , (lk)=0\dbinom{l}{k} = 0 , 从 ll 个元素中选取 kk 个元素 , 没有方案 ;
    • l=kl = k 时 , (lk)=1\dbinom{l}{k} = 1 ;
    • l>kl > k 时 , (lk)\dbinom{l}{k} 才为大于 11 的值 ;




    二、组合恒等式证明方法 ( 三种 )



    1 . 证明方法 : 之前使用过两种证明方法 , ① 二项式定理 + 求导 , ② 使用现有组合恒等式推导 ;

    在这里使用第三类证明方法 , ③ 组合分析 , 组合分析方法是要构造一个组合计数问题 , 左边和右边都是同一个计数问题的解 ;

    2 . 组合分析方法使用 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;

    指定计数问题 : 下面两个计数问题都是同一个问题的计数 ;

    • ① 问题 1 : 等号左侧代表的计数问题 ;
    • ② 问题 2 : 等号右侧代表的计数问题 ;

    参考 : 【组合数学】二项式定理与组合恒等式 ( 二项式定理 | 三个组合恒等式 递推式 | 递推式 1 | 递推式 2 | 递推式 3 帕斯卡/杨辉三角公式 | 组合分析方法 | 递推式组合恒等式特点 ) 五、组合分析方法


    3 . 组合分析方法使用总结 : 使用组合分析方法证明组合数时 , 先指定集合 , 指定元素 , 指定两个计数问题 , 公式两边是对同一个问题的计数 ;





    三、组合恒等式 ( 变上项求和 1 ) 证明



    现在开始构造选取问题 :


    1 . 指定集合 : 假定有 n+1n+1 个元素的集合 , 记作 S={a1,a2,,an+1}S = \{ a_1 , a_2 , \cdots , a_{n+1} \} ,


    2 . 指定等号右侧的计数问题 : 从上述集合 SS 中 , 选取 k+1k+1 个元素的子集 , 选择方法的个数是 (n+1k+1)\dbinom{n + 1}{k+1} 个 ;


    3 . 指定等号左侧的计数问题 : 等号左侧是 l=0n(lk)\sum\limits_{l=0}^{n} \dbinom{l}{k} ;

    计数问题类型确定 ( 分类选取 ) : 组合式中存在 和号 \sum , 说明该计数问题采用了 分类计数原理 , 对应加法法则 ; 该计数问题肯定是分类选取 ;


    SS 集合 , 从 n+1n+1 个元素中选取 k+1k+1 个元素 ;


    ( 1 ) 第 11 , 指定某个特定元素 a1a_1 , 在子集中必须含有 a1a_1 , 则只能从剩余的 nn 个元素中选取 kk 个 , 方案数是 (nk)\dbinom{n}{k} ;


    ( 2 ) 第 22 , 与 第 11 类不重叠 ,
    不含 a1a_1 , 但是必须含有 a2a_2 ,
    不含 a1a_1 那就要从 nn 个元素中选取 ( 从 n+1n+1 个元素中去掉一个 ) ,
    必须含有 a2a_2 ( 从 nn 个元素中再去掉一个, 即 n1n - 1 个 ) , 那么就要从 n1n-1 个元素中选取 kk 个元素 ,
    最终结果是 (n1k)\dbinom{n-1}{k}


    ( 3 ) 第 33 , 与 第 1,21,2 类不重叠 ,
    不含 a1,a2a_1, a_2 , 但是必须含有 a3a_3 ,
    不含 a1,a2a_1, a_2 那就要从 n1n-1 个元素中选取 ( 从 n+1n+1 个元素中去掉 22 个 , 即 n1n-1 ) ,
    必须含有 a3a_3 ( 从 n1n-1 个元素中再去掉一个, 即 n2n - 2 个 ) , 那么就要从 n2n-2 个元素中选取 kk 个元素 ,
    最终结果是 (n2k)\dbinom{n-2}{k}


    \vdots


    ( 4 ) 第 n+1n + 1 , 与 第 1,2,,n1,2, \cdots , n 类不重叠 ,
    不含 a1,a2,a3,,ana_1, a_2 , a_3 , \cdots , a_n , 但是必须含有 an+1a_{n+1} ,
    不含 a1,a2,a3,,ana_1, a_2 , a_3 , \cdots , a_n 那就要从 11 个元素中选取 ( 从 n+1n+1 个元素中去掉 nn 个 , 即 11 ) ,
    必须含有 an+1a_{n+1} ( 从 11 个元素中再去掉一个, 即 00 个 ) , 那么就要从 00 个元素中选取 kk 个元素 ,
    最终结果是 (0k)\dbinom{0}{k}


    5 . 在上述两个计数问题都是同一个计数问题 , 都是从 n+1n+1 个元素中选取 k+1k+1 个元素 ;

    展开全文
  • 组合恒等式

    2020-12-11 22:46:45
    组合恒等式 常用组合数计算公式 (转载)组合恒等式
  • 一、组合恒等式回顾 ( 8个 ) 、 二、组合恒等式 ( 积 ) 、 三、组合恒等式 ( 积 ) 证明 、 四、组合恒等式 ( 积 ) 用途 、
  • 一、组合恒等式 ( 积之和 ) 1 、 二、组合恒等式 ( 积之和 ) 1 证明 、 三、组合恒等式 ( 积之和 ) 2 、 四、组合恒等式 ( 积之和 ) 2 证明
  • 一、二项式定理 、 二、组合恒等式 ( 递推式 1 ) 、 三、组合恒等式 ( 递推式 2 ) 、 四、组合恒等式 ( 递推式 3 ) 帕斯卡 / 杨辉三角公式 、 五、组合分析方法 、 六、递推式组合恒等式特点
  • 组合恒等式1 五个基本的组合恒等式 基础与简单例子四个基本的组合恒等式应用四个基本恒等式计算组合恒等式的例题应用四个基本恒等式证明组合恒等式的例题 组合恒等式是组合学中一个非常有趣但也十分具有挑战性的小...
  • 组合恒等式2 五个基本的组合恒等式 复杂的例题使用两个数列的递推关系证明恒等式证明相反数与自身相等以说明恒等式为0组合数的倒数的裂项数学归纳法 这一讲继续讨论用五个基本的组合恒等式证明组合恒等式的方法。先...
  • 构造组合模型巧证组合恒 等式 构造组合模型巧证组合恒等式 证明组合恒等式一般是利用组合数的 性质数学归纳法二项式定理等通过一 些适当的计算或化简来完成但是很多组 合恒等式也可直接利用组合数的意义来证 明即...
  • 本文将利用格点路径的计数方法及生成函数法,推导一些组合恒等式.这些恒等式推广了Breusch,Rohatgi的结果. 文中的字母,如无另加声明,均表示自然数. 平面上以整数为坐标的点称为格点,以格点(a,b)为始点,以(c,d)为终点...
  • 数学奥林匹克辅导丛书-组合恒等式
  • 组合恒等式感兴趣的人可以下载看看。找了好长时间才找到。。
  • 组合恒等式在组合数学中占有重要地位,它有多种证法。本文舍弃了它的常见证法,另外运用了求导法则和概率方法对几个重要的组合恒等式给出了直观简洁的证明。
  • 分别用复变函数论、组合论和图论三种方法证明了与数nn-2的组合计数问题相关的一个组合恒等式,并给出该恒等式在图论、超平面配置等一些组合问题上的应用.
  • 给出了一个组合恒等式的代数证明,它比组合方法的证明简洁清晰。
  • 设二阶矩阵得到矩阵的次中的元素己11,己12,己21,姚2与a,b,c,泛间关系式,给出a,及c,d-些特殊值,利用这些关系和二项式定理得到一些有趣的组合恒等式
  • 通过发生函数的方法并结合积分理论,得到了关于广义Fibonacci组合恒等式,并对所提出的定理进行了证明。
  • 组合恒等式在组合数学中占有重要的地位,它有多种证法,运用集合论的观点,求导法则和概率方法对几个重要的组合等式给出了直观简洁的证明.
  • sz组合恒等式.pdf

    2019-09-13 08:45:59
    关于ACM竞赛的一些常用用组合数学的公式,以及每种组合数学恒等式的证明过程、应用。
  • 组合恒等式 组合分析法求得 方法: 求导,积分,二项式,组合分析 非降路径
  • 构造了以Fibonacci数为系数的一个指母生成函数,通过比较该指母生成函数与其指数组合表示形式k次幂的对应函数,从而揭示了Fibonacci数之间的内在联系,得到了一组有趣的Fibonacci数的组合恒等式
  • 组合恒等式3 母函数与形式幂级数的运算母函数与母函数方法形式幂级数 前两讲介绍了一些用基本恒等式证明组合恒等式的技巧,但这些也仅仅只是技巧,在证明过程中的某一步能起到关键作用,不能提供具有一般性的证明...
  • 组合恒等式7 组合变换的互逆公式双重求和可以交换次序互逆公式的证明应用互逆公式证明组合恒等式 类似离散序列的Z变换,我们也可以定义以组合数为系数的组合变换,一个直观的例子是 bk=∑i=0k(−1)iCkiaib_k = \sum_...
  • 已知从n个物品中取出m个,则存在一个组合恒等式。 C(n, m)=C(n, n-m)=C(n-1, m-1)+C(n-1,m) 其中C(n,0) = 1 求:从5取3 和 10 取 4 方法一:递归 def CombNum(m, n): if n==0 or m==n: return 1 ...
  • 组合恒等式证明中几个常用变量转移技巧 本文介绍的技巧来自Ronald L.Graham 等的《具体数学》edition 2. 在证明组合部分和相关恒等式时,求和变量所在的位置对于计算影响至关重要,具体情况可以分为两类: 组合数的...
  • 一、多项式系数 、 二、常见的组合计数

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,919
精华内容 2,367
关键字:

组合恒等式