排列與組合

數學敘述

對自然數 n、k 且 0≤k≤n，由 n 個相異物件無放回選取 k 個的排列數為 P(n,k)=n!/(n-k)!，組合數為 C(n,k)=n!/(k!(n-k)!)；k=0 時兩者均為 1。

代表公式（精確 TeX）

C(n,k)

成立條件

• 物件彼此相異，無放回且不可重複，n、k 是自然數並满足 0≤k≤n。
• 排列區分順序；組合忽略順序，空選取計為一種。

符號作用域

• C — 無序不重複選取數
• n — 相異物件總數
• k — 選取數

直觀、定義與常見誤解

排列依序選擇，每次可選數依次為 n、n-1、…，直到取完 k 個。空排列有一種。

每個 k 元子集合恰有 k! 種排序，所以把排列計數除以 k! 得到組合計數；此關係依物件相異且無放回。

重複選取、不可區分物件、環形排列及額外限制都需要不同計數模型；不把本輪公式無條件套用到它們。

沒有先判斷順序、相異性與放回條件，就直接套排列或組合公式。

已採用的推導導讀

原始 MKO 保留；導讀有自己的追加式修訂與驗證界線，不代表新 Lean 證明。

前置知識

• 基本計數原理 — 逐次可選數與有序／無序的責任需要計數原理。
• 階乘 — 公式以自然數階乘表示，包含 0!=1。

驗證界線

BigInt 精確計算和小集合枚舉可檢查指定計數；一般計數關係的形式 Evidence 仍待建立。

not_formalized

這不表示內容錯誤；只表示尚未登錄可重播的計算或形式證據。

下一個義務

綁定 Finset 子集合、相異有序 k-tuple、Nat.choose 與每個子集合 k! 種排序的證明。

同源結構化資料

本頁與互動版共用同一個物件與既有語言 edition；未新增證明或人工審定。