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

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

6 התמורות האפשריות של שלושה עצמים (כל שורה מייצגת תמורה)

הגדרה

בהינתן קבוצה סופית ${\displaystyle K=\{a_{1},a_{2},a_{3},...,a_{n}\}}$, הפונקציה ${\displaystyle \sigma \colon K\to K}$ תיקרא תמורה אם ורק אם היא חד חד ערכית ועל. דהיינו, אם לכל ${\displaystyle 1\leq i\leq n}$ קיים ${\displaystyle 1\leq j\leq n}$ יחיד, כך ש-${\displaystyle \sigma (a_{j})=a_{i}}$.

אם ${\displaystyle \sigma (a_{j})=a_{i}}$, נהוג לסמן ${\displaystyle \sigma (a_{j})=\sigma _{j}=a_{i}}$.

כמו כן, כדי שיהיה ניתן לראות בבירור את הקשר שבין איברי הקבוצה לבין הערכים שהתמורה מתאימה להם, ניתן לייצג את התמורה במטריצה מסדר ${\displaystyle 2\times n}$ מהצורה ${\displaystyle {\begin{pmatrix}a_{1}&a_{2}&...&a_{n}\\\sigma _{1}&\sigma _{2}&...&\sigma _{n}\end{pmatrix}}}$. נפוץ גם הכתיב ${\displaystyle {\begin{pmatrix}\sigma _{1}&\sigma _{2}&\dots &\sigma _{n}\end{pmatrix}}}$.

יתר על כן, אם נסמן ${\displaystyle \sigma _{1}=a_{i_{1}},\sigma _{2}=a_{i_{2}},\dots ,\sigma _{n}=a_{i_{n}}}$ כאשר גם ${\displaystyle a_{i_{1}},a_{i_{2}},...,a_{i_{n}}}$ הם איברי הקבוצה ${\displaystyle K}$ (מאחר שהתמורה היא פונקציה מ-${\displaystyle K}$ לעצמה), נוכל לדבר על התאמה של אינדקסים. כלומר, נוכל לומר שהתמורה מתאימה לאינדקס 1 (לאיבר ${\displaystyle a_{1}}$) את האינדקס ${\displaystyle i_{1}}$ (האיבר ${\displaystyle a_{i_{1}}}$), ולפיכך ניתן לכתוב את התמורה גם בצורה הבאה (שתשקף את אינדקס האיבר המותאם לכל איבר אחר על ידי התמורה):${\displaystyle {\begin{pmatrix}1&2&...&n\\i_{1}&i_{2}&...&i_{n}\end{pmatrix}}}$.

דוגמה

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

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

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

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

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

חבורת התמורות

אוסף כל התמורות מעל קבוצה ${\displaystyle X}$ מקיימת את התכונות הבאות:

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

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

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

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

סוגי תמורות

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

חילוף

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

מחזור

• מחזור (או מעגל) הוא תמורה הפועלת על קבוצת מספרים באופן מעגלי: האיבר ${\displaystyle a_{1}}$ עובר למקום ${\displaystyle a_{2}}$, האיבר ${\displaystyle a_{2}}$ עובר ל־${\displaystyle a_{3}}$, עד לאיבר ${\displaystyle a_{r-1}}$ העובר ל־${\displaystyle a_{r}}$, והאיבר האחרון בסדרה, ${\displaystyle a_{r}}$ עובר ל־${\displaystyle a_{1}}$. בשל חשיבותן הרבה של תמורות מסוג זה לגבי פעולות בחבורה הסימטרית, יש להן סימון מיוחד: ${\displaystyle (a_{1}\;a_{2}\;\dots \;a_{r})}$. מסימון זה מובן גם שהתמורה אינה מזיזה ממקומם איברים שאינם מופיעים ברשימה ${\displaystyle a_{1},\ldots ,a_{r}}$. לדוגמה: המחזור ${\displaystyle (2\;3\;4)}$ מעביר את ${\displaystyle 2}$ ל־${\displaystyle 3}$, את ${\displaystyle 3}$ ל־${\displaystyle 4}$, את ${\displaystyle 4}$ ל־${\displaystyle 2}$, ומותיר (למשל) את ${\displaystyle 1}$ במקומו.
• חילוף הוא מקרה פרטי של מחזור: כאשר במחזור שני איברים בלבד הוא שקול לחילוף.

פירוק למחזורים

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

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

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

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

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

סימן של תמורה

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

הגדרות שקולות לסימן של תמורה

1. הסימן של ${\displaystyle \sigma }$ הוא ${\displaystyle \operatorname {sgn}(\sigma )={\frac {\prod _{i<j}(x_{j}-x_{i})}{\prod _{i<j}(x_{\sigma (j)}-x_{\sigma (i)})}}}$, כאשר ${\displaystyle x_{1},\dots ,x_{n}}$ משתנים. התוצאה תמיד שווה או ל-${\displaystyle 1}$ או ל${\displaystyle -1}$.
2. ${\displaystyle (-1)^{|\{(i,j)|i<j,\sigma (i)>\sigma (j)\}|}}$
3. מייצגים את התמורה באמצעות קווים שנמתחים בין השורה ${\displaystyle 1,...,n}$ לבין אותה השורה. זוגיות מספר ההצטלבויות שלהם היא זוגיות התמורה.
4. מייצגים את התמורה באמצעות קווים שנמתחים בין השורה ${\displaystyle \sigma (1),...,\sigma (n)}$ לבין אותה השורה. זוגיות מספר ההצטלבויות שלהם היא זוגיות התמורה.
5. מפרקים את התמורה ל-${\displaystyle k}$ מחזורים זרים, כולל נקודות השבת. זוגיות התמורה היא זוגיות המספר ${\displaystyle n-k}$.
6. מפרקים את התמורה ל-${\displaystyle t}$ מחזורים כלשהם, ונניח כי m מחזורים מתוכם באורך זוגי. זוגיות התמורה היא זוגיות המספר ${\displaystyle m}$.

תמורות ושעשועים מתמטיים

חידת ה-15

קובייה הונגרית

תמורות משחקות תפקיד גם בחידות ומשחקים רבים. משחקים לשחקן בודד כגון חידת ה-15 וחידת הקובייה ההונגרית הם למעשה משחקי תמורות:

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

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

ראו גם

מיזמי קרן ויקימדיה
ספר לימוד בוויקיספר: מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה
תמונות ומדיה בוויקישיתוף: תמורה (מתמטיקה)

• תורת החבורות
• החבורה הסימטרית

קישורים חיצוניים

• תמורה, באתר אנציקלופדיה בריטניקה (באנגלית)
• תמורה, באתר MathWorld (באנגלית)