排列組合

排列(Permutation) 寫成函式Pm(a, b)，唸作"a 取b作排列"，其意義為"a 項元素中取b 項作直線排列的總方法數"，其公式為: a! / (a - b)!。

]Find.. 總共有編號為A、B、C、D 的四人，任選三人排列成隊，求方法數

]Pm(Am({A, B, C, D}), 3) = Pm(4, 3) = 4! / 1! = 4 * 3 * 2 * 1 / 1 = 24

 

全取直線排列，是指將所有來源作直線排列，則可直接寫成: Pm(a, a) = a!。

]Find.. 某班有三十個人，讓全班排成一直線，求方法數

]Pm(30, 30) = 30!

 

子個體，是指將某些來源重新包裝，視為一個來源元素。

]Find.. A、B、C、D 作直線排列，其中A、B 必相鄰，求方法數

]Pm(3, 3) * Pm(2, 2) //把A、B 包裝成X，來源變成{X, C, D}，全取直線排列後，A、B 再進行排列。

]= 12

 

相同物概念，是指某幾項元素在排列中視為相同，比如說: 若A、B 不為相同物，則「AB」、「BA」為兩種排列法；將A、B 視為相同物，則「AB」、「BA」視為一種排列法。每次作排列時，都應針對每項元素的相同物數量(包含自己) 取得一個數n，則排列法必須除以n!。

]Find.. 總共有編號為A、B、C、D 的四人，任選三人排列成隊，且編號A、B 所代表的人為同一個，求方法數

]Pm(Am({A, B, C, D}), 3) / (Am({A, B})! * Am({C})! * Am({D})! ) //A、B 為相同物，C 與自己為相同物，D 亦同。

]= Pm(4, 3) / (2! * 1! * 1!) = (4! / 1!) / (2 * 1 * 1 * 1) = 4 * 3 * 2 * 1 / (1 * 2) = 12

 

相同物概念也用在「順序不變」的討論上。

]Find.. A、B、C、D 四人直線排列，其中A 在C 前面，求方法數

]4! / 2! //A、C 順序不變，視為相同物。

]= 12

 

組合(Combination) 寫成函式Cm(a, b)，唸作"組合a 取b 作組合"，其意義為"a 項元素中取b 項元素作為一集合的總方法數"，其公式為: Pm(a, b) / b!，亦可看作直線排列中所有成員皆是為相同物的概念。

]Find.. 有A、B、C、D 四人，其中有兩位有機會得到一模一樣的禮物，求方法數

]Cm(Am({A, B, C, D}), 2) = Pm(4, 2) / 2! = 6

 

在較複雜的討論中，我們常使用「先取出空間再作排列」的概念，因此有以下規則: Cm(m, n) * Pm(n, n) = Pm(m, n)。

]Find.. 4 成人3 小孩作直線排列，小孩不相鄰，求方法數

]Pm(4, 4) * Cm(5, 3) * Pm(3, 3) //四個成人先排列，成人之間的五個空隙取三個讓小孩插入，三個小孩排列。

]= Pm(4, 4) * Pm(5, 3) = 240

 

潛藏排列(Malignant Permutation)，又稱為惡性排列，是指在只有Cm() 的算式中暗藏了排列的概念，這常導致不可預期的列式錯誤。

 

等量任意分配，又稱重複組合，其概念為有限個數的相同物，全部分配到不同的對象上，討論其方法數。討論這種問題時，該來源──即「有限個數的相同物」──可視為一直線排列的相同物，若以分隔線將該直線切割分為與對象等量的區域數，則可以讓每個區域對應到一個對象，達到分配的目的，因此，讓該些分隔線與該直線──也就是來源──一起作全取直線排列(其中，為了分割為與對象數相同的區塊，則需要對象數減一的分割線數)，並將來源視為相同物，分隔線順序不變，也視為相同物，便是其解。

]Find.. 十支相同鉛筆，全部分配給三個小孩，求方法數

](10 + (3 - 1))! / (10! * 2!) //鉛筆為來源，小孩為對象，有三個小孩就要分割成三個區塊，必須有兩個分隔線，與來源作全取直線排列後，來源視為相同物、分隔線也視為相同物。

]= 66