跳到内容

顺着知识,继续探索

组合数学

围绕基本计数、计数结构、分拆与对称理解概念与联系。先建立知识结构,视频讲解按审核情况逐步补充。

前置知识与跨科联系

  • 群作用

    群作用把群元素赋为集合变换,并与群运算相容。

    视频讲解待补充

基本计数

  • 组合计数

    利用互斥分类求和、逐步选择相乘、等重数除法或双射计数有限结果。须核对分类是否互斥、重数是否固定;选择数量相乘不是概率独立性假设。

    4 条审核资源
  • 排列

    排列记录顺序。n 个不同对象的全排列有 n! 种;重复且不可区分的对象需要除去组内交换造成的重数。须说明各组数量、是否用尽所有对象,以及旋转是否视为不同排列。

    3 条审核资源
  • 组合

    从 n 元集合中无序选取 k 个不同元素,要求整数 0≤k≤n。每个所选子集对应 k!(n−k)! 个全排列;允许重复选取时是另一类问题,必须另说明条件。

    4 条审核资源
  • 抽屉原理

    对象数多于容器数时,至少一个容器含多个对象。

    视频讲解待补充

计数结构

  • 容斥原理

    容斥原理以交集计数的交替和修正有限集合并集中的重复计数。

    视频讲解待补充
  • 二项式定理

    二项式系数给出两项和的非负整数次幂展开。

    视频讲解待补充
  • 递推关系

    递推关系用较早项及初始数据规定数列后续项。

    视频讲解待补充
  • 生成函数

    生成函数把数列编码为级数系数,以代数运算处理计数及递推。

    视频讲解待补充

分拆与对称

  • 整数分拆

    整数分拆把正整数写为不计顺序的正整数之和。

    视频讲解待补充
  • 卡塔兰数

    卡塔兰数计数多类递归结构,包括配对括号串。

    视频讲解待补充
  • 伯恩赛德引理

    有限群作用的轨道数等于各群元素不动点数的平均值。

    视频讲解待补充
  • 拉姆齐理论

    足够大的结构在适当染色条件下必出现指定规则子结构。

    视频讲解待补充

课程范围参考