جایگشت روی اعضای مربع لاتین: جایگزینی نمادها با یک جایگشت
مربع لاتین چیست و چرا جایگشت مهم است؟
مربع لاتین جدولی n×n است که در هر سطر و هر ستون آن، هر یک از n نماد (مثلاً اعداد 1 تا n) دقیقاً یک بار ظاهر شود. فرض کنید یک مربع لاتین از نمادهای \{A,B,C\} داریم. اگر همهٔ Aها را به B، Bها را به C و Cها را به A تبدیل کنیم، در واقع یک جایگشت1 روی نمادها اعمال کردهایم. خاصیت جالب این است که جدول حاصل دوباره یک مربع لاتین خواهد بود. به همین سادگی!
اثر جایگشت بر ساختار مربع لاتین (حالت کلی)
فرض کنیم L یک مربع لاتین از مرتبه n با مجموعه نمادهای S = \{s_1, s_2, ..., s_n\} باشد. یک جایگشت \sigma روی مجموعه S، تابعی یکبهیک و پوشا است که هر نماد را به نماد دیگری نسبت میدهد. اگر این جایگشت را روی همهٔ درایههای L اعمال کنیم، مربع جدیدی به نام \sigma(L) به دست میآید.
قضیه: برای هر مربع لاتین L و هر جایگشت \sigma روی نمادها، \sigma(L) نیز یک مربع لاتین است.
دلیل: در هر سطر از L، نمادها همه متفاوت هستند. چون \sigma یک تابع یکبهیک است، تصاویر این نمادهای متفاوت نیز با یکدیگر متفاوت خواهند بود. به همین ترتیب برای هر ستون. پس شرط تکرار نشدن نمادها در سطرها و ستونهای \sigma(L) برقرار است.
| مربع لاتین مرتبه 3 (اصلی) | جایگشت \sigma(1\to2,\;2\to3,\;3\to1) | مربع لاتین新 (پس از جایگشت) |
|---|---|---|
| 1 2 3 2 3 1 3 1 2 | 1→2, 2→3, 3→1 | 2 3 1 3 1 2 1 2 3 |
همانطور که در جدول میبینید، سطر اول اصلی (1,2,3) پس از جایگشت به (2,3,1) تبدیل شده که باز هم همه اعضایش متفاوت هستند. سطر دوم و سوم و همچنین ستونها نیز این ویژگی را دارند.
چرا جایگشت در طراحی آزمایشها و رمزنگاری مفید است؟
در طراحی آزمایشها، گاهی پژوهشگر نمیخواهد مستقیماً از نام اصلی تیمارها استفاده کند (مثلاً برای جلوگیری از سوگیری). اعمال یک جایگشت تصادفی روی مربع لاتین، یک طرح معادل ولی با برچسبهای جدید ایجاد میکند که از نظر آماری همان اطلاعات را ارائه میدهد. همچنین در رمزنگاری ساده، گاهی مربع لاتین نقش یک جانشینساز (substitution) را بازی میکند و جایگشت روی نمادها به منزلهٔ کلید رمز است.
به عنوان نمونه، فرض کنید پیام خود را در یک مربع لاتین 4×4 قرار میدهید و سپس یک جایگشت سری روی نمادها اعمال میکنید. گیرنده با دانستن جایگشت معکوس، میتواند مربع اصلی را بازگرداند. این ایده ساده، پایهٔ برخی روشهای اولیهٔ رمزگذاری است.
چالشهای مفهومی برای درک عمیقتر
پاسخ: خیر. جایگشت فقط روی نمادها (مقادیر درون خانهها) اثر میگذارد، نه روی جایگاه سطرها و ستونها. سطر اول همچنان سطر اول میماند، ولی مقادیر داخل آن عوض میشوند.
پاسخ: بله. اگر جایگشت \sigma را اعمال کرده باشیم، با اعمال جایگشت معکوس \sigma^{-1} دوباره مربع اصلی را به دست میآوریم. چون جایگشتها یک گروه تشکیل میدهند.
پاسخ: دقیقاً. اگر ابتدا \sigma_1 و سپس \sigma_2 را اعمال کنیم، حاصل برابر با اعمال جایگشت \sigma_2 \circ \sigma_1 است. این خاصیت ترکیبپذیری (composition) جایگشتها نام دارد.
در این مقاله با مفهوم مربع لاتین و تأثیر جایگشت روی نمادهای آن آشنا شدیم. دیدیم که اعمال هر جایگشتی روی درایههای مربع لاتین، ساختار لاتین بودن را حفظ میکند، زیرا یکبهیک بودن تابع جایگشت باعث میشود تکرار نکردن نمادها در سطرها و ستونها همچنان برقرار بماند. این ویژگی ساده اما پایهای، کاربردهایی در طراحی آزمایشها، رمزنگاری و ساخت مربعهای لاتین متعامد دارد. همچنین ترکیب جایگشتها با یکدیگر نیز خود یک جایگشت است، که یادآور ساختار گروهی جایگشتها میباشد.
پاورقی
1 جایگشت (Permutation): در ریاضیات، به هر تغییر ترتیب یا تعویض یکبهیک اعضای یک مجموعه متناهی، جایگشت گفته میشود. مثلاً برای مجموعه \{1,2,3\} شش جایگشت مختلف وجود دارد.