組合數學(一)

無重排列與組合

• 排列(Permutation)一般隻等是從 n n n個不同的元素中取出 r r r個不重複的元素,按照一定的次序排列,通常稱為 n n n個中取 r r r個的無重排列,通常記為 P n r P_n^r Pnr​.
• 組合(Combination)一般指的是從 n n n個元素中取出 r r r個不相同的元素,組成一子集,而不考慮元素之間的順序關系,通常稱為 n n n個中取 r r r個的無重組合,記做 C n r C_n^r Cnr​.

    對于排列群組合計數最經典的模型是往盒子裡面放小球.

    對于排列 P n r P_n^r Pnr​,将 n n n個不同的小球放入到 r r r個不同的盒子中.從盒子的角度分步來考慮,首先對于第一個盒子選擇放小球,有 n n n個小球可以選擇,然後處理将 n − 1 n-1 n−1個盒子放入到 r − 1 r-1 r−1個盒子中,這裡允許一個盒子隻能放一個小球,.于是得到 P n r = n ∗ P n − 1 r − 1 P_n^r=n*P_{n-1}^{r-1} Pnr​=n∗Pn−1r−1​這個遞推公式.如果從小球的角度考慮,選擇第一個小球如果放,那麼有 r r r個盒子可以放置,同時要處理剩下的 n − 1 n-1 n−1個小球放入到 r − 1 r-1 r−1個盒子中;如果第一個小球不被選中,那麼要處理的問題就是從 n − 1 n-1 n−1個小球中選擇 r r r個放入到盒子中去,并且每個盒子一個小球.于是可以得到 P n r = r ∗ P n − 1 r − 1 + P n − 1 r P_n^r=r*P_{n-1}^{r-1}+P_{n-1}^r Pnr​=r∗Pn−1r−1​+Pn−1r​.

    在組合的小球盒子模型中盒子是完全一樣的沒有差別,可以先假定盒子是有差別的,對盒子進行編号,則盒子的排列中共有 r ! r! r!種,此時就對應前面排列盒子完全不同的情況.于是可以得到 r ! C n r = P n r r!C_n^r=P_n^r r!Cnr​=Pnr​,從何得到:

C n r = P n r r ! C_n^r = \frac{P_n^r}{r!} Cnr​=r!Pnr​​

    有組合的定義可以知道,從 n n n個中選擇 r r r個的數目與從 n n n個中選擇 n − r n-r n−r個的數目是相同的,因為選擇 r r r個後,剩下的就恰好是 n − r n-r n−r,即 C n r = C n n − r C_n^r = C_n^{n-r} Cnr​=Cnn−r​.

關于組合數還有一個公式: C n l ⋅ C l r = C n r ⋅ C n − r l − 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 n個中選擇 l l l個元素,再從這 l l l個元素選擇 r r r個元素的數目等于先從 n n n個元素中選擇 r r r個,在從剩下的 n − r n-r n−r中選擇剩下的 l − r l-r l−r個.

這明顯是一條分割線,明天再寫2020年7月7日23:57:53.

    組合數的另外一個應用模型是格路模型,從 ( 0 , 0 ) (0,0) (0,0)走到 ( m , n ) (m,n) (m,n),在不能回退的情況下,總共有多少種走法,總共有 C m + n m C_{m+n}^m Cm+nm​中.基于各路模型還可以得到關于組合數的另外一個恒等式,總共可以走 n n n步,最後要求抵達 ( n − r , r ) (n-r,r) (n−r,r)這個位置,那麼這個位置的前一個位置隻有兩種選擇 ( n − r − 1 , n ) (n-r-1,n) (n−r−1,n)或 ( n − r , r − 1 ) (n-r,r-1) (n−r,r−1),進而可以得到 C n r = C n − r − 1 r + C n − r r − 1 C_n^r=C_{n-r-1}^r+C_{n-r}^{r-1} Cnr​=Cn−r−1r​+Cn−rr−1​.

    二項式定理也是組合數的一個應用.對于

( a + b ) n = ( a + b ) ⋅ ( a + b ) ⋯ ( a + b ) ⏟ n = C n 0 a n + C n 1 a n − 1 b + ⋯ + C n n − 1 a b n − 1 + C n n b n \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 n個 ( a + b ) (a+b) (a+b)中每一個選擇一個 a a a或 b b b得到的 a b ab ab的數目,如果從 n n n個中選擇出 r r r個 b b b,則 a n − r b r a^{n-r}b^r an−rbr的系數應該就是 C n r C_n^r Cnr​.特别的,當 a , b a,b a,b取特殊值時可以得到下面兩個等式.

• a = b = 1 a=b=1 a=b=1

  2 n = C n 0 + C n 1 + ⋯ + C n r + ⋯ + C n n − 1 + C n n 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 a=1,b=−1

  0 = C n 0 − C n 1 + ⋯ + ( − 1 ) r C n r + ⋯ + ( − 1 ) n C n n 0=C_n^0-C_n^1+\cdots+(-1)^rC_n^r+\cdots+(-1)^nC_n^n 0=Cn0​−Cn1​+⋯+(−1)rCnr​+⋯+(−1)nCnn​.

最後,關于組合式的一個有名恒等式: C h u − V a n d e r m o n d e Chu-Vandermonde Chu−Vandermonde恒等式

C m + n r = C m 0 C n r + C m 1 C n r − 1 + ⋯ + C m r C n 0 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 m個紅球, n n n個藍球,從這個 m + n m+n m+n個球中選擇出 r r r個,利用分類,可以知道,等價于選擇 0 0 0個紅球 r r r個藍球, 1 1 1個紅球 r − 1 r-1 r−1個藍球, … \dots …這些選擇之和,而對每一個選擇采用的應該是分步原理.

可重組合計數

    對于 r r r個小球,小球之沒有差別,認為是一樣的,但是 n n n個盒子是有差別的,對于每一個盒子允許放多個小球,允許盒子為空盒子.

    在前面的不可重組合中, n n n個小球是不同的,但是 r r r個盒子是相同的,并且每個盒子隻允許放一個小球.

    從集合 A = { 1 , 2 , 3 , … , n } A=\{1,2,3,\dots, n\} A={1,2,3,…,n}中選擇 r r r個元素 { a 1 , a 2 , ⋯   , a r } , a i ∈ A , i = 1 , 2 , ⋯   , 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 ≠ j a_i=a_j,i\ne j ai​=aj​,i​=j,記做 C n r ‾ \overline{C_n^r} Cnr​​.并且 C n r ‾ = C n + r − 1 r \overline{C_n^r}=C_{n+r-1}^r Cnr​​=Cn+r−1r​.

    可以将其轉化成門框分隔問題,有 r r r個相同的球,放到 n n n個不同的區域中,其中每個區域可以放多個或者不放小球,需要 n − 1 n-1 n−1個框來分割出這個 n n n個區域,将小球看做 0 0 0,将框看做 ∣ | ∣,那麼:

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

∣0⋯0∣⋯∣​0⋯0

​n​

    這裡面的框 ∣ | ∣和小球 0 0 0都是沒有标記彼此相同的,将問題轉化為求 n n n個相同的 ∣ | ∣和 r r r個相同的 0 0 0的間錯排列問題,假設它們彼此不同,于是這個問題就相當于求 n − r + 1 n-r+1 n−r+1的全排列,然後剔除 0 0 0和 ∣ | ∣相同的情況,于是得到:

( n + r − 1 ) ! r ! ( n − 1 ) ! = C n + r − 1 r = C n r ‾ \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 + ⋯ + x n = r x_1+x_2+\cdots+x_n=r x1​+x2​+⋯+xn​=r的非負整數解的個數是 C n + r − 1 r C_{n+r-1}^r Cn+r−1r​.這裡把 + + +看做隔闆,将 r r r個小球放到 n n n個區域中,每個區域可放多個也可不放小球,于是就是一個可重組合計數的問題.

    關于是否重複排列組合計數的總結:

Type	Sample	Order counts?	Repetition allowed	Number ofways
無重組合	n個求取r個	No	No	C n r C_n^r Cnr​
無重排列	n個人找r個人排隊	Yes	No	P n r P_n^r Pnr​
可重排列	n中水果選擇r個拼果籃	No	Yes	C n + r − 1 r C_{n+r-1}^r Cn+r−1r​
可重排列	n個字母組成的r位串	Yes	Yes	n r n^r nr
多重全排列	r 1 r_1 r1​個a, r 2 r_2 r2​個b組成的n位串	Yes	Yes	n ! r 1 ! r − 2 ! \frac{n!}{{r_1}!{r-2}!} r1​!r−2!n!​

放球問題計數的八種模型

将 n n n個球放到 m m m個盒子中,根據球和盒子是否有差別,是否允許空盒,有下面這些情況:

Type	Number of ways
n個球有差別,m個盒子有差別,有空盒	m n m^n mn
n個球有差別,m個盒子有差別,無空盒	n ! S ( n , m ) n!S(n,m) n!S(n,m)
n個球有差別,m個盒子無差別,有空盒	∑ k = 1 m i n { n , m } S ( n , k ) \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) S(n,m)
n個球無差別,m個盒子有差別,有空盒	C n + m − 1 r C_{n+m-1}^r Cn+m−1r​
n個球無差別,m個盒子有差別,無空盒	C n − 1 n − m = C n − 1 m − 1 C_{n-1}^{n-m}=C_{n-1}^{m-1} Cn−1n−m​=Cn−1m−1​
n個球無差別,m個盒子無差別,有空盒	G ( x ) = 1 ( 1 − x ) ( 1 − x 2 ) ⋯ ( 1 − x 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 x^n xn項的系數
n個球無差別,m個盒子無差別,無空盒	G ( x ) = x m ( 1 − x ) ( 1 − x 2 ) ⋯ ( 1 − x 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 x^n xn項的系數

母函數

    對于一個計數序列:

G ( x ) = c 0 + c 1 x + c 2 x 2 + ⋯ + c r x r + ⋯ \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) G(x),稱作序列 c 0 , c 1 , ⋯   , c r , ⋯ c_0,c_1,\cdots,c_r,\cdots c0​,c1​,⋯,cr​,⋯的母函數,母函數也稱作生成函數,用來表示一個計數序列.

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

    母函數的一個應用是給出 m m m個骰子,計算點數之和為 n n n的數目,對應的 G ( x ) = ( x + x 2 + x 3 + x 4 + x 5 + x 6 ) G(x)=(x+x^2+x^3+x^4+x^5+x^6) G(x)=(x+x2+x3+x4+x5+x6),點數為 n n n的數目即是展開後 x n x^n xn的系數.

整數拆分

    将一個正整數拆分為若幹正整數之和,如果拆分的各部分之間有序稱為有序拆分,否則稱為無序拆分.等價于有 n n n個相同的小球,将這些相同的小球分成若幹堆,總共有多少種分法.

    對于有序拆分, n n n個小球分成 r r r堆, n n n個小球緊密相鄰,中間有 n − 1 n-1 n−1個空隙,選擇 r − 1 r-1 r−1個插入一個隔闆,進而可以把這 n n n個小球分成 r r r份,進而結果就是 C n − 1 r − 1 C_{n-1}^{r-1} Cn−1r−1​.相當于将 n n n個無差別的求放到 r r r個有差別的盒子中,并且每一個盒子不允許空.

    對于正整數的無序拆分,數字之間無順序并且允許重複,它的個數是 p ( n ) p(n) p(n).歐拉給出的這個問題的解是利用母函數:

G ( x ) = ( 1 + x + x 2 + ⋯   ) ( 1 + x 2 + x 4 + ⋯   ) ⋯ ( 1 + x m + x 2 m + ⋯   ) ⋯ 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 x^n xn的系數就是拆分解的數目.

    另外, 1 1 − x \frac{1}{1-x} 1−x1​的無窮級數展開是 ( 1 + x + x 2 + ⋯   ) (1+x+x^2+\cdots) (1+x+x2+⋯),是以上面的 G ( x ) G(x) G(x),可以記做:

G ( x ) = 1 ( 1 − x ) ( 1 − x 2 ) ⋯ ( 1 − x m ) ⋯ 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) p(n)就是 G ( x ) G(x) G(x)展開式中 x n x^n xn的系數.對青前面放球無差別的球放入無差別的盒子中并且允許盒子為空.

    對于上面放球問題中球和盒子都相同并且不允許空盒時,可以首先選擇往每一個盒子放一個球,然後往從剩下的 n − m n-m n−m個求進行上面那種允許空盒的放置,此時應該對應 G ( x ) G(x) G(x)的展開式中 x n − m x^{n-m} xn−m的系數.

Stirling數

第一類Stirling數 s ( n , k ) s(n,k) s(n,k)

     n n n個人條集體舞,分成 m m m個圓環的方法的數目.

s ( n , 0 ) = 0 , s ( 1 , 1 ) = 1 s ( n + 1 , m ) = s ( n , m − 1 ) + n ⋅ s ( n , 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+1個人,它可以自己跳舞,剩下的 n n n個人構成 m − 1 m-1 m−1個圓環;或者加入到已有的隊伍中去,總共有 n n n種選擇.

第二類stirling數 S ( n , k ) S(n,k) S(n,k)

    相當于将 n n n個不同的小球放到 m m m個無差別的盒子中并且不允許盒子為空,求放球的數目.可以先考慮解決盒子有差別,并且每一個盒子不空,然後通過除以 m ! m! m!得到無差別的數目.将 n n n個不同的小球放到 m m m個不同的盒子中并且允許盒子空的方案數 ∣ S ∣ = m n |S|=m^n ∣S∣=mn.設 A i , i = 1 , 2 , 3 , ⋯ A_i,i=1,2,3,\cdots Ai​,i=1,2,3,⋯表示第 i i i個盒子為空則 A i = ( m − 1 ) n A_i=(m-1)^n Ai​=(m−1)n.,總共有 C n 1 C_n^1 Cn1​個;兩個盒子為空,即 ∣ A i ∩ A j ∣ = ( m − 2 ) n |A_i\cap A_j|=(m-2)^n ∣Ai​∩Aj​∣=(m−2)n,總共有 C n 2 C_n^2 Cn2​種; ⋯ \cdots ⋯.由容斥原理:

N = ∣ A 1 ‾ ∩ A 2 ‾ ∩ ⋯ ∩ A n ‾ ∣ = m n − C n 1 ( m − 1 ) n + C n 2 ( m − 1 ) + ⋯ + ( − 1 ) r C n r ( m − r ) n + ⋯ = ∑ k = 0 n ( − 1 ) k C n k ( m − k ) n \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​

進而:

S ( n , m ) = 1 m ! ∑ k = 0 n ( − 1 ) k ( 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 S(m,m)=1,是以

m ! = ∑ k = 0 m ( − 1 ) k C m k ( m − k ) m 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