順列の数え上げ
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/13 13:51 UTC 版)
ここでは 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 ) {\displaystyle P(n,k)=n\times (n-1)\times (n-2)\times \dots \times (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!) から、 P ( n , k ) = n ! ( n − k ) ! {\displaystyle P(n,k)={\frac {n!}{(n-k)!}}} なる関係式が成り立つことがわかる。この右辺は、k-順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として k-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては効率的ではない（プログラムの実装においては、オーバーフローの可能性も加わってくる）。
※この「順列の数え上げ」の解説は、「順列」の解説の一部です。
「順列の数え上げ」を含む「順列」の記事については、「順列」の概要を参照ください。
- 順列の数え上げのページへのリンク
