Permutations

#abstract_algebra #computer_science

תמורה היא פונקצייה חח״ע ועל $σ : [n] \to [n]$ . אוסף התמורות על $n$ איברים מסומן כ $S_{n}$ ועוצמתו היא $n!$ .
$S_{n}$ נקרא גם חבורת התמורות.

דוגמה לתמורה מעל $S_{3}$ למשל תהיה :

\begin{matrix} σ : {1, 2, 3} \to {1, 2, 3} \\ σ (1) = 2 \\ σ (2) = 1 \\ σ (3) = 3 \end{matrix}

תמורת הזהות

נסמן אותה כ $I$ שזה גם הסימון של פונקציית הזהות וזאת פשוט תמורה שבה כל איבר הולך לעצמו

דרכים מקובלות לסמן תמורה

כפונקצייה:

(\begin{matrix} 1 & 2 & 3 & \dots & n \\ σ (1) & σ (2) & σ (3) & \dots & σ (n) \end{matrix})

כמחזורים זרים :
אדגים זאת כאן אבל פירוט נוסף נמצא בהסבר על חבורת התמורות
למשל עבור התמורה

(\begin{matrix} 1 & 2 & 3 \\ 2 & 1 & 3 \end{matrix})

נוכל לסמן אותה גם כ

σ = (1, 2) (3)

זה בעצם סימון שמפריד את התמורה לחלקים שקוראים אחד לשני...

בתמורה ישנו מצב של חילוף סדר שמשמעו

(i < j) \land (σ (i) > σ (j))

מעקב אחרי הערכים (זאת שיטה פחות יעילה):
למשל עבור $σ (1, 3, 2)$ נבנה טבלה של כל הערכים שקטנים אחד מהשני ומה קורה כשמפעלים את הפרמוטצייה:

1<2	1<3	2<3
$σ (1) > σ (2)$	$σ (1) > σ (3)$	$σ (2) < σ (3)$

ולכן מספר חילופי הסדר בתמורה הוא $2$

השיטה הציורית

לכל תמורה יש סימן התלוי במספר חילופי הסדר, נסמן את מספר חילופי הסדר ב $k$ ויתקיים

s i g n (σ) = (- 1)^{k}

זוגיות ואי זוגיות של תמורה:

תמורה תקרא זוגית אם $s i g n (σ) = 1$ ואי זוגית אם $s i g n (σ) = - 1$

הגדרה נוספת לסימן התמורה :
נגדיר את סימן התמורה $f$ להיות

\prod_{i \neq j} \frac{f (i) - f (j)}{i - j}

למשל עבור התמורה

f = (\begin{matrix} 1 & 2 & 3 \\ 3 & 1 & 2 \end{matrix})

יתקיים

s i g n (f) = \frac{3 - 1}{1 - 2} \cdot \frac{3 - 2}{1 - 3} \cdot \frac{1 - 2}{2 - 3} = (- 1) (- 1) = 1