順列
初等組合せ論における順列（じゅんれつ、英: sequence without repetition、仏: arrangement）は、区別可能な特定の元から有限個を選んで作られる重複の無い有限列をいう[1]。
初等組合せ論における「順列と組合せ」はともに n-元集合から k-個の元を取り出す方法として可能なものを数え上げる問題に関するものである[2]。取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。
定義
- 定義 1
- 位数 n の有限集合 E と自然数 k に対し、E の元からなる k-順列とは {1, 2, …, k} から E への単射を言う。
- 定義 2
- 位数 n の有限集合 E と自然数 k に対し、E の元からなる k-順列（E に関する k-順列、E の n-個の元から k-個を選ぶ順列）とは、k-組 (aテンプレート:Ind, aテンプレート:Ind, …, aテンプレート:Ind) で i ≠ j (i, j ∈ {1, 2, …, k}) ⇒ aテンプレート:Ind ≠ aテンプレート:Ind を満たすものを言う。
記法について
初等組合せ論において、n 個の元から k-個を選んで得られる順列の総数を表すのにいくつか異なる記号、例えば テンプレート:MsubPテンプレート:Msub, テンプレート:MsupPテンプレート:Msub, Pテンプレート:Msub, P(n,k) などが用いられる（同様の記法で "P" を "C" に代えたものは n-元集合の k-組合せの総数を表す）。k ≤ n のとき、その値は積 n × (n − 1) × (n − 2) × … × (n − k + 1) によって表される[3]。一方、k > n のとき（上記の積は定義されないにも拘らず）k-順列の総数 テンプレート:MsubPテンプレート:Msub は単に 0 と定められる。
この記法を、初等組合せ論とは別な文脈で k-順列を考える場合に用いることは稀であるが、この数を扱う様々な状況において、適当な記法が用いられる。上記の積に関して、n が非負整数でないものとしても積自体は定義可能で、組合せ論の外で重要な役割を持つ。この場合、上記の積はポッホハマー記号 (n)k あるいは、k-次下降階乗冪 nk で表される（呼び方や記法の詳細はポッホハマー記号の項へ譲る）。
順列の数え上げ
ここでは S の相異なる k-個の元からなる順序付けられた組を S の k-順列（あるいは k-項順列）と呼ぶ。例えば、文字の集合 {C, E, G, I, N, R} が与えられたとき、文字列 ICE は 3-順列、RING や RICE は 4-順列、NICER や REIGN は 5-順列、CRINGE は 6-順列である（6-順列の例は、与えられた集合の元を使い切っているので、組合せ論的な意味での置換の例でもある）。他方、ENGINE は、文字 E と N をそれぞれ二度用いているので順列ではない。
集合 S の大きさ、つまり選ぶことのできる元の種類を、n とする。k-順列を構成するには、まず列の最初の項として取り得る可能性が n-通り（これはつまり 1-順列の総数）だけある。最初の項が決まれば、選んだ以外の残りの元から第二項を選ぶことができるから、第二項の選び方は (n − 1)-通り、従って 2-順列の総数は n × (n − 1) になる。同様に、この列の後続項ではその選び方の可能性が直前の項のそれより 1 ずつ減っていくから、選び得る k-順列の総数 P(n,k) は結局
- P(n,k) = n × (n − 1) × (n − 2) × … × (n − k + 1)
で与えられることがわかる。特に、n-順列（S の元の置換）の総数は n × (n − 1) × (n − 2) × … × 2 × 1 で、この数値は数学の各所で現れるのでより短く "n!" と書く記法が与えられ、「n の階乗」と呼ばれる。n-順列は S の元からなる最長順列であり、このことは上記の k-順列の総数の式において k > n とすると 0 になるという事実に現れている。
上記の積に余計な因数を掛けて階乗が補完できる (P(n,k) × (n − k)! = n!) から、
- [math]P(n,k)=\frac{n!}{(n-k)!}[/math]
なる関係式が成り立つことがわかる。この右辺は、k-順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として k-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては、効率的ではない（計算機でやる場合には、オーバーフローや丸め誤差の危険も加わってくる）。