תמורה (מתמטיקה)

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

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

תוכן עניינים

1 דוגמה - מהי תמורה?
2 הגדרה פורמלית
3 חבורת התמורות
4 סוגי תמורות
5 סימן של תמורה
6 ראו גם

[עריכה] דוגמה - מהי תמורה?

למשל, נסתכל על הפונקציה הבאה שפועלת על הקבוצה {1,2,3}. זו היא הפונקציה המתאימה ל־1 את 3, ל־2 את 1 ול־3 את 2. כלומר:

$\ \sigma =\left\{\begin{matrix} 1 \to 3 \\ 2 \to 1 \\ 3 \to 2 \end{matrix}\right.$

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

$\ ( 1, 2, 3 ) \to (2, 3, 1)$

כלומר, זה למעשה סידור חדש של איברי הקבוצה {1,2,3}.
צורה מקובלת לרשום תמורה היא כזאת:

$\ \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix}$

צורת רישום זו נוחה לצרכי חשבונות של הרכבת תמורות.

[עריכה] הגדרה פורמלית

תהא $\ X$ קבוצה. פונקציה $\sigma : X \to X$ תקרא תמורה על הקבוצה $\ X$ אם היא חד-חד ערכית ועל.

[עריכה] חבורת התמורות

אוסף כל התמורות מעל קבוצה X מקיימת את התכונות הבאות:

סגירות קבוצת התמורות להרכבה. כלומר, אם $\ \sigma , \tau$ הן תמורות על הקבוצה $\ X$ , אזי גם הרכבתן היא תמורה על $\ X$ .
קיום תמורה הופכית. אם $\ \sigma$ היא תמורה על $\ X$ אז יש תמורה $\ \ \sigma^{-1}$ על $\ X$ שהרכבתן היא תמורת הזהות $\ \mbox{id}$ (התמורה שאינה משנה כלל את סדר האיברים). כלומר $\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = \mbox{id}$ .
הרכבת תמורות היא פעולה אסוציאטיבית.

משלוש התכונות לעיל עולה שאוסף כל התמורות על קבוצה $\ X$ מהווה חבורה עם הפעולה של הרכבת תמורות. חבורה זו מסומנת $\ S_X$ ונקראת החבורה הסימטרית.

משפט: אם $\ X$ קבוצה סופית בעלת $\ n$ איברים אז $\ |S_X|=n!$ .

הוכחה: נסתכל על האיבר הראשון. יש $\ n$ מקומות שבהם אפשר לשבץ אותו. נשבץ אותו באחד מהם. כעת נסתכל על האיבר השני. יש רק $\ n-1$ אפשרויות בשבילו, כי מקום אחד כבר תפוס. נשבץ גם אותו ונמשיך בצורה דומה עבור כל האיברים. נקבל בסך הכול $\ n\cdot(n-1)\cdots 2\cdot 1=n!$ אפשרויות שיבוץ, על פי עקרון הכפל שבקומבינטוריקה. ולכן יש $\ n!$ תמורות אפשריות.

[עריכה] סוגי תמורות

בסעיף זה נסתכל בחבורות התמורות מעל הקבוצה $\ \{ 1,2, ..., n \}$ . במצב ההתחלתי, כל איבר נמצא במקום המתאים לו (האיבר 2, למשל, נמצא במקום השני). כאשר אנו מתארים תמורה אנו בעצם אומרים לגבי כל איבר לאיזה מקום הוא עובר. למשל: "האיבר 3 עובר למקום 5" פירושו הוא שבסדר החדש (סידור המספרים בשורה אחרי ביצוע התמורה, כלומר - הפעלת הפונקציה על כל אחד מהם) המספר 3 יופיע במקום החמישי. בהמשך לא תמיד נציין "איבר" או "מקום" ונשתמש בביטויים כמו "a עובר ל b" או "c מחליף את d" וכדומה.

חילוף:
- תמורה זו מסומנת כ (a b) והיא פשוט מחליפה בין האיברים a ו b.
- לדוגמה: הפעלת החילוף (2 1) על הקבוצה { 3 2 1 } מחזיר { 3 1 2}.
מחזור:
- תמורה זו מסומנת כ $\ \left( a_1 ... a_r \right)$ והיא מזיזה את האינדקסים המעורבים בה באופן ציקלי: האיבר a1 עובר למקום a2, האיבר a2 עובר ל a3 ... האיבר ar-1 עובר ל ar ואילו האיבר ar עובר ל a1. כלומר: כל האינדקסים המופיעים בסוגריים נעים מקום אחד קדימה (ביניהם) במעגל.
- לדוגמה: הפעלת המחזור ( 4 3 2 ) על הקבוצה { 5 4 3 2 1} תחזיר { 5 3 2 4 1}.
- נשים לב שחילוף הוא בעצם מחזור באורך 2 איברים.

[עריכה] סימן של תמורה

כל תמורה אפשר להציג כהרכבה של חילופים, בדרכים שונות. למרות שמספר החילופים אינו קבוע, מספר זה עבור תמורה נתונה הוא זוגי בכל ההצגות, או אי-זוגי בכולן. בהתאם לכך, התמורה האמורה היא תמורה "זוגית", בעלת סימן "1+"; או "אי-זוגית", בעלת סימן "1-". לדרך זו של הקצאת סימנים לתמורות יש תכונה חשובה: הסימן של מכפלת תמורות שווה למכפלת הסימנים, כך שהעתקת הסימן $\ \mbox{sgn} : S_n \to \{ +1, -1 \}$ מהווה הומומורפיזם. הגרעין של הומומורפיזם זה הוא חבורת התמורות הזוגיות.

את הסימן של $\ \sigma$ אפשר לחשב לפי הנוסחה $\ \sgn(\sigma) = \frac{\prod_{i<j}(x_j-x_i)}{\prod_{i<j}(x_{\sigma(j)}-x_{\sigma(i)})}$ , כאשר $\ x_1,\dots,x_n$ משתנים. התוצאה היא תמיד מספר, השווה ל- $\ \pm 1$ .