當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

【组合数学】计数模型、常见组合数与组合恒等式 ★★

發布時間：2025/6/17 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了【组合数学】计数模型、常见组合数与组合恒等式 ★★ 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

文章目錄

一、計數模型
二、常見的組合計數

一、計數模型

當前涉及到的計數模型 :

1 . 選取問題 :

$n$ 元集 $S$ , 從 $S$ 集合中選取 $r$ 個元素 ;

根據元素是否允許重復 , 選取過程是否有序 , 將選取問題分為四個子類型 :

元素不重復元素可以重復

有序選取	集合排列 $P (n, r)$	多重集排列
無序選取	集合組合 $C (n, r)$	多重集組合

選取問題中 :

不可重復的元素 , 有序的選取 , 對應 集合的排列 ; $\dfrac{n!}{(n-r)!}$
不可重復的元素 , 無序的選取 , 對應 集合的組合 ; $\dfrac{P(n,r)}{r!} = \dfrac{n!}{r!(n-r)!}$
可重復的元素 , 有序的選取 , 對應 多重集的排列 ; $\cfrac{n!}{n_1! n_2! \cdots n_k!}$ , 非全排列 $kr,r≤nik^r , \ \ r\leq n_i$
可重復的元素 , 無序的選取 , 對應 多重集的組合 ; $N = C (k + r ? 1, r)$

2 . 不定方程非負整數解個數 :

$x1+x2+?+xk=rx_1 + x_2 + \cdots + x_k = r$

非負整數解個數為 : $N = C (k + r ? 1, r)$

同時也是多重集的組合數 ;

3 . 非降路徑問題 :

基本模型 : 從 $(0, 0)$ 到 $(m, n)$ 的非降路徑條數 $(m+nm)\dbinom{m + n}{m}$ ;

拓展模型 1 : 從 $(a, b)$ 到 $(m, n)$ 的非降路徑條數 $(m?a+n?bm?a)\dbinom{m-a + n-b}{m-a}$ ;

拓展模型 2 : 從 $(a, b)$ 經過 $(c, d)$ 到 $(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}$

限制條件的非降路徑數 : 從 $(0, 0)$ 到 $(n, n)$ 除端點外 , 不接觸對角線的非降路徑數
參考 : 【組合數學】非降路徑問題 ( 限制條件的非降路徑數 )

二、常見的組合計數

常見的組合計數 :

I . 二項式系數

$y)^n = \sum_{k=0}^n \dbinom{n}{k}x^k y^{n-k}$

$(nk)\dbinom{n}{k}$ 是二項式系數 ;

二項式系數相關組合恒等式 :

1 . 組合恒等式 ( 遞推式 ) :

( 1 ) 遞推式 1 :

$(nk)=(nn?k)\dbinom{n}{k} = \dbinom{n}{n-k}$ ①

( 2 ) 遞推式 2 :

$(nk)=nk(n?1k?1)\dbinom{n}{k} = \dfrac{n}{k} \dbinom{n - 1}{k - 1}$ ②

( 3 ) 遞推式 3 ( 帕斯卡 / 楊輝三角公式 ) :

$(nk)=(n?1k)+(n?1k?1)\dbinom{n}{k} = \dbinom{n - 1}{k} + \dbinom{n - 1}{k - 1}$ ③

2 . 回顧四個變下項求和的組合恒等式 : 之前介紹的組合恒等式中的組合數 $(nk)\dbinom{n}{k}$ , 是下項 $k$ 一直在累加改變 , 具有 $∑k=0n\sum\limits_{k=0}^{n}$ 累加性質 , 上項 $n$ 是不變的 ;

( 1 ) 簡單和 :

$∑k=0n(nk)=2n\sum\limits_{k=0}^{n}\dbinom{n}{k} = 2^n$ ④

( 2 ) 交錯和 :

$∑k=0n(?1)k(nk)=0\sum\limits_{k=0}^{n} (-1)^k \dbinom{n}{k} = 0$ ⑤

( 3 ) 變下項求和 3 :

$∑k=0nk(nk)=n2n?1\sum\limits_{k=0}^{n} k \dbinom{n}{k} = n 2^{n-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}$ ⑦

3 . 變上項求和 :

$∑l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 1}$ ⑧

4 . 積 :

$∑l=0n(lk)=(n+1k+1)\sum\limits_{l=0}^{n} \dbinom{l}{k} = \dbinom{n + 1}{k + 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 \}$ ⑩

( 2 ) 組合恒等式 ( 積之和 ) 2 :

$∑k=0r(mk)(nk)=(m+nm)\sum\limits_{k=0}^{r}\dbinom{m}{k}\dbinom{n}{k} = \dbinom{m + n }{m}$ ?

II . 多項式系數

$(x1+x2+?+xt)n\ \ \ \ (x_1 + x_2 + \cdots + x_t)^n$

$\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}$

$(nn1n2?nt)\dbinom{n}{n_1 n_2 \cdots n_t}$ 是多項式系數

多項式系數相關組合恒等式 :

1 . 多項式定理推論 3 :

$∑(nn1n2?nt)=tn\sum\dbinom{n}{n_1 n_2 \cdots n_t} = t^n$

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!}$

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)}$

總結

以上是生活随笔為你收集整理的【组合数学】计数模型、常见组合数与组合恒等式 ★★的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

上一篇：【组合数学】非降路径问题 ( 限制条件的
下一篇：【组合数学】递推方程 ( 递推方程内容概