جایگشت بیاثر: جابهجاییای که نتیجهٔ جدید تولید نمیکند
تعریف پایه: جایگشت بیاثر یا همانی چیست؟
در ریاضیات، به هر نوع چیدمان یا مرتبسازی مجدد اعضای یک مجموعه، «جایگشت» میگوییم. فرض کنید مجموعهی {1,2,3} را داریم. جایگشتهای ممکن عبارتند از: (1,2,3)، (1,3,2)، (2,1,3) و غیره. اما یک جایگشت خاص وجود دارد که ترتیب را دقیقاً به همان حالت اولیه نگه میدارد: (1,2,3). به این حالت «جایگشت بیاثر» یا «جایگشت همانی» میگوییم.
به زبان سادهتر: اگر روی یک مجموعه دستکاری انجام دهیم اما در نهایت چیزی تغییر نکند، آن دستکاری یک جایگشت بیاثر است. برای نمونه، فرض کنید سه کتاب با رنگهای قرمز، آبی و سبز به ترتیب روی قفسه چیده شدهاند. اگر کتاب قرمز را با خودش جابهجا کنیم (یعنی جابهجایی خنثی)، یا دو کتاب را جابهجا کنیم و دوباره برگردانیم، در حالت نهایی همان ترتیب اولیه را داریم. در نظریهی گروهها، این عضو ویژه را با e یا id نمایش میدهند.
برای نشان دادن جایگشت بیاثر روی n عضو، معمولاً از نماد $(1)(2)\cdots(n)$ استفاده میکنیم که یعنی هر عضو به خودش نگاشته میشود. همچنین در نماد دوخطی، جایگشت همانی به صورت زیر نوشته میشود:
در این جا سطر بالا اعضای اولیه و سطر پایین تصویر هر عضو را نشان میدهد. چون تصویر هر عضو برابر خودش است، هیچ جابهجایی مؤثری رخ نمیدهد.
تفاوت جایگشت بیاثر با دیگر جایگشتها در عمل ترکیب
یکی از راههای درک عمیقتر جایگشت بیاثر، مقایسهٔ آن با سایر جایگشتها از نظر «ترکیب» یا «ضرب جایگشتها» است. فرض کنید دو جایگشت داریم. اگر یکی از آنها جایگشت بیاثر باشد، نتیجهٔ ترکیب با هر جایگشت دیگر، همان جایگشت دیگر خواهد بود. این ویژگی در جدول زیر برای مجموعهٔ {1,2,3} نشان داده شده است. اجازه دهید جایگشتها را به صورت چرخهای3 نمایش دهیم.
| جایگشت اول | جایگشت دوم | حاصل ترکیب (اول ∘ دوم) |
|---|---|---|
| همانی (1)(2)(3) | چرخه (1 2 3) | (1 2 3) |
| جابهجایی (1 2) | همانی | (1 2) |
| همانی | همانی | همانی |
همانطور که در جدول میبینید، هر جا که جایگشت همانی ظاهر شود، نتیجهٔ ترکیب همان جایگشت دیگر خواهد بود. این خاصیت «عنصر خنثی» نام دارد و برای گروه متقارن $S_n$ (مجموعهٔ همهٔ جایگشتهای n عضو) برقرار است.
مثال عینی: جایگشت بیاثر در رمزنگاری و بازیهای فکری
فرض کنید میخواهیم یک پیام ساده مثل "سلام" را با استفاده از یک جایگشت روی حروف آن رمزگذاری کنیم. اگر جایگشتی که انتخاب میکنیم، همان جایگشت بیاثر باشد، حرف س به س، ل به ل، ا به ا و م به م نگاشته میشود. در این حالت پیام رمزگذاریشده دقیقاً برابر خود پیام اصلی است. هرچند این حالت در رمزنگاری کاربردی ندارد، اما در برخی الگوریتمها به عنوان حالت پیشفرض یا مقدار اولیهٔ کلید به کار میرود.
مثال دیگر: در بازی «۱۵» یا پازل لغزنده، اگر تکهها را آنقدر جابهجا کنید که در نهایت به ترتیب آغازین برگردید، مجموعهٔ جابهجاییهای انجامشده معادل یک جایگشت بیاثر است. در واقع، هر چند حرکت انجام میدهید، اما حاصل نهایی «هیچ تغییری» است. به این میگویند «کلمهٔ بیاثر» در گروه حاصل از حرکات پازل.
روش گامبهگام تشخیص جایگشت بیاثر
برای تشخیص این که یک جایگشت دادهشده بیاثر است یا نه، میتوان مراحل زیر را انجام داد:
- جایگشت را به صورت تابع بنویسید: برای هر عضو x از مجموعه، مقدار f(x) را مشخص کنید.
- اگر برای همهٔ اعضا داشته باشیم $f(x)=x$، آن گاه جایگشت بیاثر است.
- در نماد چرخهای، اگر همهٔ چرخهها طول 1 داشته باشند (یعنی به صورت (1)(2)...(n) نوشته شوند)، آن گاه جایگشت همانی است.
- در نماد دوخطی، اگر سطر بالا و پایین کاملاً یکسان باشند، آن گاه جایگشت بیاثر است.
برای نمونه، جایگشت زیر را در نظر بگیرید که روی مجموعهٔ {a,b,c} تعریف شده:
واضح است که خروجی برای هر ورودی برابر خودش است. پس این یک جایگشت بیاثر است.
چالشهای مفهومی
پاسخ: بله. از نظر نتیجهی نهایی، جایگشت بیاثر دقیقاً همان حالتی است که هیچ جابهجایی مؤثری رخ ندهد. اما گاهی در مسائل ترکیبیاتی، ممکن است چندین حرکت مختلف انجام دهیم که در نهایت اثر یکدیگر را خنثی کنند و به جایگشت بیاثر برسیم. در آن صورت، اگرچه حرکتهایی انجام شدهاند، اما «نتیجه» بیاثر است.
پاسخ: بدون عضو بیاثر، ساختار گروه ریاضی معنی ندارد. در گروه متقارن $S_n$، جایگشت همانی نقش «عنصر خنثی» را ایفا میکند و امکان تعریف وارون هر جایگشت را فراهم میآورد. همچنین در محاسبات ترکیبیاتی، مبنای شمارش جایگشتها قرار میگیرد.
پاسخ: بله. برای نمونه، جابهجایی (1 2) در $S_3$ را در نظر بگیرید. اگر آن را دو بار پشت سر هم اعمال کنیم، دوباره به حالت اولیه برمیگردیم. اما خودِ (1 2) بیاثر نیست چون یک بار اعمال آن، دو عضو را جابهجا میکند. در این حالت میگوییم «ترتیب» آن جایگشت برابر 2 است، نه اینکه خودش همانی باشد.
جمعبندی
پاورقی
1 نظریهٔ گروهها (Group Theory): شاخهای از جبر انتزاعی که به مطالعهٔ ساختارهای جبری به نام «گروه» میپردازد.2 گروه متقارن (Symmetric Group): گروهی که اعضای آن همهٔ جایگشتهای یک مجموعهٔ متناهی هستند.
3 نمایش چرخهای (Cycle Notation): روشی برای نوشتن جایگشت به صورت یک یا چند چرخه که نشان میدهد هر عضو به کدام عضو دیگر نگاشته میشود.