什麼是排列與組合

從一些物件中選出一部分時,計算情形數目的方法。區分所選物件排列順序的是排列,從n個中選出r個排列的數目為 P(n, r) = n!/(n − r)!。不區分順序的是組合,C(n, r) = n!/(r!(n − r)!) = P(n, r)/r!。允許重複選取同一物件的重複排列為 nʳ 種。這是機率計算的基礎,也用於估計密碼的總數或測試組合的數目。

日文名稱: 順列と組合せ

「排列與組合」出現在3領域的5道練習題中(機率、統計與等候理論, 資訊安全基礎, 程式設計基礎(虛擬碼追蹤)等)。

這個名詞所屬的領域: 機率、統計與等候理論

練習排列與組合的題目

將10個鍵放入有100個桶的雜湊表。各鍵彼此獨立,以相等的機率被分配到100個桶中的某一個。在2個鍵的組合中,被分配到同一個桶的組合數的期望值為下列何者?

  1. A0.1
  2. B0.45
  3. C0.9
查看答案與解析

正確答案:B. 0.45

從10個鍵選出2個的組合有 C(10, 2) = 45組,每一組進入同一個桶的機率為1/100。依期望值的線性(和的期望值等於期望值的和),進入同一個桶的組合數的期望值為 45 × 1/100 = 0.45。即使組合之間並不獨立,期望值的線性仍然成立,因此只要把各組的機率相加就能求得。

解析中的「排列與組合」

出現「排列與組合」的題目(5題)

  1. 將10個鍵放入有100個桶的雜湊表。各鍵彼此獨立,以相等的機率被分配到100個桶中的某一個。在2個鍵的組合中,被分配到同一個桶的組合數的期望值為下列何者?
  2. 從8名成員中選出3名委員。若委員之間沒有職務的區別,選法的數目為下列何者?
  3. 從5人中各選出1名主席、副主席與書記。若1人不能兼任2個以上的職務,選法的數目為下列何者?
  4. 50名成員希望任兩人之間都能以加密方式通訊,且不讓其他成員知道內容。使用對稱式加密時所需的金鑰數,與使用公開金鑰加密時所需的金鑰數(公開金鑰與私密金鑰合計),正確的組合是哪一項?
  5. 以 c(4, 2) 呼叫下列函式 c 時,c 被呼叫的次數(含第一次呼叫)為下列何者?

相關名詞

雜湊表 期望值 對稱式加密 公開金鑰加密 回傳值 二項分布 卜瓦松分布 中位數 四分位數 貝氏定理

前往名詞解釋列表