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