順列
順列（じゅんれつ、テンプレート:Lang-en-short[nb 1]; 重複のない列）とは、数学において、「同じ元が二度は現れることがないが、与えられた集合の全ての元を使い切る必要はない」という条件のもと、与えられた集合から決められた長さの列の事。
初等組合せ論において、「テンプレート:仮リンク」はともに n 元集合から k 個の元を取り出す方法として可能なものを数え上げる問題に関するもので、取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。
n 個の元から k-個を選んで得られる順列の総数を表すのに、いくつか異なる記号、例えば
- n Pk, nPk, Pn,k, P(n,k)
などが用いられ、その値は積
- <math>n\cdot(n-1)\cdot(n-2)\cdots(n-k+1)</math>
によって表される[1]。これは テンプレート:Nowrap のとき 0, それ以外は
- <math>\frac{n!}{(n-k)!}</math>
に等しい。また、上記の積に関して、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-順列の総数）だけある。最初の項が決まれば、選んだ以外の残りの元から第二項を選ぶことができるから、第二項の選び方は テンプレート:Nowrap-通り、従って 2-順列の総数は n × (n − 1) になる。同様に、この列の後続項ではその選び方の可能性が直前の項のそれより 1 ずつ減っていくから、選び得る 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 になるという事実に現れている。
初等組合せ論において、n-元集合の k-順列の総数は、P(n,k) などの記号で表される（同様の記法で "P" を "C" に代えたものは n-元集合の k-組合せの総数を表すのに用いられる）。この記法を、初等組合せ論とは別な文脈で k-順列を考える場合に用いることは稀であるが、この数を扱う様々な状況において、適当な記法が用いられる。n から 1 ずつ減っていく k-個の因数からなる積を、n の k-次下降階乗冪
- <math>n^{\underline k}=n\times(n-1)\times(n-2)\times\cdots\times(n-k+1)</math>
と呼ぶ。呼び方や記法はほかにもたくさんあるが、詳細はポッホハマー記号の項へ譲る。k ≤ n のとき、この階乗冪に余計な因数を掛けて階乗が補完できる (nk × (n − k)! = n!) から、
- <math>n^{\underline k}=\frac{n!}{(n-k)!}</math>
なる関係式が成り立つことがわかる。個の右辺は、k-順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として k-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては、効率的ではない（計算機でやる場合には、オーバーフローや丸め誤差の危険も加わってくる）。またこの右辺は、k > n のとき定義されないにも拘らず、k-順列の総数 nk はこの場合単に 0 と定められる。
出典注
注釈
- ↑ 順列に対応する英単語として permutation が用いられることもある（k-permutation など）が、単に permutation といったときは置換の概念を指す方がふつう。置換は順列の一種だが、与えられた集合の各元を必ず一度だけ用いて使い切らなければならない。
