ריבוע לטיני
בקומבינטוריקה, ריבוע לטיני הוא ריבוע של n שורות ו-n עמודות, שבכל שורה ובכל עמודה שלו כתובים אותם n סמלים שונים, בלי חזרות.
לדוגמה:
הדוגמה הקלה ביותר היא ריבוע שבשורה ה-i ובעמודה ה-j שלו כתוב i+j-1 או i+j-1-n (בוחרים בכל מקרה את המספר שנמצא בין 1 ל-n). באופן כללי יותר, לוח הכפל של כל חבורה הוא ריבוע לטיני. בסטטיסטיקה ריבועים לטיניים משמשים בתכנון ניסויים של שני משתנים. מקורו של המונח 'ריבוע לטיני' הוא בכך שלאונרד אוילר, שחקר אותם, השתמש באותיות לטיניות כסמלים.
פעולות על ריבועים לטיניים
ריבועים שקולים
אם מסדרים מחדש את השורות או את העמודות של ריבוע לטיני, או מחליפים את הסימנים זה בזה, מתקבל ריבוע לטיני חדש. זוהי דוגמה לפעולה של החבורה (כאשר היא החבורה הסימטרית) על קבוצת הריבועים הלטיניים. לריבועים המתקבלים מריבוע נתון על ידי פעולות אלה קוראים ריבועים שקולים (Isotopic squares). מכיוון שריבועים שקולים שייכים לאותו מסלול תחת הפעולה של , השקילות היא אכן יחס שקילות. כשסופרים ריבועים לטיניים מגודל מסוים, נוח לספור את מחלקות השקילות במקום את הריבועים הבודדים.
ריבועים צמודים
נסמן ב- את הערך המופיע בשורה ה-i והעמודה ה-j של הריבוע A. את התנאי על הופעת כל ערך פעם אחת בכל שורה ובכל עמודה אפשר לנסח מחדש כך: ב- השלשות , כל שני רכיבים עוברים על כל האפשרויות. מכאן רואים שהתפקידים של "שורה", "עמודה" ו"ערך" בתיאור של ריבוע לטיני הם סימטריים. אפשר להחליף אותם, ולקבל ריבוע חדש. זוהי למעשה פעולה נוספת, של החבורה . ששת הריבועים המתקבלים באופן זה מריבוע נתון הם צמודים (conjugate) זה לזה.
ריבועים דומים
כשמשלבים את השקילות והצמידות, כלומר את פעולת הערבוב של שורות, עמודות או סמלים עם פעולת ההחלפה בין שורות, עמודות וסמלים, צריך להבחין שהפעולות אינן מתחלפות: החלפת שתי שורות שלאחריה מחליפים בין תפקידי השורות והעמודות אינה זהה להחלפת התפקידים שאחריה מחליפים שתי שורות. במילים אחרות, החבורה של פעולות על ריבועים לטיניים הנוצרת מן הפעולות של ושל שהוזכרו קודם לכן, אינה המכפלה הישרה של שתי החבורות; זוהי דוגמה נאה למכפלת זר (wreath product), שהיא סוג מיוחד של מכפלה ישרה למחצה.
אם אפשר לעבור מריבוע אחד לריבוע אחר על ידי פעולת השקילות ואחריה פעולת הדמיון (או להפך, הסדר אינו חשוב), אז שני הריבועים הם ריבועים דומים. גם יחס זה הוא יחס שקילות, והמחלקות קרויות 'מינים'. כל מין של ריבועים לטיניים כולל לכל היותר שש מחלקות-שקילות.
מספרם של הריבועים הלטיניים
לא ידועה נוסחה הקובעת את מספרם של הריבועים הלטיניים בגודל n; גם נוסחאות למספרן של מחלקות השקילות או של המינים, אינן ידועות. להלן מספר הריבועים בגודל n שהם 'ממוינים', כלומר שהשורה הראשונה והעמודה הראשונה ממוינות בסדר עולה (כדי לקבל את מספר הריבועים הלטיניים הכולל, יש להכפיל ב- ).
n | מספר הריבועים הממוינים |
1 | 1 |
2 | 1 |
3 | 1 |
4 | 4 |
5 | 56 |
6 | 9408 |
7 | 16942080 |
8 | 535281401856 |
9 | 377597570964258816 |
10 | 7580721483160132811489280 |
11 | 5363937773277371298119673540771840 |
להלן מספרן של מחלקות השקילות ושל המינים. מספר הריבועים במחלקת שקילות מחלק את , ומספר מחלקות השקילות בכל מין מחלק את 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.
טיפוסים והכללות
ריבועים סימטריים
יש התאמה חד-חד-ערכית ועל בין ריבועים לטיניים סימטריים () שהאלכסון שלהם קבוע, לבין פירוקים של הגרף השלם על n קודקודים ל-איחוד של n-1 התאמות מלאות (פירוק כזה נקרא 1-factorization).
יש התאמה חד-חד-ערכית ועל בין ריבועים לטיניים עם סימטריה מלאה (סימטריים כנ"ל, וכן אם ורק אם ), שהאלכסון שלהם הוא הזהות (), לבין מערכות שטיינר משולשות.
ריבועים מאונכים
שני ריבועים לטיניים A ו- B הם ריבועים מאונכים (או אורתוגונליים) אם כאשר כותבים אותם יחד באותו ריבוע, הזוגות שונים זה מזה. במילים אחרות, בכל זוג רכיבים ברביעיות מופיעות כל האפשרויות.
בסביבות 1780 מצא לאונרד אוילר דרך לבנות זוגות של ריבועים לטיניים בכל גודל שאינו מהצורה 4m+2. מאחר שאין זוג של ריבועים לטיניים מאונכים בגודל 2, שיער אוילר שלא קיימים ריבועים מאונכים בגדלים 6, 10, 14 וכו'. ההשערה קיבלה חיזוק כאשר ב-1901 הוכיח האיטלקי גסטון טרי (Gaston Tarry) באמצעות כוח גס שלא קיים זוג ריבועים מאונכים בגודל 6. ואולם, בשנת 1959 מצאו פארקר, בוסה ושריקאנדה (E. T. Parker, Raj Chandra Bose, Sharadchandra Shankar Shrikhande) זוג ריבועים מאונכים בגודל 10, והראו שקיים זוג כזה בכל גודל (פרט ל-2 ול-6).
בעיה שעדיין נותרה פתוחה היא מציאת המספר המקסימלי של ריבועים לטיניים בגודל n, המאונכים בזוגות. ידוע כי מספר זה לא יכול לעלות על , וכי הוא שווה בדיוק למספר זה, כאשר n מספר ראשוני או חזקה של מספר ראשוני. שאלה זו קשורה גם לגאומטריה פרויקטיבית סופית: קיים מישור פרויקטיבי סופי מסדר n, אם ורק אם קיימים ריבועים לטיניים בגודל n המאונכים בזוגות.
הרחבות למימד גבוה
היפרקוביה לטינית היא ההכללה של הריבוע הלטיני ל-n ממדים ומשמשת לתכנון ניסויים בממדים גבוהים יותר.
דוגמאות
להלן דוגמאות לכל המינים של ריבועים לטיניים, עד גודל 5.
ריבועים לטיניים וחידות מתמטיות
המשחק סודוקו מבוסס על ריבוע לטיני בגודל 9, עם דרישות נוספות על המספרים בתשעה תת-ריבועים בגודל 3.
קישורים חיצוניים
- ריבוע לטיני, באתר MathWorld (באנגלית)