順列
数え上げ数学における順列（じゅんれつ、英: sequence without repetition, partial permutation、仏: arrangement）は、区別可能な特定の元から有限個を選んで作られる重複の無い列をいう[1]。
初等組合せ論における「写像12相」はともに 有限集合から 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-組 (a1, a2, …, ak) で i ≠ j (i, j ∈ {1, 2, …, k}) ⇒ ai ≠ aj を満たすものを言う。
記法について
初等組合せ論において、n 個の元から k-個を選んで得られる順列の総数を表すのにいくつか異なる記号、例えば nPk, nPk, Pn,k, P(n,k) などが用いられる（同様の記法で "P" を "C" に代えたものは n-元集合の k-組合せの総数を表す）。k ≤ n のとき、その値は積 n × (n − 1) × (n − 2) × … × (n − k + 1) によって表される[3]。一方、k > n のとき（上記の積は定義されないにも拘らず）k-順列の総数 nPk は単に 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) は結局
- partial permutationのページへのリンク
