جایگشت با چسباندن: شگردی برای شمارش چیدمان اجزای کنار هم
مفهوم «یک واحد در نظر گرفتن» در جایگشت
فرض کنید میخواهیم بدانیم که اگر چند کتاب مشخص را در یک قفسه کنار هم بچینیم، به چند حالت مختلف میتوان این کار را انجام داد، به شرطی که برخی کتابها که یک مجموعه هستند (مثلاً کتابهای یک نویسنده) حتماً کنار هم قرار بگیرند. در اینجا به جای آنکه تکتک کتابها را جابجا کنیم، کل آن مجموعه را به عنوان یک «بسته» یا «یک واحد» در نظر میگیریم. این کار محاسبه را بسیار سادهتر میکند.
به این روش در ترکیبیات، «روش چسباندن»[۲] میگویند. ایده اصلی این است: اعضایی که باید کنار هم باشند را به هم میچسبانیم و آنها را یک شیء واحد فرض میکنیم. سپس تعداد جایگشتهای این اشیاء جدید (که شامل بستهها و تکعنصرهاست) را حساب کرده و در تعداد حالات چیدمان داخلی خود اعضای بسته ضرب میکنیم.
($(n-k+1)!$ مربوط به جایگشت بسته و بقیه عناصر، و $k!$ مربوط به جایگشت داخلی اعضای گروه است.)
کاربرد عملی: از حروف الفبا تا چیدمان اشیاء
برای درک بهتر این موضوع، بیایید چند مثال عینی و گامبهگام را با هم بررسی کنیم. این مثالها از ساده به دشوار مرتب شدهاند تا با منطق حاکم بر این شگرد آشنا شوید.
مثال اول: چیدمان کتابها
۵ کتاب مختلف داریم: ریاضی، فیزیک، شیمی، زیست و ادبیات. میخواهیم آنها را در یک قفسه بچینیم، به شرط آنکه کتابهای ریاضی و فیزیک حتماً کنار هم باشند. چند حالت ممکن است؟
- گام اول (چسباندن): کتاب ریاضی و فیزیک را به عنوان یک بسته در نظر میگیریم. حال به جای ۵ کتاب، یک بسته + سه کتاب دیگر (شیمی، زیست، ادبیات) داریم. تعداد کل واحدها: ۴ واحد ($1 \text{ بسته} + 3 \text{ کتاب} = 4$).
- گام دوم (جایگشت واحدها): این ۴ واحد را به $4!$ طریق میتوان کنار هم چید.
- گام سوم (جایگشت داخلی): داخل بسته، دو کتاب ریاضی و فیزیک را میتوان به $2!$ طریق جابجا کرد (ریاضی-فیزیک یا فیزیک-ریاضی).
- گام چهارم (ضرب حالات): طبق اصل ضرب، تعداد کل حالات برابر است با: $4! \times 2! = 24 \times 2 = 48$.
مثال دوم: جایگشت حروف با شرط
با حروف کلمه گلستان (۶ حرف) چند کلمهی ۶ حرفی (با معنی یا بیمعنی) میتوان نوشت که حروف «گ» و «ل» همیشه کنار هم باشند؟
- گام اول: حروف «گ» و «ل» را میچسبانیم و یک «ابرحرف» میسازیم.
- گام دوم: حالا داریم: ابرحرف (گ-ل) + س + ت + ا + ن = ۵ واحد.
- گام سوم: تعداد جایگشت این ۵ واحد: $5! = 120$.
- گام چهارم: جایگشت داخلی دو حرف «گ» و «ل»: $2! = 2$.
- گام پنجم: تعداد کل: $120 \times 2 = 240$.
اگر شرط «کنار هم بودن» شامل ترتیب مشخص هم باشد (مثلاً «گ» همیشه سمت چپ «ل» باشد)، دیگر نیازی به ضرب در $2!$ نداریم (چرا؟) چون حالت داخلی فقط یکی است. جواب مثال در این حالت $120$ میشود.
گسترش مفهوم: بیش از یک گروه و حالتهای خاص
روش چسباندن فقط به یک گروه ختم نمیشود. ممکن است در یک مسئله چند گروه داشته باشیم که هر کدام باید کنار هم باشند. در این موارد، هر گروه را جداگانه میچسبانیم و سپس به عنوان واحدهای مستقل با هم ترکیب میکنیم.
مثال سوم: دو گروه مجزا
در یک قفسه، ۴ کتاب ریاضی (مختلف) و ۳ کتاب فیزیک (مختلف) داریم. به چند طریق میتوان آنها را چید به طوری که همه کتابهای ریاضی کنار هم و همه کتابهای فیزیک کنار هم باشند؟
- چسباندن: کتابهای ریاضی را به عنوان یک بسته (R) و کتابهای فیزیک را به عنوان بسته دیگر (F) در نظر میگیریم.
- واحدها: دو بسته داریم: R و F (۲ واحد).
- جایگشت واحدها: این دو بسته به $2!$ طریق میتوانند کنار هم قرار گیرند (R,F یا F,R).
- جایگشت داخلی گروهها: داخل بسته ریاضی: $4!$ حالت، داخل بسته فیزیک: $3!$ حالت.
- جواب نهایی: $2! \times 4! \times 3! = 2 \times 24 \times 6 = 288$.
| نوع مسئله | تعداد اشیاء (n) | تعداد اشیاء گروهخورده (k) | روش حل | تعداد حالات نهایی |
|---|---|---|---|---|
| یک گروه کنار هم (بدون ترتیب خاص) | 5 | 2 | چسباندن گروه و محاسبه $(n-k+1)! \times k!$ | 48 |
| یک گروه با ترتیب مشخص داخلی | 6 | 2 | چسباندن گروه، فقط یک حالت برای داخل گروه | 120 |
| دو گروه مجزا (هر گروه کنار هم) | 7 | 4 و 3 | تشکیل دو بسته، جایگشت بستهها و ضرب جایگشت داخلی هر بسته | 288 |
چالشهای مفهومی
❓ چالش ۱: تفاوت «کنار هم بودن» با «در کنار هم قرار گرفتن» چیست؟
در جایگشت، وقتی میگوییم اشیاء «کنار هم» هستند، یعنی یک بلوک پیوسته را تشکیل میدهند و هیچ شیء دیگری بین آنها فاصله نمیاندازد. اما «در کنار هم قرار گرفتن» ممکن است به معنای نزدیک بودن یا در یک بازه بودن باشد، که مفهوم دقیقتری در ترکیبیات دارد. روش چسباندن دقیقاً برای حالت اول (بلوک پیوسته) کاربرد دارد.
❓ چالش ۲: اگر اعضای گروه تکراری باشند، آیا روش چسباندن تغییر میکند؟
بله. اگر داخل گروهی که میچسبانیم، اشیاء یکسان وجود داشته باشند، در مرحله محاسبه جایگشت داخلی گروه ( $k!$ ) باید جایگشت با تکرار را حساب کنیم. مثلاً اگر دو حرف «الف» تکراری در یک گروه ۳ تایی داشته باشیم، جایگشت داخلی گروه برابر $\frac{3!}{2!}=3$ میشود، نه $3!$ .
❓ چالش ۳: آیا ممکن است دو گروه چسبیده به هم نیز برخورد داشته باشند؟
بله، گاهی اوقات شرط مسئله به گونهای است که دو گروه چسبیده باید حتماً از یکدیگر جدا باشند یا حتماً در کنار هم قرار بگیرند. در این موارد، ابتدا گروهها را چسبانده، سپس آن بستهها را با شرایط جدید (مثلاً خود بستهها همیشه کنار هم باشند) دوباره چسباند. این کار به صورت سلسلهمراتبی انجام میشود. مثلاً اگر گروه A و B هر کدام به تنهایی باید کنار هم باشند و بعد این دو گروه نیز باید کنار هم قرار گیرند، یک ابربسته بزرگتر میسازیم.
روش «چسباندن» یکی از ابزارهای پایهای و در عین حال قدرتمند در حل مسائل جایگشت است. با تبدیل اعضای گروهخورده به یک واحد، مسئله پیچیده به یک جایگشت ساده تبدیل شده و با ضرب حالات داخلی، پاسخ نهایی به دست میآید. این شگرد نه تنها در ریاضیات دبیرستانی، بلکه در ترکیبیات، رمزنگاری و حتی برنامهنویسی برای تولید حالات خاص کاربرد فراوان دارد. به خاطر داشته باشید که کلید موفقیت در این روش، تشخیص درست «گروهی که باید چسبانده شود» و توجه به «تکرار احتمالی» اعضای داخل گروه است.
پاورقی
[1] جایگشت خطی (Permutation): به ترتیب قرار گرفتن اشیاء در یک خط (ردیف) گفته میشود که در آن جایگاهها متمایز هستند .
[2] روش چسباندن (Glue Method / Block Method): تکنیکی در ترکیبیات که در آن چند شیء که باید کنار هم قرار گیرند، به عنوان یک بلوک در نظر گرفته میشوند تا تعداد حالات محاسبه گردد.
