组合数学

• 分割立方体 - 蓝桥云课 (lanqiao.cn)
• 挑选子串 - 蓝桥云课 (lanqiao.cn)
• 糊涂人装信 - 蓝桥云课 (lanqiao.cn)
• 战斗吧N皇后 - 蓝桥云课 (lanqiao.cn)
• 杨辉三角形 - 蓝桥云课 (lanqiao.cn)

计数原理：加法原理

• 加法原理：集合S被分成两两不相交的部分S1、S2、S3、…、Sm，那么S的对象数目等于：|S| = |S1| + |S2| + |S3| + … |Sm|

• 例：一个学生想学一门数学课，一门文化课，但不能同时选，现在从4门数学课和4门文化课中选，一共有4 + 4=8种方法选一门课。

• 加法原理的关键是将计数分解为若干个独立（不相容）的部分，保证既不重复也不遗漏地进行计数。

计数原理：乘法原理

• 令S是对象的有序对(a, b)的集合，其中第一个对象a来自大小为p的一个集合，对于对象a的每个选择，对象b有q个选择，那么S的大小：|S| = p×q

• 例：中性笔的长度有3种，颜色有4种，直径有5种。不同种类的中性笔有：3×4×5=60种。

• 例：3⁴×5⁵×7²×11³的正整数因子有多少？答：这是算数基本定理的概念。3有0~4这5种选择，5有6个选择，7有3个选择，11有4个选择，因子总数是5×6×3×4=360种。

排列数

排列是有序的。

不可重复排列数：从n个不同的物品中取出r个，排列数为：

可重复排列数，从n个不同的物品中可重复地取出r个的排列数为：n^r。

组合数

排列是有序的，组合是无序的。

如果S中的元素都不相同，组合数：

鸽巢原理

• 鸽巢原理，又称抽屉原理。

• 鸽巢原理：把n+1个物体放进n个盒子，至少有一个盒子包含2个或更多的物体。

• 例：在370人中，至少有2人生日相同；

  • 把365天看成365个抽屉。把365人放进365个抽屉，不管怎么放，抽屉里面都有人了。

• 例：n个人互相握手，一定有2个人握手次数相同。

二项式定理和杨辉三角

求杨辉三角第n行的数字，可以模拟这个推导过程，逐级递推，复杂度O(n²)。

用数学公式计算，可以直接得到结果，这个公式是(1 + x)ⁿ。

⭐️10亿以内且在前44723行中没有出现的数都只能在第44723行以后的每一行的第二个数上出现。对于给定的N就是第N+1行的第2个数。（比如：N=5，第一次出现在了（5+1）行的第二个数，也就推导出了：N * (N + 1) / 2 + 2，其中N * (N + 1) / 2计算的是前N行所有的元素个数——简单的等差数列求和，第一行有1个元素，第二行有2个元素……）

以上公式可以在编程过程中作为一个防止溢出的保险!

二项式系数

二项式系数有两种计算方法：