この記法を、初等組合せ論とは別な文脈で 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) は結局 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-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては効率的ではない(プログラムの実装においては、算術オーバーフローの可能性も加わってくる)。
順列の数え上げ
脚注^ 伏見, 第I章 数学的補助手段 1節 組合わせの理論 p.3.
^ 岩波数学辞典, 184 順列・組合せ p.526.
^ Charalambides, Ch A. (2002). Enumerative Combinatorics
参考文献
日本数学会 編『数学辞典』(第4版)岩波書店、2007年。ISBN 9784000803090。
伏見康治『 ⇒確率論及統計論』河出書房、1942年。ISBN 9784874720127。 ⇒http://ebsa.ism.ac.jp/ebooks/ebook/204。
外部リンク
村田厚生, 太田幸雄「順列・組合せ問題の解答プロセスにおけるメタ認知の役割」『日本感性工学会論文誌』第12巻第4号、日本感性工学会、2013年、447-454頁、doi:10.5057/jjske.12.447、ISSN 1884-0833。
関連項目
完全順列
組合せ (数学)
重複組合せ
重複順列
置換 (数学)
重複置換
写像12相