مرتبهٔ مربع لاتین: عدد n در مربع n × n
تعریف مربع لاتین و مفهوم مرتبه
مربع لاتین1 جدولی n × n است که در هر سطر و هر ستون آن، هر یک از n نماد (معمولاً اعداد از 1 تا n یا حروف لاتین) دقیقاً یک بار ظاهر میشود. عدد n را مرتبهٔ مربع لاتین مینامند. به عبارت دیگر، مرتبه نشاندهندهٔ ابعاد مربع و همچنین تعداد نمادهای متمایز به کار رفته در آن است.
برای مرتبهٔ n=1 فقط یک مربع لاتین بدیهی وجود دارد: یک خانه با یک نماد. برای n=2 دو نوع مربع لاتین(با جابهجایی سطرها) وجود دارد. هرچه مرتبه بزرگتر شود، تعداد مربعهای لاتین ممکن به سرعت افزایش مییابد. این رشد سریع نشاندهندهٔ پیچیدگی ترکیباتی این ساختارهاست.
| مرتبه (n) | تعداد مربعهای لاتین کاهشناپذیر | تعداد کل مربعهای لاتین (با احتساب همریختی) |
|---|---|---|
| 1 | 1 | 1 |
| 2 | 1 | 2 |
| 3 | 1 | 12 |
| 4 | 4 | 576 |
| 5 | 56 | 161280 |
روشهای ساخت مربع لاتین برای مرتبهٔ دلخواه
سادهترین روش برای ساختن یک مربع لاتین مرتبهٔ n استفاده از روش چرخش سطری است. در این روش، سطر اول را به صورت 1,2,3,…,n مینویسیم. هر سطر بعدی با انتقال یک خانه به چپ (یا راست) از سطر قبلی به دست میآید. این روش یک مربع لاتین کاهشپذیر تولید میکند که به آن مربع چرخهای میگویند.
روش دیگر استفاده از عملگرهای گروهی است. اگر نمادها را عناصر یک گروه جمعی2 مانند (Z_n , +) در نظر بگیریم، میتوانیم خانهٔ (i,j) را با جمع i+j (به پیمانهٔ n) پر کنیم. این روش به ازای هر مرتبهٔ n یک مربع لاتین معتبر میدهد. مثال مرتبهٔ 5:
کاربرد عملی: طراحی آزمایشها و جدول سودوکو
یکی از مشهورترین کاربردهای مربع لاتین در آمار و طراحی آزمایشها3 است. زمانی که بخواهیم تأثیر چند عامل را بدون افزایش تصاعدی تعداد آزمایشها بررسی کنیم، از طرح مربع لاتین استفاده میشود. فرض کنید میخواهیم تأثیر 4 نوع کود، 4 روش آبیاری و 4 نوع خاک را روی محصولی آزمایش کنیم. با یک مربع لاتین مرتبهٔ 4 میتوانیم تعداد کرتها را به 16 کاهش دهیم در حالی که هر ترکیب به طور متوازن بررسی میشود.
همچنین بازی جدول سودوکو چیزی جز یک مربع لاتین مرتبهٔ 9 با قید اضافی بلوکهای 3×3 نیست. در حقیقت سودوکو یک مربع لاتین مرتبهٔ 9 است که به 9 زیرمربع 3×3 تقسیم شده و در هر زیرمربع نیز اعداد 1 تا 9 یک بار ظاهر میشوند. بنابراین درک مربع لاتین اولین گام برای حل حرفهای سودوکو است.
چالشهای مفهومی در مورد مرتبهٔ مربع لاتین
دو مربع لاتین متعامد هستند وقتی که جفتهای متناظر آنها همه جفتهای ممکن نمادها را دقیقاً یک بار تولید کنند. برای مرتبهٔ n=2 جفت مربع لاتین متعامد وجود ندارد. برای n=3 وجود دارد. مشهورترین قضیه این حوزه میگوید برای هر مرتبهٔ n که توانی از عدد اول نباشد و n \neq 2,6 میتوان دست کم یک جفت متعامد یافت. مسئلهٔ مرتبهٔ 6 (مسئلهٔ ۳۶ افسر اویلر) مدتها حلنشده بود تا اینکه ثابت شد برای n=6 چنین جفتی وجود ندارد.
خیر. مربع لاتین ممکن است کاهشپذیر یا کاهشناپذیر باشد. مربع کاهشپذیر را میتوان به مربعهای کوچکتر افراز کرد. برای مرتبهٔ 4 از 4 نوع کاهشناپذیر وجود دارد. بنابراین همهٔ مربعهای لاتین یک مرتبه همریخت نیستند. به عبارت دیگر، عمل جابهجایی سطرها و ستونها و تغییر نام نمادها نمیتواند هر مربعی را به هر مربع دیگری تبدیل کند.
برای مرتبههای کوچک، همهٔ مربعهای لاتین به یک شکل اصلی قابل تبدیل هستند. برای n=1 بدیهی است. برای n=2 تنها یک الگو وجود دارد (دو آرایش که با جابهجایی سطرها به هم میرسند). برای n=3 نیز هر مربع لاتین ۳ در ۳ با تغییر نام نمادها و سطرها به یک شکل منحصربفرد (مربع چرخهای) تبدیل میشود. از مرتبهٔ 4 به بعد است که تنوع واقعی پدیدار میشود.
جمعبندی
پاورقی
1 مربع لاتین (Latin Square): آرایهٔ n×n که در هر سطر و ستون هر یک از n نماد دقیقاً یک بار تکرار شود.
2 گروه جمعی (Additive Group): مجموعهای همراه با عمل جمع که دارای عنصر خنثی، معکوس و شرکتپذیری است. مثال: اعداد صحیح به پیمانهٔ n.
3 طراحی آزمایشها (Design of Experiments): روش آماری برای برنامهریزی آزمایشها به منظور استخراج اطلاعات معنیدار با حداقل تعداد آزمون.
4 متعامد (Orthogonal): دو مربع لاتین متعامد هستند اگر جفت نمادهای متناظر در آنها همهٔ n² ترکیب ممکن را پوشش دهند.