تکنیک «یکپنداری» در جایگشت: شمارش حالات چیدمان با اعضای اجباری در کنار هم
مفهوم «یکپنداری» و چرایی استفاده از آن
در علم شمارش، به ویژه مبحث جایگشتpermutation، گاهی مسئله شرایط خاصی را برای چیدمان اشیا تعیین میکند. یکی از رایجترین این شرایط آن است که گروهی از اشیا (مثلاً چند حرف از یک کلمه یا چند نفر از یک گروه) باید همیشه در کنار یکدیگر قرار بگیرند. به عبارت دیگر، مجاورت آنها الزامی است و هیچ شیء دیگری نمیتواند بین آنها فاصله بیندازد .
برای مثال، فرض کنید میخواهیم حروف کلمه «آموزش» را طوری مرتب کنیم که سه حرف «آ»، «م» و «و» همیشه پشت سر هم و به ترتیب خاص خود (آمو) بیایند. در نگاه اول شاید تصور کنیم باید تکتک جایگشتها را بنویسیم و بشماریم، اما برای حالات بزرگتر این کار غیرممکن است. در اینجا تکنیک «یکپنداری» یا «طنابپیچ کردن»binding technique به کمک ما میآید. در این روش، اعضایی که باید مجاور باشند را با یک طناب فرضی به هم میبندیم و آنها را به عنوان یک «بلوک» یا یک «شیء واحد» در نظر میگیریم . با این کار، مسئله از حالت پیچیده به حالت سادهتری تبدیل میشود.
$ (n - k + 1)! \times k! $
در این فرمول، $(n - k + 1)!$ تعداد حالات چیدمان بلوک واحد (به همراه سایر اشیا) و $k!$ تعداد حالات جابجایی اعضا درون بلوک است.
حالت اول: کنار هم بودن با ترتیب خاص
گاهی اوقات نه تنها باید چند حرف خاص کنار هم باشند، بلکه ترتیب قرار گرفتن آنها در کنار هم نیز از پیش تعیین شده است. مثلاً در کلمه «کتابخانه»، بخواهیم حروف «ک»، «ت»، «ا»، «ب» دقیقاً به همان ترتیب «کتاب» کنار هم قرار گیرند. در این حالت، دیگر نیازی به محاسبه جایگشت داخلی نیست، زیرا اعضای بلوک فقط یک شکل مشخص میتوانند در کنار هم بایستند.
مثال: به چند طریق میتوان حروف کلمه COMPUTER را مرتب کرد که حروف COM دقیقاً به همین ترتیب کنار هم باشند ؟
گام ۱: حروف C، O و M را به دلیل داشتن ترتیب خاص، به عنوان یک بلوک واحد در نظر میگیریم.
گام ۲: حالا به جای ۸ حرف جداگانه، ۶ شیء داریم: {COM}، P، U، T، E، R. تعداد حالات چیدمان این ۶ شیء متمایز برابر است با $6!$.
گام ۳: چون ترتیب داخل بلوک (C, O, M) از قبل مشخص است، آن را در یک حالت حساب میکنیم و نیازی به ضرب نیست.
پاسخ: بنابراین تعداد کل حالات برابر $6! = 720$ است.
حالت دوم: کنار هم بودن بدون ترتیب خاص
در این حالت، اعضای بلوک میتوانند هر ترتیبی را درون خود داشته باشند. رایجترین مثال برای این حالت، چیدن افراد یک خانواده در کنار هم است.
مثال: اعضای یک خانواده شامل ۵ پسر و ۴ دختر میخواهند برای یک عکس دستهجمعی در یک صف بایستند. به چند طریق میتوان آنرا چیدمان کرد که همه پسرها در کنار یکدیگر باشند (یعنی هیچ دختری بین پسرها نباشد) ؟
گام ۱: پسرها را به عنوان یک گروه (بلوک) در نظر میگیریم.
گام ۲: حالا ۴ دختر + ۱ بلوک پسرها = ۵ شیء داریم. تعداد حالات چیدمان این ۵ شیء در یک ردیف برابر $5!$ است.
گام ۳: درون بلوک پسرها، ۵ پسر متمایز را میتوان به $5!$ حالت مختلف جابجا کرد.
گام ۴: با استفاده از اصل ضرب، تعداد کل حالات برابر است با: $ 5! \times 5! = 120 \times 120 = 14400 $.
| نوع شرط | روش حل | فرمول کلی | مثال عددی |
|---|---|---|---|
| ترتیب داخلی مشخص | بلوک کردن و جایگشت بلوکها | $(n-k+1)!$ | $6!$ برای COM در COMPUTER |
| ترتیب داخلی دلخواه | بلوک کردن × جایگشت داخلی اعضا | $(n-k+1)! \times k!$ | $5! \times 5!$ برای ۵ پسر کنار هم |
کاربرد عملی: چیدن کتابها با موضوع مشترک
مسئله: یک دانشآموز ۷ کتاب مختلف دارد که ۳ تای آنها ریاضی و ۴ تای آنها فیزیک هستند. او میخواهد این کتابها را در قفسهای بچیند. به چند طریق میتواند این کار را انجام دهد اگر کتابهای ریاضی باید کنار یکدیگر قرار بگیرند؟
تحلیل: این مسئله دقیقاً مشابه مثال خانواده ۵ پسر و ۴ دختر است. کتابهای ریاضی نقش «پسرها» و کتابهای فیزیک نقش «دخترها» را دارند .
گام ۱: ۳ کتاب ریاضی را به عنوان یک بلوک در نظر میگیریم.
گام ۲: تعداد کل اشیاء برای چیدمان: ۱ بلوک ریاضی + ۴ کتاب فیزیک = ۵ شیء. تعداد جایگشتهای این ۵ شیء: $5! = 120$.
گام ۳: تعداد حالات جابجایی ۳ کتاب ریاضی درون بلوک: $3! = 6$.
پاسخ نهایی:$120 \times 6 = 720$ حالت مختلف برای چیدن کتابها با شرط داده شده.
این روش نه تنها در چیدن کتاب، بلکه در مسائل مربوط به کدنویسی، صفبندی افراد، جایگشت حروف یک کلمه و هر جای دیگری که با اشیاء فیزیکی سروکار داریم، کاربرد گستردهای دارد .
چالشهای مفهومی
❓ سوال ۱: اگر بخواهیم سه حرف خاص در یک کلمه ۶ حرفی کنار هم باشند، چرا تعداد حالات را $ (6-3+1)! \times 3! $ مینویسیم؟
پاسخ: چون با یکپنداری، ۳ حرف به یک بلوک تبدیل میشوند و به همراه ۳ حرف دیگر (مجموعاً ۴ واحد) جایگشت مییابند ($4!$). سپس باید ضرب در جایگشت داخلی ۳ حرف ($3!$) شود.
❓ سوال ۲: تفاوت بین «کنار هم بودن با ترتیب مشخص» و «کنار هم بودن بدون ترتیب مشخص» در فرمول نویسی چیست؟
پاسخ: در حالت «با ترتیب مشخص»، جایگشت داخلی بلوک یک است (یعنی در فرمول ضرب نمیشود)، اما در حالت «بدون ترتیب مشخص»، باید حتماً جایگشت داخلی اعضا (فاکتوریل تعداد اعضای بلوک) را در نتیجه نهایی ضرب کنیم.
❓ سوال ۳: اگر اعضای درون بلوک یکسان باشند (مثلاً حروف تکراری)، روش کار چه تغییری میکند؟
پاسخ: اگر اعضای داخل بلوک تکراری باشند، جایگشت داخلی آنها طبق فرمول جایگشت با تکرار محاسبه میشود . برای مثال، اگر بخواهیم دو حرف «A» و «B» کنار هم باشند، جایگشت داخلی $2!$ است، اما اگر بخواهیم دو حرف «A» و «A» کنار هم باشند، جایگشت داخلی $ \frac{2!}{2!}=1 $ خواهد بود.
پاورقی
1جایگشت (Permutation): به معنای شمارش تعداد حالتهای ممکن برای چیدن اشیا در کنار یکدیگر است، به شرطی که ترتیب قرار گرفتن آنها اهمیت داشته باشد .
2فاکتوریل (Factorial): حاصلضرب اعداد طبیعی از ۱ تا n را گویند و با نماد $n!$ نمایش میدهند. برای مثال $5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$.
3اصل ضرب (Multiplication Principle): اگر عملی به دو مرحله متوالی انجام شود، به طوری که مرحله اول به aراه و مرحله دوم به bراه قابل انجام باشد، کل عملیات به $a \times b$ روش قابل انجام است .
