順列

数え上げ数学における順列（じゅんれつ、英: sequence without repetition, partial permutation、仏: arrangement）は、区別可能な特定の元から有限個を選んで作られる重複の無い列をいう^[1]。

初等組合せ論における「写像12相」はともに有限集合から $k$ -個の元を取り出す方法として可能なものを数え上げる問題に関するものである^[2]。取り出す順番を勘案するのが $k$ -順列、順番を無視するのが $k$ -組合せである。

定義

定義 1: 位数 $n$ の有限集合 $E$ と自然数 $k$ に対し、 $E$ の元からなる $k$ -順列とは ${1, 2, \dots, k}$ から $E$ への単射を言う。
定義 2: 位数 $n$ の有限集合 $E$ と自然数 $k$ に対し、 $E$ の元からなる $k$ -順列（ $E$ に関する $k$ -順列、 $E$ の $n$ -個の元から $k$ -個を選ぶ順列）とは、 $k$ -組 $(a 1, a 2, \dots, a k)$ で $i \neq j (i, j \in {1, 2, \dots, k}) \Rightarrow a i \neq a j$ を満たすものを言う。

記法について

初等組合せ論において、 $n$ 個の元から $k$ -個を選んで得られる順列の総数を表すのにいくつか異なる記号、例えば $n P k$ , $n P k$ , $P n,k$ , $P (n, k)$ などが用いられる（同様の記法で "P" を "C" に代えたものは $n$ -元集合の $k$ -組合せの総数を表す）。 $k \leq n$ のとき、その値は積 $n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1)$ によって表される^[3]。一方、 $k > n$ のとき（上記の積は定義されないにも拘らず） $k$ -順列の総数 $n P k$ は単に $0$ と定められる。

この記法を、初等組合せ論とは別な文脈で $k$ -順列を考える場合に用いることは稀であるが、この数を扱う様々な状況において、適当な記法が用いられる。上記の積に関して、 $n$ が非負整数でないものとしても積自体は定義可能で、組合せ論の外で重要な役割を持つ。この場合、上記の積はポッホハマー記号 $(n) k$ あるいは、 $k$ -次下降階乗冪 $n k$ で表される（呼び方や記法の詳細はポッホハマー記号の項へ譲る）。

順列の数え上げ

ここでは $S$ の相異なる $k$ -個の元からなる順序付けられた組を $S$ の $k$ -順列（あるいは $k$ -項順列）と呼ぶ。例えば、文字の集合 ${C, E, G, I, N, R}$ が与えられたとき、文字列 $ICE$ は $3$ -順列、 $RING$ や $RICE$ は $4$ -順列、 $NICER$ や $REIGN$ は $5$ -順列、 $CRINGE$ は $6$ -順列である（ $6$ -順列の例は、与えられた集合の元を使い切っているので、組合せ論的な意味での置換の例でもある）。他方、 $EN GI NE$ は、文字 $E$ と $N$ をそれぞれ二度用いているので順列ではない。

集合 $S$ の大きさ、つまり選ぶことのできる元の種類を、 $n$ とする。 $k$ -順列を構成するには、まず列の最初の項として取り得る可能性が $n$ -通り（これはつまり $1$ -順列の総数）だけある。最初の項が決まれば、選んだ以外の残りの元から第二項を選ぶことができるから、第二項の選び方は $(n - 1)$ -通り、従って $2$ -順列の総数は $n \times (n - 1)$ になる。同様に、この列の後続項ではその選び方の可能性が直前の項のそれより $1$ ずつ減っていくから、選び得る $k$ -順列の総数 $P (n, k)$ は結局

P(n,k)=n\times (n-1)\times (n-2)\times \dots \times (n-k+1)

で与えられることがわかる。特に、 $n$ -順列（ $S$ の元の置換）の総数は $n \times (n - 1) \times (n - 2) \times \dots \times 2 \times 1$ で、この数値は数学の各所で現れるのでより短く " $n!$ " と書く記法が与えられ、「 $n$ の階乗」と呼ばれる。 $n$ -順列は $S$ の元からなる最長順列であり、このことは上記の $k$ -順列の総数の式において $k > n$ とすると $0$ になるという事実に現れている。

上記の積に余計な因数を掛けて階乗が補完できる $(P (n, k) \times (n - k)! = n!)$ から、

P(n,k)={\frac {n!}{(n-k)!}}

なる関係式が成り立つことがわかる。この右辺は、 $k$ -順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として $k$ -個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては効率的ではない（プログラムの実装においては、算術オーバーフローの可能性も加わってくる）。

脚注

^ 伏見, 第I章　数学的補助手段 1節組合わせの理論 p.3.
^ 岩波数学辞典, 184 順列・組合せ p.526.
^ Charalambides, Ch A. (2002). Enumerative Combinatorics. CRC Press. p. 42. ISBN 978-1-58488-290-9

参考文献

日本数学会編『数学辞典』（第4版）岩波書店、2007年。ISBN 9784000803090。
伏見康治『確率論及統計論』河出書房、1942年。ISBN 9784874720127。

外部リンク

村田厚生, 太田幸雄「順列・組合せ問題の解答プロセスにおけるメタ認知の役割」『日本感性工学会論文誌』第12巻第4号、日本感性工学会、2013年、447-454頁、doi:10.5057/jjske.12.447、ISSN 1884-0833。

定義

記法について

順列の数え上げ

脚注

参考文献

外部リンク

関連項目