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

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

אם K={a1,a2,...,an} ונקבל תמורה σ:K→K, נרשום לעתים את הערכים כשורה שנייה מתחת לשורה של האיברים. גם מקובל לציין את התמורה על ידי התאמת האינדקסים: שורה עליונה 1,...,n ושורה תחתונה i1,...,in.

לדוגמה, σ שמקיימת 1↦2, 2↦3, 3↦1 ממקמת את הקבוצה {1,2,3} מחדש. אפשר לרשום זאת בשתי שורות: 1 2 3 / 2 3 1. הצורה הזו נוחה לחישוב הרכבות.

כל התמורות על קבוצה X יוצרות חבורה תחת הרכבה. חבורה זו מסומנת S_X ונקראת החבורה הסימטרית.
אם |X|=n אז יש בדיוק n! תמורות. ההוכחה קצרה: לבחירת מקום לכל איבר יש n·(n-1)·...·1 אפשרויות, לפי עקרון הכפל.

כשבוחנים את הקבוצה {1,2,...,n} נהיה ברור מה המשמעות של "איבר עובר למקום". מדובר בתיאור לכל איבר לאן הוא מגיע בסידור החדש.

כל תמורה ניתנת לפירוק למחזורים זרים. לדוגמה:
σ = 1↦3, 2↦1, 3↦2, 4↦4, 5↦6, 6↦5
ניתן לכתוב זאת כפירוק (1 3 2)(5 6); במחזור באורך אחד כמו 4 בדרך כלל נוטים להשמיטו.
מבנה המחזורים (אורכם ומספרם) נותן מידע חשוב. סדר התמורה שווה ל־הכפל המשותף המינימלי של אורכי המחזורים. בנוסף, אם τ תמורה כלשהי אז τστ^{-1} יש את מבנה המחזורים של σ.
כאשר גודל הקבוצה גדל לאינסוף, תוחלת האורך של המחזור הארוך ביותר שואפת להיות פרופורציונית לגודל, עם מקדם קבוע גולומב־דיקמן.

תמורה ניתנת להצגה כהרכבה של חילופים (החלפות של שני איברים). זוגיות מספר החילופים לא משתנה בכל פירוק, ולכן אפשר להגדיר את הסימן: תמורה זוגית (סימן +1) או אי־זוגית (סימן −1).
הסימן הוא הומומורפיזם sgn:S_n→{+1,−1}, והגרעין שלו הוא חבורת התמורות הזוגיות.
יש כמה הגדרות שקולות לסימן: למשל זוגיות מספר ה"היפוכים" (inversions), זוגיות מספר ההצטלבויות בייצוג קווי, או זוגיות של n−k כאשר מפרקים ל־k מחזורים זרים.

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

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

לדוגמה: 1 עובר ל־2, 2 עובר ל־3, 3 עובר ל־1.
זה מסדר את 1,2,3 בשורה חדשה.

כל הסידורים האפשריים של n איברים יוצרים קבוצה חשובה. מספר כל הסידורים הוא n פעמים n-1 פעמים ועוד..., עד 1. זאת קוראים n!.

במקום לומר "איבר" או "מקום" אפשר פשוט לומר מי עובר לאן.

מחזור הוא כאשר כמה איברים מסתובבים בזה אחר זה, כמו בלולאה.

כל סידור אפשר לכתוב כקבוצות של לולאות. לדוגמה, 1→3→2→1 ו־5↔6. כאן 4 נשאר במקום.

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

חידות כמו חידת ה־15 הן חידות של סידורים. כל מצב במשחק הוא סידור של המשבצות. לפעמים אי־אפשר לפתור חידה בגלל סימן שונה.
קוביית רוביק גם קשורה לסידורים. היא הומצאה על ידי ארנה רוביק בשנת 1974.