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

קובץ:Permutations RGB.svg

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

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

הגדרה

בהינתן קבוצה סופית $K=\{a_{1},a_{2},a_{3},...,a_{n}\}$, הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma \colon K \to K} תיקרא תמורה אם ורק אם היא חד חד ערכית ועל, דהיינו אם לכל הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\leq i \leq n} קיים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1\leq j \leq n} יחיד, כך ש-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma (a_j)=a_i} .

אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma (a_j)=a_i} , נהוג לסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma (a_j)=\sigma _j=a_i} .

כמו כן, כדי שיהיה ניתן לראות בבירור את הקשר שבין איברי הקבוצה לבין הערכים שהתמורה מתאימה להם, ניתן לייצג את התמורה במטריצה מסדר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\times n} מהצורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix} a_1 & a_2 & ... & a_n \\ \sigma_1 & \sigma_2 & ... & \sigma_n \end{pmatrix}} . נפוץ גם הכתיב הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix} \sigma_1 & \sigma_2 & \dots & \sigma_n \end{pmatrix}} .

יתר על כן, אם נסמן הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma_1=a_{i_1}, \sigma_2=a_{i_2} ,\dots, \sigma_n=a_{i_n}} כאשר גם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{i_1},a_{i_2},...,a_{i_n}} הם איברי הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} (מאחר שהתמורה היא פונקציה מ-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} לעצמה), נוכל לדבר על התאמה של אינדקסים. כלומר, נוכל לומר שהתמורה מתאימה לאינדקס 1 (לאיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1} ) את האינדקס הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle i_1} (האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_{i_1}} ), ולפיכך ניתן לכתוב את התמורה גם בצורה הבאה (שתשקף את אינדקס האיבר המותאם לכל איבר אחר על ידי התמורה):הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{pmatrix} 1 & 2 & ... & n \\ i_1 & i_2 & ... & i_n \end{pmatrix}} .

דוגמה

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma =\begin{cases} 1 \mapsto 2 \\ 2 \mapsto 3 \\ 3 \mapsto 1 \end{cases}}

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

הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma = \begin{pmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \end{pmatrix} }

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

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

אוסף כל התמורות מעל קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} מקיימת את התכונות הבאות:

• סגירות קבוצת התמורות להרכבה. כלומר, אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma, \tau} הן תמורות על הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} , גם הרכבתן היא תמורה על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} .
• קיום תמורה הופכית – אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma} היא תמורה על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} אז יש תמורה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma^{-1}} על הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} שהרכבתן היא תמורת הזהות, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mbox{id}} (התמורה שאינה משנה כלל את סדר האיברים). כלומר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \sigma \circ \sigma^{-1} = \sigma^{-1} \circ \sigma = \mbox{id} } .
• הרכבת תמורות היא פעולה אסוציאטיבית.

משלוש התכונות לעיל עולה שאוסף כל התמורות על קבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} מהווה חבורה עם הפעולה של הרכבת תמורות. חבורה זו מסומנת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle S_X} ונקראת החבורה הסימטרית.

משפט: אם הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle X} קבוצה סופית בעלת הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} איברים אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle |S_X| = n!} .

הוכחה: נסתכל על האיבר הראשון. יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} מקומות שבהם אפשר לשבץ אותו. נשבץ אותו באחד מהם. כעת נסתכל על האיבר השני. יש רק הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n-1} אפשרויות בשבילו, כי מקום אחד כבר תפוס. נשבץ גם אותו ונמשיך בצורה דומה עבור כל האיברים. נקבל בסך הכול הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \cdot(n-1) \cdots 2 \cdot 1 = n!} אפשרויות שיבוץ, על פי עקרון הכפל שבקומבינטוריקה; ולכן יש הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle n!} תמורות אפשריות.

סוגי תמורות

קל להבין את סוגי התמורות השונות, אם נסתכל על הקבוצה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2, \ldots, n\}} . במצב ההתחלתי, כל איבר נמצא במקום המתאים לו (האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2} , למשל, נמצא במקום השני). כאשר אנו מתארים תמורה אנו בעצם אומרים לגבי כל איבר לאיזה מקום הוא עובר. למשל: "האיבר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} עובר למקום הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 5} " פירושו הוא שבסדר החדש (סידור המספרים בשורה אחרי ביצוע התמורה, כלומר - הפעלת הפונקציה על כל אחד מהם) המספר הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} יופיע במקום החמישי. בהמשך לא תמיד נציין "איבר" או "מקום" ונשתמש בביטויים כמו "הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} עובר ל־הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} " או "הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} מחליף את הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} " וכדומה.

חילוף

• תמורה זו מסומנת כ־הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (a \; b)} , והיא פשוט מחליפה בין האיברים הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} ו־$b$.
• לדוגמה: הפעלת החילוף $(1\;2)$ על $(1\;2\;3)$ מחזירה $(2\;1\;3)$.

מחזור

• מחזור (או מעגל) הוא תמורה הפועלת על קבוצת מספרים באופן מעגלי: האיבר $a_{1}$ עובר למקום $a_{2}$, האיבר $a_{2}$ עובר ל־$a_{3}$, עד לאיבר $a_{r-1}$ העובר ל־$a_{r}$, והאיבר האחרון בסדרה, $a_{r}$ עובר ל־$a_{1}$. בשל חשיבותן הרבה של תמורות מסוג זה לגבי פעולות בחבורה הסימטרית, יש להן סימון מיוחד: $(a_{1}\;a_{2}\;\dots \;a_{r})$. מסימון זה מובן גם שהתמורה אינה מזיזה ממקומם איברים שאינם מופיעים ברשימה $a_{1},\ldots ,a_{r}$. לדוגמה: המחזור $(2\;3\;4)$ מעביר את $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}}\colon S_{n}\to \{+1,-1\}$, מהווה הומומורפיזם. הגרעין של הומומורפיזם זה הוא חבורת התמורות הזוגיות.

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

1. הסימן של $\sigma$ הוא $\operatorname {sgn}(\sigma )={\frac {\prod _{i<j}(x_{j}-x_{i})}{\prod _{i<j}(x_{\sigma (j)}-x_{\sigma (i)})}}$, כאשר $x_{1},\dots ,x_{n}$ משתנים. התוצאה תמיד שווה או ל-$1$ או ל$-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-puzzle-loyd.svg

חידת ה-15

קובץ:Rubiks cube scrambled.jpg

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

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

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

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

ראו גם

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

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

• 
  שגיאות פרמטריות בתבנית:בריטניקה
  פרמטרי חובה [ 1 ] חסרים
• תמורה, באתר MathWorld (באנגלית)   

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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