美文网首页
组合数的应用

组合数的应用

作者: madao756 | 来源:发表于2020-05-08 19:55 被阅读0次

0X00 组合恒等式

首先我们来学一些组合恒等式

  • C_{n}^{k} = C_{n}^{n-k}
  • C_{n}^{k} = C_{n-1}^{k} + C_{n-1}^{k-1}
    • 当 k = n - 1 时
    • C_{m}^{m} + C_{m}^{m-1} = C_{m+1}^{m}
  • C_{n}^{0} + C_{n}^{1} + ... + C_{n}^{n} = 2 ^ n
  • C_{n}^{0} - C_{n}^{1} + ... + (-1)^nC_{n}^{n} = 0

0X01 隔板法

隔板法求等式的正整数解的数量

求：x_1 + x_2 + ... + x_k = n 的正整数解的数量

相当于有 n 个小球， n - 1 个空隙。在 n-1 个空隙里面插入 k - 1 个板子所以答案是 C_{n-1}^{k-1}

隔板法求不等式正整数解的数量

求：x_1 + x_2 + ... + x_k \leq n 的正整数解的数量

同样也是有 n 个小球，每个解 x_i \geq 1 相当于有 n 个空隙（包括最后一个小球的最后），再往这 n 个空隙里面插入 k 个板子就是最后的答案 C_{n}^{k}

可能这么说，比较抽象，我举一个具体的例子假设 n = 6, k = 3 如下面的小球

⚪⚪⚪⚪⚪⚪

现在我用「隔板法」画出一个解

⚪⚪|⚪|⚪|⚪⚪

除了第一个解，每个板子之间就是一个解。而最后剩下的部分， 因为是 \leq 所以是可以不要的，也可以全部要就像这样：

⚪⚪|⚪|⚪⚪⚪|

隔板法的变形

  • 每一个解 x_i \geq 0

上面的每一个解都是 x_i \geq 1, 我们需要做的就是将当前这种情况，转换成上面的情况

令 y_i = x_i + 1 这样 y_i \geq 1 而等式右边由 n 变化为 n+k

  • 区间求解

现在我们求的是 l \leq x_1 + x_2 + ... + x_k \leq r 解的数量，同样我们可以把它转换成：0 \leq y_1 + y_2 + ... + y_k \leq r - l

0X02 重要的卡特兰数

一旦看到有这么一个序列，它由两种元素组成，且一部分的个数大于等于另一部分的个数，就得想到卡特兰数

这么说可能比较抽象，举个具体的例子：满足条件的01序列

它的推导

得放在一个坐标系中，不具体叙述了记住结论，到 B 的方案数量 = C_{m+n}^{m} - C_{m+n}^{m+1}

相关文章

  • 组合数的应用

    0X00 组合恒等式 首先我们来学一些组合恒等式 当 k = n - 1 时 0X01 隔板法 隔板法求等式的正整...

  • Oracle 集合处理sql

    /根据一组坐标+半径+生成的坐标精度生成一组圆形集合数据/SELECT SDO_UTIL.CIRCLE_POLYG...

  • python_列表

    python 列表：list 列表：可以存储一组数据的类型；组合数据类型 创建列表 name=list() ...

  • 丰田近日推出探索混合动力车型的AR应用

    丰田GB联合数字代理商Brand Width推出了一款基于iPad体验的AR应用。 本款AR应用旨在让消费者自由探...

  • Python学习笔记（六）

    第六章 组合数据类型 组合数据类型概述 计算机不仅对单个变量表示的数据进行处理，更多情况，计算机需要对一组数据进行...

  • GEOquery 下载 GEO 数据

    前言 NCBI Gene Expression Omnibus（基因表达综合数据库，GEO）公开了很多高通量基因组...

  • 计算组的多层应用

    计算组1应用生效： 计算组2应用生效： 计算组1，2共同应用生效，说明，如果某一个计算组中引用了度量，别的计算组中...

  • [iOS-Vendor] Mantle

    结合数据层返回的 JSON 数据，Mantle 在基于 MVC 模式的应用的 Model 层中发挥了重要作用，包括...

  • 生成排列、组合数

    排列组合数 组合数 生成组合数举例：比如有一个数组int arr[3] = {1,4,8}，生成组合数就是要生成{...

  • 应用组

    技术管理委员会： a)负责提出技术路线、技术规划； b)负责公司重大技术项目的立项论证和总体方案论证； c)负责产...

网友评论

      本文标题：组合数的应用

      本文链接：https://www.haomeiwen.com/subject/uguqnhtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|组合数的应用|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！