הצגת המקור של הדף "תמורה (מתמטיקה)"

[[קובץ:Permutations RGB.svg|ממוזער|6 התמורות האפשריות של שלושה עצמים (כל שורה מייצגת תמורה)]]
'''תְּמוּרָה''' או '''פֶּרְמוּטַצְיָה''' היא [[פונקציה חד-חד-ערכית ועל]] מקבוצה לעצמה. באופן אינטואיטיבי ניתן לראות בתמורה כסידור מחדש של איברים ב[[קבוצה (מתמטיקה)|קבוצה]]. לפיכך, בניגוד ל[[צירוף (קומבינטוריקה)|צירוף]], בתמורה יש חשיבות לסדר. 

==הגדרה==
בהינתן קבוצה סופית <math>K=\{a_1,a_2,a_3,...,a_n\}</math>, הפונקציה <math>\sigma \colon K \to K</math> תיקרא תמורה [[אם ורק אם]] היא חד חד ערכית ועל. דהיינו, אם לכל <math>1\leq i \leq n</math> קיים <math>1\leq j \leq n</math> יחיד, כך ש-<math>\sigma (a_j)=a_i</math>.

אם <math>\sigma (a_j)=a_i</math>, נהוג לסמן <math>\sigma (a_j)=\sigma _j=a_i</math>.

כמו כן, כדי שיהיה ניתן לראות בבירור את הקשר שבין איברי הקבוצה לבין הערכים שהתמורה מתאימה להם, ניתן לייצג את התמורה במטריצה מסדר <math>2\times n</math> מהצורה <math>\begin{pmatrix} a_1 & a_2 & ... & a_n \\ \sigma_1 & \sigma_2 & ... & \sigma_n \end{pmatrix}</math>. נפוץ גם הכתיב <math>\begin{pmatrix}
\sigma_1 & \sigma_2 & \dots & \sigma_n
\end{pmatrix}</math>.

יתר על כן, אם נסמן <math>\sigma_1=a_{i_1}, \sigma_2=a_{i_2} ,\dots, \sigma_n=a_{i_n}</math> כאשר גם <math>a_{i_1},a_{i_2},...,a_{i_n}</math> הם איברי הקבוצה <math>K</math> (מאחר שהתמורה היא פונקציה מ-<math>K</math> לעצמה), נוכל לדבר על התאמה של אינדקסים. כלומר, נוכל לומר שהתמורה מתאימה לאינדקס 1 (לאיבר <math>a_1</math>) את האינדקס <math>i_1</math> (האיבר <math>a_{i_1}</math>), ולפיכך ניתן לכתוב את התמורה גם בצורה הבאה (שתשקף את אינדקס האיבר המותאם לכל איבר אחר על ידי התמורה):<math>\begin{pmatrix}
1 & 2 & ... & n \\
i_1 & i_2 & ... & i_n
\end{pmatrix}</math>.

==דוגמה==
נסתכל למשל על ה[[פונקציה]]
:<math>\sigma =\begin{cases} 1 \mapsto 2 \\ 2 \mapsto 3 \\ 3 \mapsto 1 \end{cases}</math>
זו היא הפונקציה המתאימה ל־1 את 2, ל־2 את 3 ול־3 את 1, ובכך מסדרת מחדש את הקבוצה {1,2,3}.
צורה מקובלת לרשום תמורה היא כזאת:
: <math>\sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} </math>
צורת רישום זו נוחה לצורכי חשבונות של הרכבת תמורות.
==חבורת התמורות==
'''אוסף כל התמורות''' מעל קבוצה <math>X</math> מקיימת את התכונות הבאות:
*'''[[סגירות (אלגברה)|סגירות]] קבוצת התמורות [[הרכבת פונקציות|להרכבה]]'''. כלומר, אם <math>\sigma, \tau</math> הן תמורות על הקבוצה <math>X</math>, גם הרכבתן היא תמורה על <math>X</math>.
*'''קיום תמורה הופכית''' – אם <math>\sigma</math> היא תמורה על <math>X</math> אז יש תמורה <math>\sigma^{-1}</math> על <math>X</math> שהרכבתן היא תמורת ה[[פונקציית הזהות|זהות]], <math>\mbox{id}</math> (התמורה שאינה משנה כלל את סדר האיברים). כלומר <math>\sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = \mbox{id} </math>.
*'''הרכבת תמורות היא [[אופרטור|פעולה]] [[פעולה אסוציאטיבית|אסוציאטיבית]]'''.

משלוש התכונות לעיל עולה שאוסף כל התמורות על קבוצה <math>X</math> מהווה [[חבורה (מבנה אלגברי)|חבורה]] עם הפעולה של [[הרכבת פונקציות|הרכבת תמורות]]. חבורה זו מסומנת <math>S_X</math> ונקראת [[החבורה הסימטרית]].

'''משפט:''' אם <math>X</math> [[קבוצה סופית]] בעלת <math>n</math> איברים אז <math>|S_X| = n!</math>.

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

ההוכחה לכך היא באינדוקציה:
* שלב הבסיס: עבור n=1 ברור שיש רק תמורה אחת. עבור n=2 יש רק שתי תמורות: תמורת הזהות וחילוף מקום.
* שלב האינדוקציה: נוכל להניח בלי הגבלת הכלליות שהמרחב X מורכב מהמספרים 1, 2, ..., n ונניח שאנו יודעים שעל מרחב בין n-1 איברים יש <math>(n-1)!</math> תמורות. מספר התמורות על הקבוצה 1 עד n הוא מספר האפשרויות לסדר את המספרים 1, 2, ..., n בשורת משבצות הממוספרות גם הן מ 1 עד n. נסתכל על האיבר n ונשים אותו באיזשהי משבצת. יש n אפשרויות לבחור משבצת למקם אותו. אחרי שמיקמנו אותו נסתכל על שאר האיברים: נותר לנו לסדר n-1 מספרים ב n-1 משבצות, אבל הרי זה בדיוק מספר התמורות מעל קבוצה בעלת n-1 איברים.
* מסקנה: אם נסמן את מספר התמורות מעל קבוצה בת n איברים ב <math>|S_n |</math> אזי באינדוקציה הוכחנו ש <math>| S_n | = n \cdot | S_{n-1} |</math>. בשילוב תנאי ההתחלה ש <math>|S_1| = 1</math> נובע שקיבלנו את ההגדרה הרקורסיבית של [[עצרת]] ולכן <math>|S_n| = n!</math> .
-->

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

===חילוף===
* תמורה זו מסומנת כ־<math>(a \; b)</math>, והיא פשוט מחליפה בין האיברים <math>a</math> ו־<math>b</math>.
* לדוגמה: הפעלת החילוף <math>(1 \; 2)</math> על <math>(1 \; 2 \; 3)</math> מחזירה <math>(2 \; 1 \; 3)</math>.

===מחזור===
* מחזור (או מעגל) הוא תמורה הפועלת על קבוצת מספרים באופן מעגלי: האיבר <math>a_1</math> עובר למקום <math>a_2</math>, האיבר <math>a_2</math> עובר ל־<math>a_3</math>, עד לאיבר <math>a_{r-1}</math> העובר ל־<math>a_r</math>, והאיבר האחרון בסדרה, <math>a_r</math> עובר ל־<math>a_1</math>. בשל חשיבותן הרבה של תמורות מסוג זה לגבי פעולות ב[[החבורה הסימטרית|חבורה הסימטרית]], יש להן סימון מיוחד: <math>(a_1 \; a_2 \; \dots \; a_r)</math>. מסימון זה מובן גם שהתמורה אינה מזיזה ממקומם איברים שאינם מופיעים ברשימה <math>a_1,\ldots,a_r</math>. לדוגמה: המחזור <math>(2 \; 3 \; 4)</math> מעביר את <math>2</math> ל־<math>3</math>, את <math>3</math> ל־<math>4</math>, את <math>4</math> ל־<math>2</math>, ומותיר (למשל) את <math>1</math> במקומו.
* חילוף הוא [[מקרה פרטי]] של מחזור: כאשר במחזור שני איברים בלבד הוא שקול לחילוף.

==פירוק למחזורים==
ניתן לפרק כל תמורה יחידה למחזורים זרים. לדוגמה, התמורה
: <math>\sigma = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6\\ 3 & 1 & 2 & 4 & 6 & 5 \end{pmatrix} </math>
ניתנת לפירוק ל <math>\sigma = (132)(56)</math>. בפירוק לרוב משמיטים את המחזורים באורך אחד (בדוגמה זו זהו המחזור <math>(4)</math>), כיוון שמחזור באורך אחד הוא למעשה תמורת ה[[פונקציית הזהות|זהות]].

מבנה המחזורים של התמורה, כלומר אורך המחזורים הזרים ומספרם, מספק מידע חשוב לגבי התמורה. לדוגמה, [[סדר (תורת החבורות)#סדר של איבר בחבורה|סדר]] התמורה הוא ה[[כפולה משותפת מינימלית|כפולה המשותפת המינימלית]] של אורכי המחזורים. בנוסף, הפירוק למחזורים זרים הוא [[שמורה (מתמטיקה)|שמורה]] תחת [[איזומורפיזם#איזומורפיזם בין חבורות|איזומורפיזמים]]: אם <math>\tau</math> תמורה כלשהי, אז ל[[הצמדה (תורת החבורות)|הצמדה]] <math>\tau\sigma\tau^{-1}</math> יש מבנה מחזורים זהה לזה של <math>\sigma</math>.

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

==סימן של תמורה==
כל תמורה אפשר להציג כ[[הרכבת פונקציות|הרכבה]] של חילופים, בדרכים שונות. אף על פי שמספר החילופים אינו קבוע, הזוגיות של מספר זה לא תלויה בהצגה. בהתאם לכך, התמורה האמורה היא תמורה "זוגית", כלומר בעלת '''סימן''' "<math>+1</math>"; או "אי-זוגית", כלומר בעלת סימן "<math>-1</math>". לדרך זו של הקצאת סימנים לתמורות יש תכונה חשובה: הסימן של מכפלת תמורות שווה למכפלת הסימנים, כך שהעתקת הסימן, <math>\mbox{sgn} \colon S_n \to \{ +1,-1 \}</math>, מהווה [[הומומורפיזם (אלגברה)|הומומורפיזם]]. הגרעין של הומומורפיזם זה הוא [[חבורת התמורות הזוגיות]].

;הגדרות שקולות לסימן של תמורה
# הסימן של <math>\sigma</math> הוא <math>\sgn(\sigma) = \frac{\prod_{i<j}(x_j-x_i)}{\prod_{i<j}(x_{\sigma(j)}-x_{\sigma(i)})}</math>, כאשר <math>x_1,\dots,x_n</math> משתנים. התוצאה תמיד שווה או ל-<math>1</math> או ל<math>-1</math>.
# <math>(-1)^{|\{(i,j)|i<j,\sigma(i)>\sigma(j)\}|}</math>
# מייצגים את התמורה באמצעות קווים שנמתחים בין השורה <math>1,...,n</math> לבין אותה השורה. זוגיות מספר ההצטלבויות שלהם היא זוגיות התמורה.
# מייצגים את התמורה באמצעות קווים שנמתחים בין השורה <math>\sigma(1),...,\sigma(n)</math> לבין אותה השורה. זוגיות מספר ההצטלבויות שלהם היא זוגיות התמורה.
# מפרקים את התמורה ל-<math>k</math> מחזורים זרים, כולל נקודות השבת. זוגיות התמורה היא זוגיות המספר <math>n-k</math>.
# מפרקים את התמורה ל-<math>t</math> מחזורים כלשהם, ונניח כי m מחזורים מתוכם באורך זוגי. זוגיות התמורה היא זוגיות המספר <math>m</math>.

==תמורות ושעשועים מתמטיים==
[[קובץ:15-puzzle-loyd.svg|ממוזער|שמאל|100px|[[חידת ה-15]]]]
[[קובץ:Rubiks cube scrambled.jpg|שמאל|ממוזער|100px|[[קובייה הונגרית]]]]
תמורות משחקות תפקיד גם ב[[שעשועי מתמטיקה|חידות ומשחקים]] רבים. משחקים לשחקן בודד כגון [[חידת ה-15]] וחידת [[קובייה הונגרית|הקובייה ההונגרית]] הם למעשה משחקי תמורות:

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

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

<!-- כאשר ממלאים טופס [[לוטו]], לא משנה מהו סדר המספרים שיוצאים בהגרלה, אלא המספרים עצמם שאתה ממלא, לפיכך כל האפשרויות הקיימות בלוטו, יכולות להצטמצם לכמה קבוצות. (לא קשור לכאן) -->
{{-}}

==ראו גם==
{{מיזמים|ויקיספר=מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה/תמורות|שם ויקיספר=מתמטיקה תיכונית/אלגברה תיכונית/קומבינטוריקה}}
* [[תורת החבורות]]
* [[החבורה הסימטרית]]

==קישורים חיצוניים==
* {{בריטניקה}}
* {{MathWorld}}

{{בקרת זהויות}}

[[קטגוריה:תורת החבורות]]
[[קטגוריה:קומבינטוריקה]]
[[קטגוריה:פונקציות מתמטיות: מאפיינים]]