排列与组合

组合数学

『组合数学』1 排列与组合

1.2 一一对应

组合数学中的重要思想，：模型转换

例子：$Cayley$定理：一个有标号的树与一串生成序列一一对应，计算求解为$n^{n-2}$

1.4 圆周排列与重排列

简单但有点重要的概念略

1.5排列的生成算法

1.5.1 序数法

$m = a_{n-1}!+......+a_1$

排列转序数：2    1    4     3：→ 1 0 1从nto1找逆序数

1.5.2 字典序

• 求下一个排列算法：

i    从后向前第一个不增的数，h 后i个第一个大于 $a_{i-1}$ 的数字交换后i个倒序

1.5.3 换位

• 活跃状态：相邻数比其小
• 算法
  • $S_1$若此时没有活跃状态
  • $S_2$活跃最大的数m先活跃，交换位置，比m大的数字改变箭头方向
• 例题：1234 4123 1324 3124 4312 4321

1.5.4 组合的生成

易得。。

1.6 允许重复的组合与不相邻的组合

定理1-2 n元素中取r个可重复元素 一一对应与n+r-1个不同的取r个不重复 一一对应充分必要性：$C^r_{n+r-1}$

定理1-3 从n个元素取r个不相邻的组合$C^r_{n-r+1}$

证明同理，

• 虽然上面两个定理都比较容易证明，但是卢开澄老师的书上的证明对于我而言还是有一点“数学”。。容易证明但是不太理解为什么。 它的证明附在下面：

  

通过翻看$Richard A. Brualdi$的组合数学算是理解了

：该问题等价于非负整数$x_1+x_2+\cdots+x_r = n$的解的个数问题，有一集合：$\{ n\cdot 1 ,(k-1)\cdot *\}$， 即一个集合中有$n$个相同的1，$k-1$个相同的$*$，$*$将集合化为$n$问题转化为这个集合的排列数问题，易得$\frac{(n+k-1)!}{n!(k-1)!} = \binom{n+k-1}{k}$

不相邻的组合数证明也是倒着用上图的证明方法即可。具体实际含义为在$n-r+1$个元素中随机抽取$r$个，之后用$r-1$个球来填补上这$r$个球的间隙，易知是一一对应的关系

1.7 组合数学解的解释

C(n,r)=C(n-1,r)+C(n-1,r-1)解释