英: permutation

WordNet

act of changing the lineal order of objects in a group
complete change in character or condition; "the permutations...taking place in the physical world"- Henry Miller
the act of changing the arrangement of a given number of elements

PrepTutorEJDIC

並べ変えること,順序を変えること / (数学で)順列,置換

Wikipedia preview

出典(authority):フリー百科事典『ウィキペディア（Wikipedia）』「2015/05/07 07:12:56」(JST)

wiki ja

[Wiki ja表示]

組合せ論における順列（じゅんれつ、英: partial permutation）は、置換に延長可能な部分写像（英語版）をいう^[1]^[2]。

初等組合せ論において、「順列と置換（英語版）」はともに n 元集合から k 個の元を取り出す方法として可能なものを数え上げる問題に関するもので、取り出す順番を勘案するのが k-順列、順番を無視するのが k-組合せである。

定義

有限集合 $S$ を文字集合とする順列とは、 $S$ の二つの部分集合 $U, V$ の間に定まる全単射を言う。すなわち $U, V$ は同じ大きさの部分集合で $U$ の元は順列によって $V$ の元に一対一で写される。

文献によっては始域^[3] あるいは終域^[4]に制限を施して、集合の $n$ 個の元のうち適当な自然数 $k$ に対して最初の $k$ -個の元を並べ替える全単射だけ考えるというものもある。前者の場合、文字集合 $S$ の $n$ -個の元から $k$ -個を選ぶ順列とは、各項が $S$ の元からなる重複の無い有限 $k$ -項列である。（初等組合せ論では、こういう意味で「 $n$ 個から $k$ 個を選ぶ順列」（ $k$ -順列）という言葉を使うことがあるため紛らわしい）。

記法

n 個の元から k-個を選んで得られる順列の総数を表すのに、いくつか異なる記号、例えば

_n P_k, ⁿP_k, P_n,k, P(n,k)

などが用いられ、その値は積

によって表される^[5]。これは k > n のとき 0, それ以外は

に等しい。また、上記の積に関して、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-順列の例は、与えられた集合の元を使い切っているので、組合せ論的な意味での置換の例でもある）。他方、ENGINE は、文字 E と N をそれぞれ二度用いているので順列ではない。

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

n × (n − 1) × (n − 2) ... × (n − k + 1)

であることがわかる。特に、n-順列（S の元の置換）の総数は、

n × (n − 1) × (n − 2) × ... × 2 × 1

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

初等組合せ論において、n-元集合の k-順列の総数は、P(n,k) などの記号で表される（同様の記法で "P" を "C" に代えたものは n-元集合の k-組合せの総数を表すのに用いられる）。この記法を、初等組合せ論とは別な文脈で k-順列を考える場合に用いることは稀であるが、この数を扱う様々な状況において、適当な記法が用いられる。n から 1 ずつ減っていく k-個の因数からなる積を、n の k-次下降階乗冪

と呼ぶ。呼び方や記法はほかにもたくさんあるが、詳細はポッホハマー記号の項へ譲る。k ≤ n のとき、この階乗冪に余計な因数を掛けて階乗が補完できる (n^k × (n − k)! = n!) から、

なる関係式が成り立つことがわかる。個の右辺は、k-順列の総数の式としてしばしば与えられるものだが、主な利点は短く階乗記法を用いて書けることである。非常に大きくなるかもしれない積同士の商として k-個の因数からなる積を表すということは、分母の全ての因数が分子に明示的に表れている今の状況においては、効率的ではない（計算機でやる場合には、オーバーフローや丸め誤差の危険も加わってくる）。またこの右辺は、k > n のとき定義されないにも拘らず、k-順列の総数 n^k はこの場合単に 0 と定められる。

参考文献

^ Straubing, Howard (1983), “A combinatorial proof of the Cayley-Hamilton theorem”, Discrete Mathematics 43 (2-3): 273–279, doi:10.1016/0012-365X(83)90164-4, MR685635 .
^ Ku, C. Y.; Leader, I. (2006), “An Erdős-Ko-Rado theorem for partial permutations”, Discrete Mathematics 306 (1): 74–86, doi:10.1016/j.disc.2005.11.007, MR2202076 .
^ Burstein, Alexander; Lankham, Isaiah (2010), “Restricted patience sorting and barred pattern avoidance”, Permutation patterns, London Math. Soc. Lecture Note Ser., 376, Cambridge: Cambridge Univ. Press, pp. 233–257, doi:10.1017/CBO9780511902499.013, MR2732833 .
^ Claesson, Anders; Jelínek, Vít; Jelínková, Eva; Kitaev, Sergey (2011), “Pattern avoidance in partial permutations”, Electronic Journal of Combinatorics 18 (1): Paper 25, 41, MR2770130 .
^ Charalambides, Ch A. (2002). Enumerative Combinatorics. CRC Press. p. 42. ISBN 978-1-58488-290-9.

UpToDate Contents

全文を閲覧するには購読必要です。 To read the full text you will need to subscribe.

1. 脆弱Ｘ症候群の出生前スクリーニングおよび診断 prenatal screening and diagnosis for fragile x syndrome
2. 遺伝学用語集 glossary of genetic terms
3. 末梢血塗抹標本の評価 evaluation of the peripheral blood smear

Japanese Journal

3.順列の圧縮列挙索引化とソーティング(<小特集>「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野)

川原純,湊真一
電子情報通信学会誌 97(12), 1086-1090, 2014-12-01
… 基礎的な離散構造の一つである順列(置換)は,ソーティングや順序付け,マッチング,レイアウト,符号化等,多くの実用的な問題で現れる.近年提案されたπDDは,多数の順列の集合を圧縮された状態で保持するデータ構造であり,二つの順列集合の和集合や共通集合を求める演算,二つの順列集合から任意に要素を取り出して積をとって得られる集合の計算等,各種集合 …
NAID 110009893126

1.二分決定グラフによる離散構造処理の概観(<小特集>「フカシギの数え方」から広がるアルゴリズムの理工学-二分決定グラフによる離散構造処理と広がる応用分野)

湊真一
電子情報通信学会誌 97(12), 1074-1079, 2014-12-01
… 常に重要である.本稿ではBDD(Binary Decision Diagram,二分決定グラフ)及びZDD(Zero-suppressedBDD,ゼロサプレス型BDD)を用いた離散構造データの処理技法を概観する.まずBDDによるブール演算処理,ZDDによる組合せ集合の代数処理について述べ,次に文字列集合や順列集合への発展について述べる.更に最近注目されているグラフ列挙の手法や,その適用例である「おねえさんの問題」など,本研究分野における最近の展開について紹介する. …
NAID 110009893124