順列
テンプレート:Otheruses 数え上げ数学における順列（じゅんれつ、テンプレート:Lang-en-short、テンプレート:Lang-fr-short）は、区別可能な特定の元から有限個を選んで作られる重複の無い列をいうテンプレート:Sfn。
初等組合せ論における「写像12相」はともに 有限集合から テンプレート:Mvar-個の元を取り出す方法として可能なものを数え上げる問題に関するものであるテンプレート:Sfn。取り出す順番を勘案するのが テンプレート:Mvar-順列、順番を無視するのが テンプレート:Mvar-組合せである。
定義
- 定義 1
- 位数 テンプレート:Mvar の有限集合 テンプレート:Mvar と自然数 テンプレート:Mvar に対し、テンプレート:Mvar の元からなる テンプレート:Mvar-順列とは テンプレート:Mathから テンプレート:Mvar への単射を言う。
- 定義 2
- 位数 テンプレート:Mvar の有限集合 テンプレート:Mvar と自然数 テンプレート:Mvar に対し、テンプレート:Mvar の元からなる テンプレート:Mvar-順列（テンプレート:Mvar に関する テンプレート:Mvar-順列、テンプレート:Mvar の テンプレート:Mvar-個の元から テンプレート:Mvar-個を選ぶ順列）とは、テンプレート:Mvar-組 テンプレート:Math で テンプレート:Math を満たすものを言う。
記法について
初等組合せ論において、テンプレート:Mvar 個の元から テンプレート:Mvar-個を選んで得られる順列の総数を表すのにいくつか異なる記号、例えば テンプレート:Mvar, テンプレート:Mvar, テンプレート:Mvar, テンプレート:Math などが用いられる（同様の記法で "P" を "C" に代えたものは テンプレート:Mvar-元集合の テンプレート:Mvar-組合せの総数を表す）。テンプレート:Math のとき、その値は積 テンプレート:Math によって表される[1]。一方、テンプレート:Math のとき（上記の積は定義されないにも拘らず）テンプレート:Mvar-順列の総数 テンプレート:Mvar は単に テンプレート:Math と定められる。
この記法を、初等組合せ論とは別な文脈で テンプレート:Mvar-順列を考える場合に用いることは稀であるが、この数を扱う様々な状況において、適当な記法が用いられる。上記の積に関して、テンプレート:Mvar が非負整数でないものとしても積自体は定義可能で、組合せ論の外で重要な役割を持つ。この場合、上記の積はポッホハマー記号 テンプレート:Math あるいは、テンプレート:Mvar-次下降階乗冪 テンプレート:Math で表される（呼び方や記法の詳細はポッホハマー記号の項へ譲る）。
順列の数え上げ
ここでは テンプレート:Mvar の相異なる テンプレート:Mvar-個の元からなる順序付けられた組を テンプレート:Mvar の テンプレート:Mvar-順列（あるいは テンプレート:Mvar-項順列）と呼ぶ。例えば、文字の集合テンプレート:Mathが与えられたとき、文字列 テンプレート:Math は テンプレート:Math-順列、テンプレート:Math や テンプレート:Math は テンプレート:Math-順列、テンプレート:Math や テンプレート:Math は テンプレート:Math-順列、テンプレート:Math は テンプレート:Math-順列である（テンプレート:Math-順列の例は、与えられた集合の元を使い切っているので、組合せ論的な意味での置換の例でもある）。他方、テンプレート:Math は、文字 テンプレート:Math と テンプレート:Math をそれぞれ二度用いているので順列ではない。
集合 テンプレート:Mvar の大きさ、つまり選ぶことのできる元の種類を、テンプレート:Mvar とする。テンプレート:Mvar-順列を構成するには、まず列の最初の項として取り得る可能性が テンプレート:Mvar-通り（これはつまり テンプレート:Math-順列の総数）だけある。最初の項が決まれば、選んだ以外の残りの元から第二項を選ぶことができるから、第二項の選び方は テンプレート:Math-通り、従って テンプレート:Math-順列の総数は テンプレート:Math になる。同様に、この列の後続項ではその選び方の可能性が直前の項のそれより テンプレート:Math ずつ減っていくから、選び得る テンプレート:Mvar-順列の総数 テンプレート:Math は結局
で与えられることがわかる。特に、テンプレート:Mvar-順列（テンプレート:Mvar の元の置換）の総数は テンプレート:Math で、この数値は数学の各所で現れるのでより短く "テンプレート:Math" と書く記法が与えられ、「テンプレート:Mvar の階乗」と呼ばれる。テンプレート:Mvar-順列は テンプレート:Mvar の元からなる最長順列であり、このことは上記の テンプレート:Mvar-順列の総数の式において テンプレート:Math とすると テンプレート:Math になるという事実に現れている。
上記の積に余計な因数を掛けて階乗が補完できる テンプレート:Math から、
なる関係式が成り立つことがわかる。この右辺は、テンプレート:Mvar-順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として テンプレート:Mvar-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては効率的ではない（プログラムの実装においては、算術オーバーフローの可能性も加わってくる）。