置換 (数学)
実際には、与えられた 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}!}}}
によって与えられる。
この手続きにおいて、新しい巡回置換を作るための始点とする元の取り方は一通りとは限らないから、一つの置換に対する巡回置換表示は、一般には複数存在する。例えば、やはり先と同じ例で言えば
[ 1 2 3 4 5 2 5 4 3 1 ] = [ 1 2 5 ] [ 3 4 ] = [ 3 4 ] [ 1 2 5 ] = [ 3 4 ] [ 5 1 2 ] {\displaystyle {\begin{bmatrix}1&2&3&4&5\\2&5&4&3&1\end{bmatrix}}={\begin{bmatrix}1&2&5\end{bmatrix}}{\begin{bmatrix}3&4\end{bmatrix}}={\begin{bmatrix}3&4\end{bmatrix}}{\begin{bmatrix}1&2&5\end{bmatrix}}={\begin{bmatrix}3&4\end{bmatrix}}{\begin{bmatrix}5&1&2\end{bmatrix}}}
のような表示が可能である。σ の各巡回置換成分 (x1 x2 ... xl) はそれ自身が置換を表しており、具体的にはこの軌道上で σ と同じく i < l のとき xi を xi+1 に写し、xl を x1) に写す一方、この軌道に属さない S の元は何れも動かさない。位数が l であるような軌道は、長さ l の巡回置換と呼ばれる。