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

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש
6 התמורות האפשריות של שלושה עצמים (כל שורה מייצגת תמורה)

באופן אינטואיטיבי, תמורה (בלועזית: פֶּרְמוּטַצְיָה) היא סידור מחדש של העצמים בקבוצה. הגדרה פורמלית של תמורה מופיעה בהמשך ערך זה.

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

למשל, נסתכל על הפונקציה

\  \sigma =\begin{cases} 1 \mapsto 2 \\ 2 \mapsto 3 \\ 3 \mapsto 1 \end{cases}

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

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

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

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

תהא \ X קבוצה. פונקציה \sigma : X \to X תקרא תמורה על הקבוצה \ 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, \ldots, n \}. במצב ההתחלתי, כל איבר נמצא במקום המתאים לו (האיבר 2, למשל, נמצא במקום השני). כאשר אנו מתארים תמורה אנו בעצם אומרים לגבי כל איבר לאיזה מקום הוא עובר. למשל: "האיבר 3 עובר למקום 5" פירושו הוא שבסדר החדש (סידור המספרים בשורה אחרי ביצוע התמורה, כלומר - הפעלת הפונקציה על כל אחד מהם) המספר 3 יופיע במקום החמישי. בהמשך לא תמיד נציין "איבר" או "מקום" ונשתמש בביטויים כמו "a עובר ל b" או "c מחליף את d" וכדומה.

חילוף[עריכת קוד מקור | עריכה]

  • תמורה זו מסומנת כ (a b) והיא פשוט מחליפה בין האיברים a ו b.
  • לדוגמה: הפעלת החילוף (2 1) על הקבוצה { 3 2 1 } מחזיר { 3 1 2}.

מחזור[עריכת קוד מקור | עריכה]

  • מחזור (או מעגל) זו תמורה הפועלת על קבוצת מספרים באופן מעגלי: האיבר \,a_1 עובר למקום \,a_2, האיבר \,a_2 עובר ל \,a_3, עד לאיבר \,a_{r-1} העובר ל-\,a_r, ובסופו של דבר האיבר \,a_r עובר ל-\,a_1. בשל החשיבות הרבה של תמורות מסוג זה לגבי פעולות בחבורה הסימטרית, יש להן סימון מיוחד - \ \left(a_1, \ldots, a_r \right), שממנו מבינים גם שהתמורה אינה מזיזה ערכים שאינם מופיעים ברשימה \ a_1,\ldots,a_r. לדוגמה: המחזור (4 3 2) מעביר את 2 ל-3, את 3 ל-4, את 4 ל-2, ואת 1 הוא מותיר במקומו.
  • מחזור של שני איברים בלבד הוא חילוף.

פירוק למחזורים[עריכת קוד מקור | עריכה]

ניתן לפרק כל תמורה יחידה למחזורים זרים. לדוגמה, התמורה

\ \sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 2 & 4 & 6 & 5 \end{pmatrix}

ניתנת לפירוק ל \ \sigma = (132)(56). בפירוק לרוב משמיטים את המחזורים באורך אחד (בדוגמה זו זהו המחזור  \ (4) ), כיוון שמחזור באורך אחד הוא למעשה תמורת הזהות.

מבנה המחזורים של התמורה, כלומר אורך המחזורים הזרים ומספרם, מספק מידע חשוב לגבי התמורה. לדוגמה, סדר התמורה הוא המכפלה המשותפת המינימלית של אורכי המחזורים. בנוסף, הפירוק למחזורים זרים היא שמורה תחת איזומורפיזמים: אם \ \tau תמורה כלשהי, אז להצמדה \ \tau\sigma\tau^{-1} יש את אותו מבנה מחזורים של  \ \sigma .

כשגודל התמורה שואף לאינסוף, תוחלת האורך של המחזור הארוך ביותר של תמורה שואף להיות לינארי בגודל התמורה כאשר המקדם הוא קבוע גולומב-דיקמן.

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

כל תמורה אפשר להציג כהרכבה של חילופים, בדרכים שונות. למרות שמספר החילופים אינו קבוע, הזוגיות של מספר זה לא תלויה בהצגה. בהתאם לכך, התמורה האמורה היא תמורה "זוגית", כלומר בעלת סימן "1+"; או "אי-זוגית", כלומר בעלת סימן "1-". לדרך זו של הקצאת סימנים לתמורות יש תכונה חשובה: הסימן של מכפלת תמורות שווה למכפלת הסימנים, כך שהעתקת הסימן \ \mbox{sgn} : S_n \to \{ +1, -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.
  2. (-1)^{|{(i,j)|i<j,\sigma(i)>\sigma(j)}|}
  3. מייצגים את התמורה באמצעות קווים שנמתחים בין השורה 1,...,n לבין אותה השורה. זוגיות מספר ההצטלבויות שלהם היא זוגיות התמורה.
  4. מייצגים את התמורה באמצעות קווים שנמתחים בין השורה \sigma(1),...,\sigma(n) לבין אותה השורה. זוגיות מספר ההצטלבויות שלהם היא זוגיות התמורה.
  5. מפרקים את התמורה ל-k מחזורים זרים, כולל נקודות השבת. זוגיות התמורה היא זוגיות המספר n-k.
  6. מפרקים את התמורה ל-t מחזורים כלשהם, ונניח כי m מחזורים מתוכם באורך זוגי. זוגיות התמורה היא זוגיות המספר m.

תמורות ושעשועים מתמטיים[עריכת קוד מקור | עריכה]

תמורות משחקות תפקיד גם בחידות ומשחקים רבים. משחקים לשחקן בודד כגון חידת ה-15 וחידת הקובייה ההונגרית הינם למעשה משחקי תמורות. לדוגמה בחידת ה-15 המספרים מ-1 עד 15 כתובים על לוחיות המסודרות במטריצה בגודל 4X4, כאשר אחת המשבצות נותרת ריקה. במשחק בכל מהלך ניתן להזיז אל תוך המשבצת הריקה את אחת הלוחיות הסמוכות אליה. מטרת המשחק הינה לשנות את המיקום של הלוחיות בעלות המספרים 14 ו-15. את המשחק ניתן לראות כמשחק תמורות. כל מצב במשחק מהווה תמורה על 16 איברים (כולל המשבצת הריקה) וחוקי המשחק מתארים את הפעולות המותרות למעבר מתמורה אחת לאחרת. מכאן שהמצבים שניתן להגיע אליהם במשחק מהווים חבורה, שהיא תת-חבורה של כל התמורות על 16 איברים. התרגום של החידה לשפה מתמטית הינה האם המצב ההתחלתי והמצב הסופי הם שניהם בעלי אותה זוגיות, והתשובה הינה שלילית: כלומר לא ניתן לפתור את המשחק.

גם הקובייה ההונגרית, שהומצאה על ידי ארנו רוביק בשנת 1974 היא דוגמה למשחק תמורות, אם כי מורכב יותר.

ראו גם[עריכת קוד מקור | עריכה]