Permutations and combinations

Mathematical statement

For natural numbers n and k with 0≤k≤n, the number of ordered selections without replacement is P(n,k)=n!/(n-k)!, while the number of unordered selections is C(n,k)=n!/(k!(n-k)!). Both values are 1 when k=0.

Representative formula (exact TeX)

C(n,k)

Assumptions

• The objects are distinct, selection is without replacement and without repetition, and n and k are natural numbers satisfying 0≤k≤n.
• Permutations distinguish order, combinations ignore order, and the empty selection counts as one selection.

Symbol scope

• C — number of unordered nonrepeating selections
• n — number of distinct available objects
• k — selection size

Intuition, definition, and misconceptions

A permutation chooses in order. The available counts are n, n-1, and so on until k objects have been selected. There is one empty permutation.

Every k-element subset has exactly k! orderings, so dividing the permutation count by k! gives the combination count. This relation depends on distinct objects and selection without replacement.

Selection with repetition, indistinguishable objects, circular arrangements, and additional restrictions require different counting models; the formulas in this entry do not apply to them unconditionally.

A common mistake is to apply a permutation or combination formula before deciding whether order matters, whether objects are distinct, and whether replacement is allowed.

Adopted derivation guide

The original MKO is retained. The guide has its own append-only revision and verification boundaries, not a new Lean proof.

Prerequisites

• Basic counting principles — The successive number of choices and the ordered-versus-unordered distinction require counting principles.
• Factorial — The formulas use natural-number factorials, including 0!=1.

Verification boundary

BigInt computation and small-set enumeration can check stated counts, but formal Evidence for the general counting relation remains to be constructed.

not_formalized

This does not mean the content is false; it means no replayable computational or formal evidence is registered yet.

Next obligation

Bind finite subsets, distinct ordered k-tuples, Nat.choose, and the proof that each k-element subset has k! orderings.

Same-source structured data

This page and the interactive view use the same object and existing language edition; this adds no proof or human review.