组合数学(一)

无重排列与组合

• 排列(Permutation)一般只等是从$n$n个不同的元素中取出$r$r个不重复的元素,按照一定的次序排列,通常称为$n$n个中取$r$r个的无重排列,通常记为$P_n^r$Pnr​.

• 组合(Combination)一般指的是从$n$n个元素中取出$r$r个不相同的元素,组成一子集,而不考虑元素之间的顺序关系,通常称为$n$n个中取$r$r个的无重组合,记做$C_n^r$Cnr​.

    对于排列和组合计数最经典的模型是往盒子里面放小球.

    对于排列$P_n^r$Pnr​,将$n$n个不同的小球放入到$r$r个不同的盒子中.从盒子的角度分步来考虑,首先对于第一个盒子选择放小球,有$n$n个小球可以选择,然后处理将$n-1$n−1个盒子放入到$r-1$r−1个盒子中,这里允许一个盒子只能放一个小球,.于是得到$P_n^r=n*P_{n-1}^{r-1}$Pnr​=n∗Pn−1r−1​这个递推公式.如果从小球的角度考虑,选择第一个小球如果放,那么有$r$r个盒子可以放置,同时要处理剩下的$n-1$n−1个小球放入到$r-1$r−1个盒子中;如果第一个小球不被选中,那么要处理的问题就是从$n-1$n−1个小球中选择$r$r个放入到盒子中去,并且每个盒子一个小球.于是可以得到$P_n^r=r*P_{n-1}^{r-1}+P_{n-1}^r$Pnr​=r∗Pn−1r−1​+Pn−1r​.

    在组合的小球盒子模型中盒子是完全一样的没有区别,可以先假定盒子是有区别的,对盒子进行编号,则盒子的排列中共有$r!$r!种,此时就对应前面排列盒子完全不同的情况.于是可以得到$r!C_n^r=P_n^r$r!Cnr​=Pnr​,从何得到:

$C_n^r = \frac{P_n^r}{r!}$Cnr​=r!Pnr​​

    有组合的定义可以知道,从$n$n个中选择$r$r个的数目与从$n$n个中选择$n-r$n−r个的数目是相同的,因为选择$r$r个后,剩下的就恰好是$n-r$n−r,即$C_n^r = C_n^{n-r}$Cnr​=Cnn−r​.

关于组合数还有一个公式:$C_n^l \cdot C_l^r = C_n^r \cdot C_{n-r}^{l-r}$Cnl​⋅Clr​=Cnr​⋅Cn−rl−r​.意思是从$n$n个中选择$l$l个元素,再从这$l$l个元素选择$r$r个元素的数目等于先从$n$n个元素中选择$r$r个,在从剩下的$n-r$n−r中选择剩下的$l-r$l−r个.

---

这明显是一条分割线,明天再写2020年7月7日23:57:53.

---

    组合数的另外一个应用模型是格路模型,从$(0,0)$(0,0)走到$(m,n)$(m,n),在不能回退的情况下,总共有多少种走法,总共有$C_{m+n}^m$Cm+nm​中.基于各路模型还可以得到关于组合数的另外一个恒等式,总共可以走$n$n步,最后要求抵达$(n-r,r)$(n−r,r)这个位置,那么这个位置的前一个位置只有两种选择 $(n-r-1,n)$(n−r−1,n)或 $(n-r,r-1)$(n−r,r−1),从而可以得到$C_n^r=C_{n-r-1}^r+C_{n-r}^{r-1}$Cnr​=Cn−r−1r​+Cn−rr−1​.

    二项式定理也是组合数的一个应用.对于

$\begin{matrix} (a+b)^n= \underbrace{(a+b)\cdot(a+b) \cdots (a+b)} \\ n \\ = C_n^0a^n+C_n^1a^{n-1}b+\cdots+C_n^{n-1}ab^{n-1}+C_n^nb^n \end{matrix}$(a+b)n=(a+b)⋅(a+b)⋯(a+b)​n=Cn0​an+Cn1​an−1b+⋯+Cnn−1​abn−1+Cnn​bn​

表示从$n$n个$(a+b)$(a+b)中每一个选择一个$a$a或$b$b得到的$ab$ab的数目,如果从$n$n个中选择出$r$r个$b$b,则$a^{n-r}b^r$an−rbr的系数应该就是$C_n^r$Cnr​.特别的,当$a,b$a,b取特殊值时可以得到下面两个等式.

• $a=b=1$a=b=1
  $2^n = C_n^0+C_n^1+\cdots+C_n^r+\cdots+C_n^{n-1}+C_n^n$2n=Cn0​+Cn1​+⋯+Cnr​+⋯+Cnn−1​+Cnn​
• $a=1,b=-1$a=1,b=−1
  $0=C_n^0-C_n^1+\cdots+(-1)^rC_n^r+\cdots+(-1)^nC_n^n$0=Cn0​−Cn1​+⋯+(−1)rCnr​+⋯+(−1)nCnn​.

最后,关于组合式的一个有名恒等式: $Chu-Vandermonde$Chu−Vandermonde恒等式

$C_{m+n}^r=C_m^0C_n^r+C_m^1C_n^{r-1}+\cdots+C_m^rC_n^0$Cm+nr​=Cm0​Cnr​+Cm1​Cnr−1​+⋯+Cmr​Cn0​

这个恒等式可以用取小球来简单的解释,假设有$m$m个红球,$n$n个蓝球,从这个$m+n$m+n个球中选择出$r$r个,利用分类,可以知道,等价于选择$0$0个红球$r$r个蓝球,$1$1个红球$r-1$r−1个蓝球,$\dots$…这些选择之和,而对每一个选择采用的应该是分步原理.

可重组合计数

    对于$r$r个小球,小球之没有区别,认为是一样的,但是$n$n个盒子是有区别的,对于每一个盒子允许放多个小球,允许盒子为空盒子.

    在前面的不可重组合中,$n$n个小球是不同的,但是$r$r个盒子是相同的,并且每个盒子只允许放一个小球.

    从集合$A=\{1,2,3,\dots, n\}$A={1,2,3,…,n}中选择$r$r个元素$\{a_1,a_2,\dotsb,a_r\},a_i\in A,i=1,2,\dotsb,r${a1​,a2​,⋯,ar​},ai​∈A,i=1,2,⋯,r并且允许$a_i=a_j,i\ne j$ai​=aj​,i​=j,记做$\overline{C_n^r}$Cnr​​.并且$\overline{C_n^r}=C_{n+r-1}^r$Cnr​​=Cn+r−1r​.

    可以将其转化成门框分隔问题,有$r$r个相同的球,放到$n$n个不同的区域中,其中每个区域可以放多个或者不放小球,需要$n-1$n−1个框来分割出这个$n$n个区域,将小球看做$0$0,将框看做$|$∣,那么:

$\begin{matrix} r \\ \overbrace{0\cdots0 \underbrace{|0\cdots0|\cdots|}0\cdots0} \\ n \end{matrix}$r0⋯0∣0⋯0∣⋯∣​0⋯0​n​

    这里面的框$|$∣和小球$0$0都是没有标记彼此相同的,将问题转化为求$n$n个相同的$|$∣和$r$r个相同的$0$0的间错排列问题,假设它们彼此不同,于是这个问题就相当于求$n-r+1$n−r+1的全排列,然后剔除$0$0和$|$∣相同的情况,于是得到:
$\frac{(n+r-1)!}{r!(n-1)!}=C_{n+r-1}^r=\overline{C_n^r}$r!(n−1)!(n+r−1)!​=Cn+r−1r​=Cnr​​

    可重组合的一个应用是线性方程的整数解问题.线性方程$x_1+x_2+\cdots+x_n=r$x1​+x2​+⋯+xn​=r的非负整数解的个数是$C_{n+r-1}^r$Cn+r−1r​.这里把$+$+看做隔板,将$r$r个小球放到$n$n个区域中,每个区域可放多个也可不放小球,于是就是一个可重组合计数的问题.

    关于是否重复排列组合计数的总结:

Type	Sample	Order counts?	Repetition allowed	Number ofways
无重组合	n个求取r个	No	No	$C_n^r$Cnr​
无重排列	n个人找r个人排队	Yes	No	$P_n^r$Pnr​
可重排列	n中水果选择r个拼果篮	No	Yes	$C_{n+r-1}^r$Cn+r−1r​
可重排列	n个字母组成的r位串	Yes	Yes	$n^r$nr
多重全排列	$r_1$r1​个a,$r_2$r2​个b组成的n位串	Yes	Yes	$\frac{n!}{{r_1}!{r-2}!}$r1​!r−2!n!​

放球问题计数的八种模型

将$n$n个球放到$m$m个盒子中,根据球和盒子是否有区别,是否允许空盒,有下面这些情况:

Type	Number of ways
n个球有区别,m个盒子有区别,有空盒	$m^n$mn
n个球有区别,m个盒子有区别,无空盒	$n!S(n,m)$n!S(n,m)
n个球有区别,m个盒子无区别,有空盒	$\sum_{k=1}^{min\{n,m\}}{S(n,k)}$k=1∑min{n,m}​S(n,k)
n个球有区别,m个盒子无区别,无空盒	$S(n,m)$S(n,m)
n个球无区别,m个盒子有区别,有空盒	$C_{n+m-1}^r$Cn+m−1r​
n个球无区别,m个盒子有区别,无空盒	$C_{n-1}^{n-m}=C_{n-1}^{m-1}$Cn−1n−m​=Cn−1m−1​
n个球无区别,m个盒子无区别,有空盒	$G(x)=\frac{1}{(1-x)(1-x^2)\cdots(1-x^m)}$G(x)=(1−x)(1−x2)⋯(1−xm)1​中$x^n$xn项的系数
n个球无区别,m个盒子无区别,无空盒	$G(x)=\frac{x^m}{(1-x)(1-x^2)\cdots(1-x^m)}$G(x)=(1−x)(1−x2)⋯(1−xm)xm​中$x^n$xn项的系数

母函数

    对于一个计数序列:
$\qquad G(x) = c_0+c_1x+c_2x^2+\cdots+c_rx^r+\cdots$G(x)=c0​+c1​x+c2​x2+⋯+cr​xr+⋯
函数$G(x)$G(x),称作序列$c_0,c_1,\cdots,c_r,\cdots$c0​,c1​,⋯,cr​,⋯的母函数,母函数也称作生成函数,用来表示一个计数序列.

母函数就是一列用来表示一串数字序列的挂衣架.

    母函数的一个应用是给出$m$m个骰子,计算点数之和为$n$n的数目,对应的$G(x)=(x+x^2+x^3+x^4+x^5+x^6)$G(x)=(x+x2+x3+x4+x5+x6),点数为$n$n的数目即是展开后$x^n$xn的系数.

整数拆分

    将一个正整数拆分为若干正整数之和,如果拆分的各部分之间有序称为有序拆分,否则称为无序拆分.等价于有$n$n个相同的小球,将这些相同的小球分成若干堆,总共有多少种分法.

    对于有序拆分,$n$n个小球分成$r$r堆,$n$n个小球紧密相邻,中间有$n-1$n−1个空隙,选择$r-1$r−1个插入一个隔板,从而可以把这$n$n个小球分成$r$r份,从而结果就是$C_{n-1}^{r-1}$Cn−1r−1​.相当于将$n$n个无区别的求放到$r$r个有区别的盒子中,并且每一个盒子不允许空.

    对于正整数的无序拆分,数字之间无顺序并且允许重复,它的个数是$p(n)$p(n).欧拉给出的这个问题的解是利用母函数:
$G(x)=(1+x+x^2+\cdots)(1+x^2+x^4+\cdots)\cdots(1+x^m+x^{2m}+\cdots)\cdots$G(x)=(1+x+x2+⋯)(1+x2+x4+⋯)⋯(1+xm+x2m+⋯)⋯展开式中$x^n$xn的系数就是拆分解的数目.

    另外,$\frac{1}{1-x}$1−x1​的无穷级数展开是$(1+x+x^2+\cdots)$(1+x+x2+⋯),所以上面的$G(x)$G(x),可以记做:
$G(x) = \frac{1}{(1-x)(1-x^2)\cdots(1-x^m)\cdots}$G(x)=(1−x)(1−x2)⋯(1−xm)⋯1​
$p(n)$p(n)就是$G(x)$G(x)展开式中$x^n$xn的系数.对青前面放球无区别的球放入无区别的盒子中并且允许盒子为空.

    对于上面放球问题中球和盒子都相同并且不允许空盒时,可以首先选择往每一个盒子放一个球,然后往从剩下的$n-m$n−m个求进行上面那种允许空盒的放置,此时应该对应$G(x)$G(x)的展开式中$x^{n-m}$xn−m的系数.

Stirling数

第一类Stirling数$s(n,k)$s(n,k)

    $n$n个人条集体舞,分成$m$m个圆环的方法的数目.
$\begin{aligned} s(n,0)&=0,s(1,1)=1 \\ s(n+1,m) &= s(n,m-1) + n\cdot s(n,m) \end{aligned}$s(n,0)s(n+1,m)​=0,s(1,1)=1=s(n,m−1)+n⋅s(n,m)​
对于第$n+1$n+1个人,它可以自己跳舞,剩下的$n$n个人构成$m-1$m−1个圆环;或者加入到已有的队伍中去,总共有$n$n种选择.

第二类stirling数$S(n,k)$S(n,k)

    相当于将$n$n个不同的小球放到$m$m个无区别的盒子中并且不允许盒子为空,求放球的数目.可以先考虑解决盒子有区别,并且每一个盒子不空,然后通过除以$m!$m!得到无区别的数目.将$n$n个不同的小球放到$m$m个不同的盒子中并且允许盒子空的方案数$|S|=m^n$∣S∣=mn.设$A_i,i=1,2,3,\cdots$Ai​,i=1,2,3,⋯表示第$i$i个盒子为空则$A_i=(m-1)^n$Ai​=(m−1)n.,总共有$C_n^1$Cn1​个;两个盒子为空,即$|A_i\cap A_j|=(m-2)^n$∣Ai​∩Aj​∣=(m−2)n,总共有$C_n^2$Cn2​种;$\cdots$⋯.由容斥原理:

$\begin{aligned} N &=|\overline{A_1}\cap\overline{A_2}\cap \cdots \cap \overline{A_n}|\\ & = m^n - C_n^1(m-1)^n + C_n^2(m-1) + \cdots+ (-1)^rC_n^r(m-r)^n+\cdots\\ & = \sum_{k=0}^n{(-1)^kC_n^k(m-k)^n} \end{aligned}$N​=∣A1​​∩A2​​∩⋯∩An​​∣=mn−Cn1​(m−1)n+Cn2​(m−1)+⋯+(−1)rCnr​(m−r)n+⋯=k=0∑n​(−1)kCnk​(m−k)n​

从而:

$\begin{aligned} S(n,m) = \frac{1}{m!}\sum_{k=0}^n{(-1)^k(m-k)^n} \end{aligned}$S(n,m)=m!1​k=0∑n​(−1)k(m−k)n​

特别地:因为$S(m,m)=1$S(m,m)=1,所以
$m!=\sum_{k=0}^m{(-1)^kC_m^k(m-k)^m}$m!=k=0∑m​(−1)kCmk​(m−k)m.

---

这是一条未完待更的分割线2020年7月8日15:21:31

---