ריבוע לטיני

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בקומבינטוריקה, ריבוע לטיני הוא ריבוע של (נאמר) n שורות ו- n עמודות, שבכל שורה ובכל עמודה שלו כתובים אותם n סמלים, בלי חזרות.

לדוגמה:

$\begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \\ \end{bmatrix} \quad\quad \begin{bmatrix} 1 & 3 & 0 & 2 \\ 3 & 2 & 1 & 0 \\ 2 & 0 & 3 & 1 \\ 0 & 1 & 2 & 3 \end{bmatrix}$

הדוגמה הקלה ביותר היא ריבוע שבשורה ה- i ובעמודה ה-j שלו כתוב i+j-1 או i+j-1-n (בוחרים בכל מקרה את המספר שנמצא בין 1 ל- n). באופן כללי יותר, לוח הכפל של כל חבורה הוא ריבוע לטיני. בסטטיסטיקה ריבועים לטיניים משמשים בתכנון ניסויים. מקורו של המונח 'ריבוע לטיני' הוא בכך שלאונרד אוילר שחקר אותם השתמש באותיות לטיניות כסמלים.

[עריכה] פעולות על ריבועים לטיניים

[עריכה] ריבועים שקולים

אם מסדרים מחדש את השורות והעמודות של ריבוע לטיני, ומחליפים את הסימנים זה בזה, מתקבל ריבוע לטיני חדש. זוהי דוגמה לפעולה של החבורה $\ S_n\times S_n \times S_n$ (כאשר $\ S_n$ היא החבורה הסימטרית) על קבוצת הריבועים הלטיניים. לריבועים המתקבלים מריבוע נתון על-ידי פעולות אלה קוראים ריבועים שקולים (Isotopic squares). מכיוון שריבועים דומים שייכים לאותו מסלול תחת הפעולה של $\ S_n \times S_n \times S_n$ , השקילות היא אכן יחס שקילות. כשסופרים ריבועים לטיניים מגודל מסוים, נוח לספור את מחלקות השקילות במקום את הריבועים הבודדים.

[עריכה] ריבועים צמודים

נסמן ב- $\ A_{ij}$ את הערך המופיע בשורה ה-i והעמודה ה-j של הריבוע A. את התנאי על הופעת כל ערך פעם אחת בכל שורה ובכל עמודה אפשר לנסח מחדש כך: ב- $\ n^2$ השלשות $\ \{(i,j,A_{ij})\}$ , כל שני רכיבים עוברים על כל $\ n^2$ האפשרויות. מכאן רואים שהתפקידים של 'שורה', 'עמודה' ו'ערך' בתיאור של ריבוע לטיני הם סימטריים. אפשר להחליף אותם, ולקבל ריבוע חדש. זוהי למעשה פעולה נוספת, של החבורה $\ S_3$ . ששת הריבועים המתקבלים באופן זה מריבוע נתון הם צמודים (conjugate) זה לזה.

[עריכה] ריבועים דומים

כשמשלבים את השקילות והצמידות, כלומר את פעולת הערבוב של שורות, עמודות או סמלים עם פעולת ההחלפה בין שורות, עמודות וסמלים, צריך להבחין שהפעולות אינן מתחלפות: החלפת שתי שורות שלאחריה מחליפים בין תפקידי השורות והעמודות אינה זהה להחלפת התפקידים שאחריה מחליפים שתי שורות. במלים אחרות, החבורה של פעולות על ריבועים לטיניים הנוצרת מן הפעולות של $\ S_n^3$ ושל $\ S_3$ שהוזכרו קודם לכן, אינה המכפלה הישרה של שתי החבורות; זוהי דוגמה נאה למכפלת זר (wreath product), שהיא סוג מיוחד של מכפלה ישרה למחצה.

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

[עריכה] מספרם של הריבועים הלטיניים

לא ידועה נוסחה הקובעת את מספרם של הריבועים הלטיניים בגודל n; גם נוסחאות למספרן של מחלקות השקילות או של המינים, אינן ידועות. להלן מספר הריבועים בגודל n שהם 'ממוינים', כלומר שהשורה הראשונה והעמודה הראשונה ממוינות בסדר עולה (כדי לקבל את מספר הריבועים הלטיניים הכולל, יש להכפיל ב- $\ (n-1)!n!$ ).

**מספר הריבועים הלטיניים בגודל נתון**
n	מספר הריבועים הממויינים
1	1
2	1
3	1
4	4
5	56
6	9408
7	16942080
8	535281401856
9	377597570964258816
10	7580721483160132811489280
11	5363937773277371298119673540771840

להלן מספרן של מחלקות השקילות ושל המינים. מספר הריבועים במחלקת שקילות מחלק את $\ (n!)^3$ , ומספר מחלקות השקילות בכל מין מחלק את 6.

**מחלקות שקילות ומינים של ריבועים לטיניים**
n	מינים	מחלקות שקילות
1	1	1
2	1	1
3	1	1
4	2	2
5	2	2
6	12	22
7	147	564
8	283657	1676267
9	19270853541	115618721533
10	34817397894749939	208904371354363006

[עריכה] השלמה לריבוע לטיני

אחת הבעיות המעניינות הקשורות לריבועים לטיניים היא זו של השלמת מידע חלקי: נתונים חלק מהערכים בריבוע בגודל n-על-n, ומעוניינים להשלים את כל האחרים כך שיתקבל ריבוע לטיני. כמובן שהדבר בלתי אפשרי אם הערכים הנתונים כבר כוללים חזרות (בשורות או בעמודות), אבל לרוע המזל גם אם אין בנתונים חזרות, זה עדיין לא מבטיח שההשלמה אפשרית.

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

[עריכה] ריבועים מאונכים

שני ריבועים לטיניים A ו- B הם ריבועים מאונכים אם כאשר כותבים אותם יחד באותו ריבוע, $\ n^2$ הזוגות $\ (A_{ij},B_{ij})$ שונים זה מזה. במלים אחרות, כל זוג רכיבים ברביעיות $\ \{(i,j,A_{ij},B_{ij})\}$ עובר על כל $\ n^2$ האפשרויות.

בסביבות 1780 מצא לאונרד אוילר דרך לבנות זוגות של ריבועים לטיניים בכל גודל שאינו מהצורה 4m+2. מאחר שאין זוג של ריבועים לטיניים מאונכים בגודל 2, שיער אוילר שלא קיימים ריבועים מאונכים בגדלים 6, 10, 14 וכו'. ההשערה קיבלה חיזוק כאשר ב- 1901 הוכיח Gaston Tarry (באמצעות כוח גס) שלא קיים זוג ריבועים מאונכים בגודל 6. ואולם, בשנת 1959 מצאו Parker, Bose ו- Shrikhande זוג ריבועים מאונכים בגודל 10, והראו שקיים זוג כזה בכל גודל (פרט כמובן ל- 2 ו- 6).

בעיה שעדיין נותרה פתוחה, היא מציאת המספר המקסימלי של ריבועים לטיניים בגודל n, המאונכים בזוגות. ידוע כי מספר זה לא יכול לעלות על $\ n-1$ , וכי הוא שווה בדיוק למספר זה, כאשר n מספר ראשוני או חזקה של מספר ראשוני. שאלה זו קשורה גם לגאומטריה פרויקטיבית סופית: קיים מישור פרויקטיבי סופי מסדר n, אם ורק אם קיימים $\ n-1$ ריבועים לטיניים בגודל n המאונכים בזוגות.

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

להלן דוגמאות לכל המינים של ריבועים לטיניים, עד גודל 5.

$\begin{bmatrix} 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 \\ 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 1 & 4 & 3 \\ 3 & 4 & 1 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 \\ 2 & 4 & 1 & 3 \\ 3 & 1 & 4 & 2 \\ 4 & 3 & 2 & 1 \end{bmatrix}$

$\begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 5 & 1 & 4 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 2 & 5 & 3 \\ 5 & 4 & 1 & 3 & 2 \end{bmatrix} \quad \begin{bmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \\ 3 & 5 & 4 & 2 & 1 \\ 4 & 1 & 5 & 3 & 2 \\ 5 & 3 & 2 & 1 & 4 \end{bmatrix}$