排列组合

排列

元素的有序排列。

计算: 个元素的排列:
结果:

——n个元素的r排列: P(n,r) = n!/(n-r)!

元素的无序排列，也称子集。

计算: 个元素的子集:
结果:

——n个元素的r子集: C(n,r) = n!/((n-r)!*(r)!)

多重集合S，有k种元素，每种元素都有无限重复数。

计算: 种元素的排列:
结果:

——集合 S 的 r 排列为: k^r（每个位置都有k种选择，其实只要“重复数＞r”即可使用）

多重集合S，有k种元素，每种元素的重复数分别为n1，n2，...，nk，且满足n1+n2+...+nk = n。

计算: 种元素的 n 排列:
每种元素的重复数为：

结果:

——集合 S 的 n 排列数目等于: n! / n1!n2! ... nk!

注意：这里只给出了求S的n排列（全排列）的公式，而当 r < n 时，只能用生成函数方法求解。

多重集合S，有k种元素，每种元素都有无限重复数，允许限定重复数的上下界。

计算: 种元素的子集:
每种元素的重复数为（允许限定上下界，默认为0和无穷大）

结果:

——集合 S 的 r 组合的数目等于: C(r+k-1, k-1)，可转化为求解方程 x1+x2+...+xk=r 的非负整数解个数。限定上下界，相当于修改了方程中的r（容斥原理永远滴神）。