在leetcode刷題過程中，遇到過很多關于排列組合的問題。弄清楚排列組合的相關原理，是非常有用處的。

文章目錄

• • 1 問題
  • 2 排列-有序選取
  • • 2.1 重復選取-可重排列
    • 2.2 不重復選取-排列
    • • 2.21 全排列
  • 3 例題
  • 4 總結

1 問題

設集合S包含n個元素，從S中選取r個元素有多少種選取方法？

根據取出的元素是否允許重復，以及取出元素的過程是否有序，可以將上述問題分為下面的四個子類型：

排列都是有序的，組合都是無序的。這在后面的學習中會深刻體會。

2 排列-有序選取

2.1 重復選取-可重排列

• 從 n 個不同的對象中， 取 r 個可重復的對象，按次序排列，稱為n取r的可重排列。
• 此也即當 |A|=n 時， A* 中長為 r 的串的個數。

定理1：n取r的可重排列數目為n^r

2.2 不重復選取-排列

• 從 n 個不同的對象中， 取 r 個不重復的對象， 按次序排列， 稱為 n 取 r 的排列（permutation of n objects taken r at atime） 。 n 取 r 排列的全體構成的集合用 P(n, r) 表示， 排列的個數用 P(n, r) 表示（由于個數的表示是斜體不容易區分，后面我們說P(n, r) 即代表排列的個數。）

• 當 r = n 時稱為全排列或置換（permutation）

• 此也即當 |A|=n 時， A* 中長為 r 且各項彼此不同的串的個數。

舉例子：

A = { a, b, c, d }， A 上的所有4取3的排列是：

A = { a, b, c, d },A 上的所有全排列是:

定理2：

n < r 時， P(n, r) = 0； n >= r 時， P(n, r) = n*(n - 1) * … *(n - r + 1)。

2.21 全排列

全排列經常被理解為是包含某個有限集合中的所有元素一次且僅一次的序列。

• 設 A 是集合，如果|A|=n， 則 A 的全排列的個數為：

  n * (n-1) * … * 1

這個值也經常被寫作 n! ，稱作n 的階乘（factorial） 。

可以給出 P(n, r) 的一個更緊湊的表達式：

3 例題

例一

一個社團共有 10 名成員，從中選出一名主席、一名副主席、一名書記，則共有 P(10, 3)=720 種方法。（因為不光是要選出三名學生，還要在這三明學生中確定三個身份。相當于C（10,3）* P（3,3）=p（10,3）,這樣更易于理解。C（10,3）是組合的求解公式，后面會學習）

例二

如果有4個男孩和4個女孩坐成一排，每個人的旁邊都可以隨便坐，那么共有多少種坐的方式？

P（8,8）=8！

例三

如果有4個男孩和4個女孩坐成一排，每個人旁邊都只能坐著異性，那么共有多少種坐的方式？

2 * 4! * 4!

如下圖所示：

4 總結

• 堅持學數學

總結

以上是生活随笔為你收集整理的【离散数学中的数据结构与算法】五 排列与组合一的全部內容，希望文章能夠幫你解決所遇到的問題。

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