置換

定義 集合 X 的置換是 X 到其自身的雙射。

n個元素的集合X恰有 n! 個置換。

置換也可看成集合 X 中元素的重排。

比如 {1, 2, 3} 的重排有：

123；132；213；231；312；321

X的一次重排i_1，i_2，...，i_n確定了一個函數alpha:X->X，即：

alpha(i) = i_1，alpha(2) = i_2， ...，alpha(n) = i_n。

例如重排213對應的函數alpha是：

alpha(1) = 2，alpha(2) = 1，alpha(3) = 3。

自變量就是下標1，2，...，n；函數值則是下標對應的元素。

這里用函數的觀點來表達重排的概念，還是比較好理解的。

這個函數有如下特點：

• 函數中包括了X中的所有元素，即alpha是一個滿射
• 無重復元素說明了不同的點有不同的值，alpha是一個單射
• 因此，alpha是一個雙射alpha：X->X

把置換看做函數的好處是可以對它們進行復合，置換的復合仍是置換（需要證明）。

對稱群

引出對稱群的概念

定義 稱集合X的全體置換的族為X上的對稱群，記為S_X。當X={1,2,...,n}時，常用S_n來記S_X，并稱之為n個字母上的對稱群。

看到這里來有點懵逼了，怎么一下子來了個對稱群？先不糾結這個了。其實可以這樣，就是把集合上的所有置換取了一個名字而已。

beta?·?alpha是函數的復合操作，只不過這里要注意的是運算順序是從左至右的，先算alpha，然后再算beta。

?

S_3中的復合是不交換的（會舉例說明）。

兩個置換可以交換么？

一個置換的平方是恒等函數嗎？（我猜這里的平方是進行兩次相同的操作，比如原來是beta?·?alpha這種復合操作，然后平方就是alpha·?alpha）

輪換

上一個部分留了幾個問題，直接去想這幾個問題有難度，這里進而引入了輪換的概念。

定義 設i_1,i_2,...,i_r是{1,2,...,n}中的不同整數。如果alpha屬于S_n固定其他整數（如果有的話），且

alpha(i_1) = i_2，alpha(i_2) = i_3，...，alpha(i_r-1) = i_r，alpha(i_r) = i_1，

則稱alpha為一個r-輪換，也稱alpha為長r的輪換，記為

alpha = (i_1i_2...i_r)

第一眼看的話肯定會懵逼，這他媽的是啥？

輪換其實是一種特殊的置換，集合中的元素重排的是時候會遵循一種循環。

2-輪換把i_1和i_2對調而其余的不動，2-輪換也叫對換。

1-輪換是恒等函數，因為它們固定每個i。

輪換中的任一i_j可以作為起點，因此任一r-輪換有r中不同的輪換記號：

(i_1i_2...i_r) = (i_2i_3...i_ri_1) = ... = (i_ri_1i_2...i_r-1)。

?

輪換的作用是，可以把置換分解成輪換乘積，就問你屌不屌。

不相交

之前就說過，輪換其實即使一種特殊的置換，因為你可以固定其他的元素，而只有r-輪換，這樣不就補全成為了一個置換么。

定義 稱兩個置換alpha，beta屬于S_n不相交，如果每個i被一個移動而被另一個固定：如果alpha(i) != i，則beta(i)=i，且如果beta(j) != j，則alpha(j) = j。稱置換族beta_1，...，beta_t不相交，如果它們兩兩不相交。

為啥他喵的要引入不相交的概念？

?

緊接著證明就來了

引理 不相交的置換alpha，beta是可以交換的。

?

休息一會，要炸了

?

命題 每個置換alpha屬于S_n，不是一個輪換就是不相交輪換的乘積。

?

總結

以上是生活随笔為你收集整理的置换的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。