組合數學及其算法篇

• 前言
• 排列與組合
• • 無重集的排列與組合
  • • 無重集的排列
    • 應用例子
    • 無重集的組合
    • 應用例子
  • 重集的排列和組合
  • • 重集的排列
    • 重集的組合

前言

組合數學研究的對象是組態。所謂組態就是指若干個對象按照某些約束條件組成的各種狀態。

排列與組合

在組合數學中，集合分為無重集和重集。
\lbrace表達式\rbrace

• 無重集即集合中的不同元素只出現一次，指在選取過程中每個元素不可重復選取，也就是至多選取一次。記作， $S=\{a_1,a_2,?,a_k\}$
• 重集即集合中的不同元素可出現多次，指在選取過程中每個元素可重復選取。有限重集就是第i個元素a，至多選取n;次。
  記作， $=\{n1?a1,n2?a2,?,nk?ak\}$ 其中n，稱作a，的重數。
  無限重集指每個不同元素可以任意選取若干次。記作，
  S={ω?a1,ω?a2,?,ω0?ak}

無重集的排列與組合

無重集的排列

定義：若集合含有n個不同的元素，從中任選r個的有序編排，則稱為排列或r排列。其不同的排列的個數，簡稱排列數，記作$p(n,r)$

定理1:$對于r<=n,p(n,r)=\frac{n!}{(n?r)!}$ 。

定理2: 從n個元素的集合中任取r個的圓排列個數為:$\frac{p(n,r)}{r}$。證：由前面的定理，從n個不同元素中任取r個的排列個數。為p(n，r)，這種排列又稱線排列。將這些排列分成組，每組有r個線排列且產生相同的r圓排列，所以r圓排列的個數為p(n，r)/r。
特別地，n個元素的圓排列個數為(n-1)!。
我們舉一個例子：

對于一個圓排列abcde ， 我們從5個空隙中斷開，那么會產生5個線排列。也就是說這5個線排列對應的圓排列是一樣的。

應用例子

若男女混座，問6位男士和6位女士圍圓桌就座有多少種方式？
解：我們先安排6位男士就座，6位男士的圓排列數為5！，6位男士就座后，每相鄰兩人之間有一個空位，共6個。剛好安排6位女士，6位女士的全排列數為6！。所以按乘法原理就是 5! * 6!.

無重集的組合

定義：從n個元素的集合S中，任取r個元素且不考慮次序，則稱為組合或r組合。其不同的組合個數，簡稱組合數，記作$C（n,r）$

定理 ， $對于r<=n,C(n,r)=\frac{p(n,r)}{r!}$
例子 ：求1~300的整數中，有多少種方法選出三個整數來使得它們的和被3整除？
解1，2，…，300這300個整數可以分成三組：被3整除者為一組，除以3余1者為一組，除以3余2者為一組，顯然，每一組有100個整數。如果三個整數都選自同一組，其和必能被3整除；如果每組選取一個整數，其和也必能被3整除。因此，選擇三個整數其和能被3整除的方法總數為
C(100,3)+C(100,3) +C(100,3)+1003=1485100。
為什么每一組有100個數呢：我們以余1的為例，對于集合中每一個數我們可以表示成$3x+1$，對于個數我們將99代入< 300 ,代入100>300 , 那么我們x的取值為0 - 99 一共100個數。

應用例子

若一個凸多邊形無三條對角線在其內部交于一點，問這些對角線被它們的交點分成多少短：
凸多邊形對角線條數為$C(n,2)?n$,由于每四個點有一個交點，凸多邊形交點數為$C(n,4)$。每一個對角線上的K個交點將其分為K+1的線段，那么應該是$(K_1+1+...+K_n+1)=(K_1+...+K_n)+n$,其中n為對角線條數，由于一個交點位于兩條對角線上，所以總數為 $$(C(n,2)?n)+2?C(n,4)$$

1000！后邊有多少個0？
1到1000中2的個數遠多于5的個數，2*5可得到一個0。

所以求得1到1000中有多少個5就可以求得1000！的末尾有幾個0.

分析

5的1次冪5的倍數增加1個0 (5,10,15,20,25,30,…)
5的2次冪25的倍數增加2個0(必然是5的倍數)(25,50,75,100,125…)
5的3次冪125的倍數增加3個0(必然是25的倍數)(125,250,375,500…)
5的4次冪625的倍數增加4個0(必然是125的倍數)(625,1250,1875,2500…)
…
所以先求出5的倍數
加上25的倍數(2個0,其中1個已記入5的倍數)
加上125的倍數(3個0,其中1個已記入5的倍數1個已記入25的倍數)
加上625的倍數(4個0,其中…)

1000/5=200 (1000里面含有200個5的倍數，但同時也包含了25倍數，125的倍數，625的倍數各一次)

1000/25=40(1000里面含有40個25的倍數，同時也含有125的倍數，625的倍數各一次)

1000/125=8(1000里面含有8個125的倍數，同時也含有625的倍數)

1000/625=1（1000里含有1個625的倍數）

所以1000！里面含 有0的個數為200+40+8+1=249個

重集的排列和組合

重集的排列

定理1 ： 若S是含有K個不同元素而每一個元素具有無限重復的重集，則S的r排列的個數是$k^r$ 。因為是無限重復的，那么對于每一個元素我們都有K種選法，選r個，因此就是$k^r$

定理2：設重集S有k個不同元素$a_1，a_2，\dots ，a_k$，其有限重復數分別為$n_1,n_2,?,n_k$,且$n=n_1+n_2+?+n_k$,則S的排列個數(指的是所有元素的排列)等于：$$\frac{n!}{n_1!?n_2!...?n_k!}$$

重集的組合

若S是重集，則S的r組合是不考慮次序地從S中選擇r個元素，因此，S的r組合通常是一個子重集。如果S有n個元素，則只存在一個S的n組合。

定理1 ：設S是有K個不同元素的重集，且每個元素的重復次數無限，則S的r組合個數等于 $C(k?1+r,r)$ . 證明: 設S的不同元素是 $a_1，a_2，\dots ，a_k$，因而 $S=\{\infty ?a_1,\infty ?a_2,....,\infty ?a_k\}$. S的任何r組合形如 $\{x_1?a_1,x_2?a2,?,x_k?a_k\}$，其中$x_1，x_2，\dots ，x_k是非負整數且x_1+x_2+?+x_k=r$ 反之，任何滿足$x_1+x_2+?+x_k=r的非負整數序列x_1，x_2，...,x_k對應S的一個r組合$。$于是S的r組合個數等于方程x_1+x_2+?+x_k=r的非負整數解的個數$。
可以證明這些解的個數等于重集$T=\{(k?1)?0,r?1)\}$的排列個數。給定T的一個排列，這(k-1)個0把r個1分成k組。令$x_1$個1在第一個0的左邊，$x_2$個1在第一個0和第二個0之間，…，$x_k$個1在最后一個0的右邊，$而x_1，x_2，...，x_k是非負整數且x_1+x_2+\dots +x_k=r$。 反之，給定非負整數$x_1，x_2，\dots ，x_k,且x_1+x_2+?+x_k=r,$可按相反步驟構造T的一個排列。于是：重集S的r組合個數等于重集T-{(k-1)·0，r·1}的排列個數。而重集T的排列個數就是有限重復集的排列個數，由上面公式，T的排列個數等于
$\frac{(k?1+r)!}{(k?1)!?r!}=C(k?1+r,r)$ 證畢。

對于上面的結果和推導過程，對于重集T的由來，我么可以類比隔板法，（由方程我們可以將r看成r個1）我們有r個一樣的球，我們將其放入k個盒子，可以允許有空盒的方案數。我們用隔板法得到的結果是一樣的。
那么由這個我們就可以求出 $x_1+x_2+...+x_k=r$的非負整數解的個數就是$C(k?1+r,r)$ , 而這就是 $(x_1+...+x_k{)}^r的項數$

定理2 : 設重集S有K個不同元素$a_1,a_2,...,a_k$的重集，且每個元素有無限重復次 。若要求S的每個元素至少在r組合出現一次，則S的這種r組合個數等于$C(r?1,k?1),r>=k$ ，這就是隔板法的理論依據。也就是方程$x_1+...,+x_k=r,x_i>=i$的正整數的解的個數。

定理2的推論: 將r個相同的元素放入n個不同的盒子而使每個盒子至少含有q個元素的分配方法的個數為 $$C(n?nq+r?1,n?1)$$

總結

以上是生活随笔為你收集整理的算法之组合数学及其算法篇(一） ----- 排列与组合的全部內容，希望文章能夠幫你解決所遇到的問題。

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