Menu
翘楚小站
  • 主页
  • 小项目
  • 算法
  • 摄影
翘楚小站

组合数

Posted on 2019年11月14日2019年11月14日 by WonderBoy

通项公式

\tbinom{n}{m} = \frac{m!}{(m-n)!n!}

递推式

三角递推式(适用于求多个组合数)

\tbinom{n}{m} = \tbinom{n}{m-1} + \tbinom{n-1}{m-1}

c++代码

void initC(int m)
{
    // C[m][n] 表示 m中选n个
    for (int i = 0; i <= m; i++)
        C[i][0] = 1;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= i; j++)
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}

打表如下

http://static.xzzhangqiaochu.top/images/combination0.jpg

线性递推式(适用于求单个组合数)

\tbinom{n}{m} = \frac{m-n+1}{n} \tbinom{n-1}{m}

c++代码

int C(int m, int n) { // 表示 m中选n个
    if (n > m)
        return 0;
    int ans = 1;
    for (int i = 1; i <= n; i++)
        ans = 1LL * ans * (m-i+1) / i;
    return ans;
}

求和公式

公式一

\sum_{i=n}^m \tbinom{n}{i} = \tbinom{n+1}{m+1}

可结合三角形递推公式理解

以 m=4,n=1 为例

http://static.xzzhangqiaochu.top/images/combination1.png

公式二

\sum_{i=0}^n \tbinom{i}{i+k} = \tbinom{n}{n+k+1}

以 k=2,n=2 为例

http://static.xzzhangqiaochu.top/images/combination2.png

  • 信息学
  • 数学
  • 发表评论 取消回复

    电子邮件地址不会被公开。 必填项已用*标注

    标签

    Arduino CSP DIY NOIP python tensorflow 一中文创 二分 人工智能 信息学 动态规划 图论 徐州一中 摄影 撷秀极客社区 数学 数论 最短路 树 模拟 洛谷 电子 短片 航拍 递归

    分类目录

    文章归档

    近期评论

    • 王清筠发表在《【徐州一中】再一次出发》
    • 王清筠发表在《测绘伏安特性曲线(I-U图像)》
    • xzqiaochu发表在《测绘伏安特性曲线(I-U图像)》
    • xzqiaochu发表在《测绘伏安特性曲线(I-U图像)》
    • 晨鹤发表在《测绘伏安特性曲线(I-U图像)》

    友情链接

    清筠小站
    晨鹤小站(。・∀・)ノ゙

    ©2021 翘楚小站 | 苏ICP备18005311号 | Powered by WordPress & Superb Themes