【组合数学】计数模型、常见组合数与组合恒等式 ★★
文章目錄
- 一、計數模型
- 二、常見的組合計數
一、計數模型
當前涉及到的計數模型 :
1 . 選取問題 :
nnn 元集 SSS , 從 SSS 集合中選取 rrr 個元素 ;
根據 元素是否允許重復 , 選取過程是否有序 , 將選取問題分為四個子類型 :
| 有序選取 | 集合排列 P(n,r)P(n,r)P(n,r) | 多重集排列 |
| 無序選取 | 集合組合 C(n,r)C(n,r)C(n,r) | 多重集組合 |
選取問題中 :
- 不可重復的元素 , 有序的選取 , 對應 集合的排列 ; P(n,r)=n!(n?r)!P(n,r) = \dfrac{n!}{(n-r)!}P(n,r)=(n?r)!n!?
- 不可重復的元素 , 無序的選取 , 對應 集合的組合 ; C(n,r)=P(n,r)r!=n!r!(n?r)!C(n,r) = \dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}C(n,r)=r!P(n,r)?=r!(n?r)!n!?
- 可重復的元素 , 有序的選取 , 對應 多重集的排列 ; 全排列=n!n1!n2!?nk!全排列 = \cfrac{n!}{n_1! n_2! \cdots n_k!}全排列=n1?!n2?!?nk?!n!? , 非全排列 kr,r≤nik^r , \ \ r\leq n_ikr,??r≤ni?
- 可重復的元素 , 無序的選取 , 對應 多重集的組合 ; N=C(k+r?1,r)N= C(k + r - 1, r)N=C(k+r?1,r)
2 . 不定方程非負整數解個數 :
x1+x2+?+xk=rx_1 + x_2 + \cdots + x_k = rx1?+x2?+?+xk?=r
非負整數解個數為 : N=C(k+r?1,r)N= C(k + r - 1, r)N=C(k+r?1,r)
同時也是多重集的組合數 ;
3 . 非降路徑問題 :
基本模型 : 從 (0,0)(0,0)(0,0) 到 (m,n)(m, n)(m,n) 的非降路徑條數 (m+nm)\dbinom{m + n}{m}(mm+n?) ;
拓展模型 1 : 從 (a,b)(a,b)(a,b) 到 (m,n)(m, n)(m,n) 的非降路徑條數 (m?a+n?bm?a)\dbinom{m-a + n-b}{m-a}(m?am?a+n?b?) ;
拓展模型 2 : 從 (a,b)(a,b)(a,b) 經過 (c,d)(c, d)(c,d) 到 (m,n)(m, n)(m,n) 的非降路徑條數 (c?a+c?bc?a)(m?c+n?dm?c)\dbinom{c-a + c-b}{c-a}\dbinom{m-c + n-d}{m-c}(c?ac?a+c?b?)(m?cm?c+n?d?)
限制條件的非降路徑數 : 從 (0,0)(0,0)(0,0) 到 (n,n)(n,n)(n,n) 除端點外 , 不接觸對角線的非降路徑數
參考 : 【組合數學】非降路徑問題 ( 限制條件的非降路徑數 )
二、常見的組合計數
常見的組合計數 :
I . 二項式系數
(x+y)n=∑k=0n(nk)xkyn?k(x + y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}(x+y)n=k=0∑n?(kn?)xkyn?k
(nk)\dbinom{n}{k}(kn?) 是二項式系數 ;
二項式系數相關組合恒等式 :
1 . 組合恒等式 ( 遞推式 ) :
( 1 ) 遞推式 1 :
(nk)=(nn?k)\dbinom{n}{k} = \dbinom{n}{n-k}(kn?)=(n?kn?) ①
( 2 ) 遞推式 2 :
(nk)=nk(n?1k?1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}(kn?)=kn?(k?1n?1?) ②
( 3 ) 遞推式 3 ( 帕斯卡 / 楊輝三角公式 ) :
(nk)=(n?1k)+(n?1k?1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}(kn?)=(kn?1?)+(k?1n?1?) ③
2 . 回顧四個變下項求和的組合恒等式 : 之前介紹的組合恒等式 中的組合數 (nk)\dbinom{n}{k}(kn?) , 是下項 kkk 一直在累加改變 , 具有 ∑k=0n\sum\limits_{k=0}^{n}k=0∑n? 累加性質 , 上項 nnn 是不變的 ;
( 1 ) 簡單和 :
∑k=0n(nk)=2n\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^nk=0∑n?(kn?)=2n ④
( 2 ) 交錯和 :
∑k=0n(?1)k(nk)=0\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0k=0∑n?(?1)k(kn?)=0 ⑤
( 3 ) 變下項求和 3 :
∑k=0nk(nk)=n2n?1\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-1}k=0∑n?k(kn?)=n2n?1 ⑥
( 4 ) 變下項求和 4 :
∑k=0nk2(nk)=n(n+1)2n?2\sum_{k=0}^{n} k^2 \dbinom{n}{k} = n ( n+1 ) 2^{n-2}∑k=0n?k2(kn?)=n(n+1)2n?2 ⑦
3 . 變上項求和 :
∑l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}l=0∑n?(kl?)=(k+1n+1?) ⑧
4 . 積 :
∑l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}l=0∑n?(kl?)=(k+1n+1?) ⑨
5 . 積之和 :
( 1 ) 組合恒等式 ( 積之和 ) 1 :
∑k=0r(mk)(nr?k)=(m+nr),r=min?{m,n}\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{r-k} = \dbinom{m + n }{r} , \ \ \ \ \ \ r= \min \{ m, n \}k=0∑r?(km?)(r?kn?)=(rm+n?),??????r=min{m,n} ⑩
( 2 ) 組合恒等式 ( 積之和 ) 2 :
∑k=0r(mk)(nk)=(m+nm)\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}k=0∑r?(km?)(kn?)=(mm+n?) ?
II . 多項式系數
(x1+x2+?+xt)n\ \ \ \ (x_1 + x_2 + \cdots + x_t)^n????(x1?+x2?+?+xt?)n
=∑滿足n1+n2+?+nt=n非負整數解個數(nn1n2?nt)x1n1x2n2?xtnt= \sum\limits_{滿足 n_1 + n_2 + \cdots + n_t = n 非負整數解個數}\dbinom{n}{n_1 n_2 \cdots n_t}x_1^{n_1}x_2^{n_2}\cdots x_t^{n_t}=滿足n1?+n2?+?+nt?=n非負整數解個數∑?(n1?n2??nt?n?)x1n1??x2n2???xtnt??
(nn1n2?nt)\dbinom{n}{n_1 n_2 \cdots n_t}(n1?n2??nt?n?) 是多項式系數
多項式系數相關組合恒等式 :
1 . 多項式定理推論 3 :
∑(nn1n2?nt)=tn\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n∑(n1?n2??nt?n?)=tn
2 . 多重集全排列 :
(nn1n2?nt)=n!n1!n2!?nk!\dbinom{n}{n_1 n_2 \cdots n_t} = \cfrac{n!}{n_1! n_2! \cdots n_k!}(n1?n2??nt?n?)=n1?!n2?!?nk?!n!?
3 . 遞推式 :
(nn1n2?nt)=(n?1(n1?1)n2?nt)+(n?1n1(n2?1)?nt)+(n?1n1n2?(nt?1))\dbinom{n}{n_1 n_2 \cdots n_t} = \dbinom{n-1}{(n_1-1) n_2 \cdots n_t} + \dbinom{n-1}{n_1 (n_2 - 1) \cdots n_t}+ \dbinom{n-1}{n_1 n_2 \cdots (n_t -1)}(n1?n2??nt?n?)=((n1??1)n2??nt?n?1?)+(n1?(n2??1)?nt?n?1?)+(n1?n2??(nt??1)n?1?)
總結
以上是生活随笔為你收集整理的【组合数学】计数模型、常见组合数与组合恒等式 ★★的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 【组合数学】非降路径问题 ( 限制条件的
- 下一篇: 【组合数学】递推方程 ( 递推方程内容概