文章目录
前言一、组合分析排列组合前言
概率论基础教程系列是我在阅读Sheldon M.Ross的概率论基础教程时候的笔记和一些个人学习总结，在此记录方便后续复习。
一、组合分析
排列
计数基本法则：
有两个实验，其中实验1有m种可能发生的结果，对应于实验1的每一个可能发生的结果，实验2有n中可能发生的结果，则对这两个实验来说，一共有mn种可能的结果。
法则拓展
nnn个元素，如果其中n1n_1n1个元素彼此相同，另外n2n_2n2个彼此相同…nrn_rnr个彼此相同，那么一共有n!n1!n2!…nr!\cfrac{n!}{n_1!n_2!\dots n_r!}n1!n2!…nr!n!种排列方式。
组合
如果考虑顺序的话，从nnn个元素中选取rrr个组成一组一共有n(n−1)…(n−r+1)n(n-1)\dots(n-r+1)n(n−1)…(n−r+1)种方式，但是如果不考虑选取的顺序，因为之前考虑顺序时每次选择的rrr个元素都当做了r!r!r!种计算，所以不考虑顺序的数目应该为n(n−1)…(n−r+1)r!\cfrac{n(n-1)\dots(n-r+1)}{r!}r!n(n−1)…(n−r+1)
组合法则：
对于r⩽nr\leqslant nr⩽n，定义(nr)\dbinom{n}{r}(rn):
(nr)=n!(n−r)!r!\dbinom{n}{r}=\cfrac{n!}{(n-r)!r!}(rn)=(n−r)!r!n!
我们说(nr)表示从n个元素中一次取出r个的可能组合数\dbinom{n}{r}表示从n个元素中一次取出r个的可能组合数(rn)表示从n个元素中一次取出r个的可能组合数(不考虑顺序)
一个很有用的组合恒等式：
(nr)=(n−1r−1)+(n−1r)\dbinom{n}{r} =\dbinom{n-1}{r-1}+\dbinom{n-1}{r}(rn)=(r−1n−1)+(rn−1)
关于其证明可以这么考虑，假设nnn个元素中有一个是特殊元素，那么从nnn中取出rrr个其实可以看做，包含这个特殊元素或者不包含，如果包含的话，只需要再从n−1n-1n−1个中取出r−1r-1r−1个。如果不包含这个特殊元素，直接从n−1n-1n−1个元素中取出rrr个。
二项式定理
(x+y)n=∑k=0n(nk)xkyn−k\big( x+y\big)^n=\displaystyle\sum_{k=0}^n\dbinom{n}{k}x^ky^{n-k}(x+y)n=k=0∑n(kn)xkyn−k
将nnn个元素分成大小分别为n1,n2,…,nrn_1,n_2,\dots,n_rn1,n2,…,nr的rrr个可分辨的组的方法数：
如果n1+n2+⋯+nr=nn_1+n_2+\dots+n_r=nn1+n2+⋯+nr=n ,定义(nn1,n2,…,nr)=n!n1!n2!…nr!\dbinom{n}{n_1,n_2,\dots,n_r}=\cfrac{n!}{n_1!n_2!\dots n_r!}(n1,n2,…,nrn)=n1!n2!…nr!n!
值得注意的是，虽然这个公式不考虑同一组内成员之间的区别，但是它其实区分了不同组之间的区别。如果说其中有sss个组之间不相互区分，而且每个组包含的元素数目都一样，那么还要在最终结果继续除以s!s!s!
关于上面公式的理解，其实可以这么理解编号为1,2,…,n1,2,\dots,n1,2,…,n的球放到编号为1,2,…,r1,2,\dots,r1,2,…,r的桶里面，首先桶的顺序固定，然后确定一个球的排列，当球的排列确定时，它对应的木桶编号就被确定了。球的排列数目是n!n!n!，但是因为同一个木桶内的球不相互区分所以需要除以n1!n2!…nr!n_1!n_2!\dots n_r!n1!n2!…nr!,所以最后的方法数目为n!n1!n2!…nr!\cfrac{n!}{n_1!n_2!\dots n_r!}n1!n2!…nr!n!。不同的理解思路会改变求解的方法，而有的思路可以简化问题。
多项式定理：
(x1+x2+⋯+xr)n=∑(n1n2…nr):n1+⋯+nr=n(nn1,n2,…,nr)x1n1x2n2…xrnr(x_1+x_2+\dots+x_r)^n=\displaystyle\sum_{(n_1n_2\dots n_r):n_1+\dots+n_r=n}\dbinom{n}{n_1,n_2,\dots,n_r}x_1^{n_1}x_2^{n_2}\dots x_r^{n_r}(x1+x2+⋯+xr)n=(n1n2…nr):n1+⋯+nr=n∑(n1,n2,…,nrn)x1n1x2n2…xrnr
将nnn个不可分辨的球分到rrr个不可分辨的坛子里面的分法有？
如果这么理解，先把nnn个球排好序，因为不可分辨所以只有1种排列方法。然后我们选择从前往后将其分成rrr份。每份分别是x1,x2,…,xrx_1,x_2,\dots,x_rx1,x2,…,xr,所以如果保证每个坛子里面都至少有一个球，其实也就是求满足x1+x2+⋯+xr=nx_1+x_2+\dots+x_r=nx1+x2+⋯+xr=n的非负整数向量(x1,x2,…,xr)(x_1,x_2,\dots,x_r)(x1,x2,…,xr)的个数。其结果其实就是插空，从小球的n−1n-1n−1个空位中选择r−1r-1r−1个位置插入。结果为(n−1r−1)\dbinom{n-1}{r-1}(r−1n−1)。可以得到一个结论：
满足x1+x2+⋯+xr=nx_1+x_2+\dots+x_r=nx1+x2+⋯+xr=n的正整数向量(x1,x2,…,xr)(x_1,x_2,\dots,x_r)(x1,x2,…,xr)的个数为(n−1r−1)\dbinom{n-1}{r-1}(r−1n−1)
其中，xi>0,i=1,2,…,rx_i>0,i=1,2,\dots,rxi>0,i=1,2,…,r
但是我们其实需要的是每个维度都可以⩾0\geqslant0⩾0的向量的个数。所以求解满足x1+x2+⋯+xr=nx_1+x_2+\dots+x_r=nx1+x2+⋯+xr=n的非负整数向量(x1,x2,…,xr)(x_1,x_2,\dots,x_r)(x1,x2,…,xr)的个数，可以理解为求满足y1+y2+⋯+yr=n+ry_1+y_2+\dots+y_r=n+ry1+y2+⋯+yr=n+r的正整数向量(y1,y2,…,yr)(y_1,y_2,\dots,y_r)(y1,y2,…,yr)的个数。
(其中yi=xi+1y_i=x_i+1yi=xi+1)
所以最终结果为(n+r−1r−1)\dbinom{n+r-1}{r-1}(r−1n+r−1)
满足x1+x2+⋯+xr=nx_1+x_2+\dots+x_r=nx1+x2+⋯+xr=n的非负整数向量(x1,x2,…,xr)(x_1,x_2,\dots,x_r)(x1,x2,…,xr)的个数为(n+r−1r−1)\dbinom{n+r-1}{r-1}(r−1n+r−1)
其中，xi⩾0,i=1,2,…,rx_i\geqslant0,i=1,2,\dots,rxi⩾0,i=1,2,…,r
