順列のソースを表示

{{otheruses|順列|初等組合せ論における permutation |置換}}
[[数え上げ数学]]における'''順列'''（じゅんれつ、{{lang-en-short|sequence without repetition, partial permutation}}、{{lang-fr-short|arrangement}}）は、区別可能な特定の元から有限個を選んで作られる重複の無い[[列 (数学)|列]]をいう{{sfn|伏見|loc=第I章　数学的補助手段 1節 組合わせの理論 p.3}}。

初等組合せ論における「[[写像12相]]」はともに [[有限集合]]から {{mvar|k}}-個の元を取り出す方法として可能なものを[[数え上げ]]る問題に関するものである{{sfn|岩波数学辞典|loc=184 順列・組合せ p.526}}。取り出す順番を勘案するのが {{mvar|k}}-順列、順番を無視するのが {{mvar|k}}-[[組合せ (数学)|組合せ]]である。

== 定義 ==
; 定義 1: [[位数 (群論)|位数]] {{mvar|n}} の有限集合 {{mvar|E}} と自然数 {{mvar|k}} に対し、{{mvar|E}} の元からなる {{mvar|k}}-順列とは {{math|{1, 2, …, ''k''} }}から {{mvar|E}} への[[単射]]を言う。
; 定義 2: 位数 {{mvar|n}} の有限集合 {{mvar|E}} と自然数 {{mvar|k}} に対し、{{mvar|E}} の元からなる {{mvar|k}}-順列（{{mvar|E}} に関する {{mvar|k}}-順列、{{mvar|E}} の {{mvar|n}}-個の元から {{mvar|k}}-個を選ぶ順列）とは、{{mvar|k}}-組 {{math|(''a''{{ind|1}}, ''a''{{ind|2}}, …, ''a''{{ind|''k''}})}} で {{math|''i'' &ne; ''j'' (''i'', ''j'' &isin; {1, 2, …, ''k''}) ⇒ ''a''{{ind|''i''}} &ne; ''a''{{ind|''j''}}}} を満たすものを言う。

== 記法について ==
初等組合せ論において、{{mvar|n}} 個の元から {{mvar|k}}-個を選んで得られる順列の総数を表すのにいくつか異なる記号、例えば''' {{mvar|{{msub|n}}P{{msub|k}}}}, {{mvar|{{msup|n}}P{{msub|k}}}}, {{mvar|P{{msub|n,k}}}}, {{math|''P''(''n'',''k'')}} '''などが用いられる（同様の記法で "P" を "C" に代えたものは {{mvar|n}}-元集合の {{mvar|k}}-組合せの総数を表す）。{{math|''k'' ≤ ''n''}} のとき、その値は積 {{math|''n'' × (''n'' − 1) × (''n'' − 2) × … × (''n'' − ''k'' + 1)}} によって表される<ref>{{cite book|author=Charalambides, Ch A.|title=Enumerative Combinatorics|publisher=CRC Press|year=2002|isbn=978-1-58488-290-9|page=42|url=https://books.google.co.jp/books?id=PDMGA-v5G54C&pg=PA42&redir_esc=y&hl=ja}}</ref>。一方、{{math|''k'' &gt; ''n''}} のとき（上記の積は定義されないにも拘らず）{{mvar|k}}-順列の総数 {{mvar|{{msub|n}}P{{msub|k}}}} は単に {{math|0}} と定められる。

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

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

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

: <math>P(n, k) = n \times (n - 1) \times (n - 2) \times \dots \times (n - k + 1)</math>

で与えられることがわかる。特に、{{mvar|n}}-順列（{{mvar|S}} の元の置換）の総数は {{math|''n'' × (''n'' − 1) × (''n'' − 2) × … × 2 × 1}} で、この数値は数学の各所で現れるのでより短く "{{math|''n''!}}" と書く記法が与えられ、「{{mvar|n}} の[[階乗]]」と呼ばれる。{{mvar|n}}-順列は {{mvar|S}} の元からなる最長順列であり、このことは上記の {{mvar|k}}-順列の総数の式において {{math|''k'' &gt; ''n''}} とすると {{math|0}} になるという事実に現れている。

上記の積に余計な因数を掛けて階乗が補完できる {{math|(''P''(''n'',''k'') × (''n'' − ''k'')! {{=}} ''n''!)}} から、
:<math>P(n,k)=\frac{n!}{(n-k)!}</math>
なる関係式が成り立つことがわかる。この右辺は、{{mvar|k}}-順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として {{mvar|k}}-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては効率的ではない（プログラムの実装においては、[[算術オーバーフロー]]の可能性も加わってくる）。

== 脚注 ==
{{Reflist}}

== 参考文献 ==
* {{Cite book|和書|editor=日本数学会|editor-link=日本数学会|year=2007|title=数学辞典|edition=第4版|publisher=[[岩波書店]]|isbn=9784000803090|ref={{sfnref|岩波数学辞典}}}}
* {{Cite book|和書|author=伏見康治|authorlink=伏見康治|year=1942|title=確率論及統計論|publisher=[[河出書房]]|isbn=9784874720127|url=http://ebsa.ism.ac.jp/ebooks/ebook/204| ref={{sfnref|伏見}}}}

== 外部リンク ==
* {{Cite journal|和書|author=村田厚生, 太田幸雄 |year=2013 |url=https://doi.org/10.5057/jjske.12.447 |title=順列・組合せ問題の解答プロセスにおけるメタ認知の役割 |journal=日本感性工学会論文誌 |ISSN=1884-0833 |publisher=日本感性工学会 |volume=12 |issue=4 |pages=447-454 |doi=10.5057/jjske.12.447 |ref=harv}}

== 関連項目 ==
* [[重複順列]]
* [[完全順列]]
* [[場合の数]]
* [[数え上げ]]
* [[数え上げ数学]]
* [[組合せ (数学)]]
* [[組合せ数学]]
* [[重複組合せ]]
* [[置換 (数学)]]
* [[重複置換]]
* [[写像12相]]
* [[樹形図]]

{{デフォルトソート:しゆんれつ}}
[[Category:初等数学]]
[[Category:組合せ論]]
[[Category:順列|*]]
[[Category:数学に関する記事]]