組合せ論の文脈で
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/06/13 13:51 UTC 版)
組合せ論において置換とは、有限集合の各元を一つずつ、かつ唯一つずつ用いて得られる列と理解するのが普通である。ここで、「列」の概念は「集合」の概念と異なり、列に現れる項は何らかの順序に従っていなければならない。つまり列は（それが空でなければ）「初項」を持ち、（長さが 2 より小さくなければ）第二項を持ち、といった具合に各項が順番に現れる。対照的に、集合の元は決まった順番を持たず、例えば {1, 2, 3} と {3, 2, 1} は見た目が異なるだけで全く同じ集合である。この意味で、n 個の元からなる有限集合 S 上の置換は、各 i を列の第 i 項へ写すものとみて {1, 2, …, n} から S への全単射である。あるいは、x < y は、列の中で x の後に y が現れるという意味でさだめて、S 上の一つの全順序を与えるものと見ることもできる。この意味での S の置換も、やはり n! 通り存在する。 置換の概念を少し弱めて「同じ元が二度は現れることがないが、与えられた集合の全ての元を使い切る必要はない」ものとした列を考えることが、初等組合せ論においてたびたびある。実際には、与えられた n 個の元からなる集合から、決められた長さ k の列を考えるという形で、この概念が用いられることが多い。これらの対象は、本項に言う置換の概念と区別するために、順列と呼ばれ、二項係数と深く関連する。 また、有限多重集合 M 上の置換は、重複置換とも呼ばれ、M の各元が、自身の M における重複度とちょうど同じ数だけ現れるような列である。M の各元の重複度が、（適当な順に）m1, m2, …, ml で、それらの和（つまり M の位数）が n であるとすると、M 上の置換の総数は多項係数 ( n m 1 , m 2 , … , m l ) = n ! m 1 ! m 2 ! ⋯ m l ! {\displaystyle {n \choose m_{1},m_{2},\ldots ,m_{l}}={\frac {n!}{m_{1}!\,m_{2}!\,\cdots \,m_{l}!}}} によって与えられる。
※この「組合せ論の文脈で」の解説は、「置換 (数学)」の解説の一部です。
「組合せ論の文脈で」を含む「置換 (数学)」の記事については、「置換 (数学)」の概要を参照ください。
- 組合せ論の文脈でのページへのリンク
