ترکیب: انتخاب r شیء از n شیء متمایز بدون توجه به ترتیب
۱. مفهوم پایهای ترکیب: انتخاب بدون اولویت
تصور کنید در یک کلاس با ۵ دانشآموز به نامهای علی، سارا، رضا، مریم و امین قرار است یک گروه ۲ نفره برای انجام یک پروژه تشکیل دهیم. مهم نیست که اول علی انتخاب شود و بعد سارا، یا اول سارا و بعد علی. در هر دو حالت، گروه نهایی {علی، سارا} است. اینجا بحث «ترتیب» مطرح نیست و صرفاً اعضای گروه اهمیت دارند. به این نوع انتخاب، ترکیب میگویند. در حالت کلی، ترکیب r عنصر از یک مجموعه n عضوی، یک انتخاب بدوناولویت است و تعداد این انتخابها را با نماد $C(n, r)$، $\binom{n}{r}$ یا «تعداد ترکیبهای r از n» نمایش میدهند.
۲. تفاوت کلیدی: ترکیب در برابر جایگشت
بزرگترین چالش دانشآموزان در مسائل ترکیبیات، تشخیص موقعیت استفاده از ترکیب یا جایگشت1 است. در جایگشت، ترتیب چیدمان اهمیت دارد اما در ترکیب، اهمیت ندارد. به مثال زیر توجه کنید:
فرض کنید از میان ۴ کتاب مختلف (کتاب ریاضی، فیزیک، شیمی، زیست) میخواهیم ۲ کتاب را انتخاب کنیم.
- حالت جایگشت: اگر بخواهیم آنها را در یک قفسه بچینیم و بگوییم کدام کتاب سمت چپ و کدام کتاب سمت راست باشد، ترتیب مهم است. تعداد حالتها برابر P(4,2) = 12 است.
- حالت ترکیب: اگر فقط بخواهیم بدانیم کدام دو کتاب را برای مطالعه در سفر برداریم (و ترتیب اهمیتی ندارد)، تعداد حالتها برابر C(4,2) = 6 است.
در واقع، رابطهی بین این دو مفهوم این است که هر جایگشت از r عنصر، خودش یک ترکیب خاص است که عناصر آن به تعداد r! حالت مختلف مرتب شدهاند. بنابراین:
۳. ویژگیهای مهم و روابط ترکیبی
اعداد ترکیبی (ضریب دوجملهای) دارای ویژگیهای جذابی هستند که حل مسائل را سادهتر میکنند. دو ویژگی بسیار کاربردی عبارتند از:
- خاصیت مکمل بودن:$\binom{n}{r} = \binom{n}{n-r}$. انتخاب r عضو از n دقیقاً معادل با کنار گذاشتن n-r عضو است.
- فرمول بازگشتی (مثلث خیام-پاسکال3):$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$. این فرمول به ما میگوید که برای انتخاب r عنصر از n، یا عنصر خاصی را انتخاب میکنیم (و باید r-1 عنصر دیگر از n-1 باقیمانده برگزینیم) یا آن عنصر را انتخاب نمیکنیم (و باید همه r عنصر را از n-1 باقیمانده انتخاب کنیم).
۴. جدول مقایسه موارد کاربرد ترکیب و جایگشت
| موقعیت / سوال | ترتیب اهمیت دارد؟ | روش شمارش | مثال |
|---|---|---|---|
| تشکیل کمیته از بین اعضا | خیر | ترکیب $C(n, r)$ | انتخاب ۳ نماینده از ۱۰ نفر |
| تعیین ساماندهی کتابها در قفسه | بله | جایگشت $P(n, r)$ | چیدن ۴ کتاب از ۷ کتاب در قفسه |
| انتخاب طعمهای پیتزا برای سفارش | خیر | ترکیب | انتخاب ۲ طعم از ۵ طعم |
| ایجاد کلمهی عبور با حروف مشخص | بله | جایگشت | تعداد رمزهای ۳ رقمی با ارقام غیرتکراری |
۵. مثال عینی و کاربردی: انتخاب تیم پروژه
فرض کنید در یک شرکت ۱۲ برنامهنویس با تخصصهای مختلف وجود دارد. مدیر پروژه میخواهد یک تیم ۴ نفره برای توسعهی یک اپلیکیشن جدید تشکیل دهد. از آنجا که همهی اعضای تیم وظایف مشابهی دارند و فقط حضورشان مهم است، مسئله از نوع ترکیب است. تعداد تیمهای ممکن برابر است با:
حال اگر مدیر بخواهد از بین این ۱۲ نفر، یک نفر را به عنوان رهبر تیم، یک نفر را به عنوان مسئول پایگاه داده و دو نفر را به عنوان برنامهنویس عادی انتخاب کند (و عناوین مشخص باشند)، آنگاه ترتیب و نوع پست مهم میشود و باید از جایگشت یا ضرب اعداد ترکیبی استفاده کرد: ابتدا انتخاب تیم ۴ نفره و سپس تخصیص نقشها.
۶. چالشهای مفهومی
پاسخ: بله، دقیقاً به همین دلیل است! تنها یک راه برای انتخاب «هیچکدام» از اعضای یک مجموعه وجود دارد و آن هم انتخاب نکردن همهی آنهاست. این موضوع در فرمول نیز صدق میکند: $\frac{n!}{0! \cdot n!} = 1$.
پاسخ: اگر پست بازیکنان تفاوتی نداشته باشد و صرفاً لیست نفرات مد نظر باشد، ترکیب است (C(18,11)). اما اگر پستها (دروازهبان، مدافع، ...) اهمیت داشته باشند و بخواهیم مشخص کنیم هر کدام در کدام پست بازی کنند، آنگاه به مسئلهای پیچیدهتر و شبیه جایگشت تبدیل میشود (که معمولاً با احتساب حالتهای مختلف پستها حل میشود).
پاسخ: فرض کنید میخواهیم از ۵ نفر (علی، سارا، رضا، مریم، امین) یک گروه ۲ نفره انتخاب کنیم. تعداد کل گروهها C(5,2)=10 است. حال به علی فکر کنید: یا علی در گروه است یا نیست. اگر علی در گروه باشد، باید ۱ نفر دیگر از ۴ نفر باقیمانده انتخاب کنیم (C(4,1)=4). اگر علی در گروه نباشد، باید هر ۲ نفر را از ۴ نفر دیگر انتخاب کنیم (C(4,2)=6). مجموع این دو حالت (۴+۶=۱۰) همان تعداد کل گروههاست.
پاورقیها
- 1جایگشت (Permutation): به معنی تعداد روشهای چیدن r عنصر از n عنصر در حالتی که ترتیب قرارگیری آنها مهم باشد. فرمول: P(n, r) = n! / (n-r)!.
- 2رابطهی بازگشتی (Recurrence Relation): در این رابطه، یک عبارت بر حسب مقادیر قبلی خودش تعریف میشود. فرمول C(n, r) = C(n-1, r-1) + C(n-1, r) یک رابطهی بازگشتی کلاسیک است.
- 3مثلث خیام-پاسکال (Pascal's Triangle): آرایهای مثلثی شکل از ضرایب بسط دوجملهای است. هر خانه در این مثلث حاصل جمع دو خانهی بالای خودش است و مقادیر آن برابر با C(n, r) میباشد. این مثلث اولینها توسط ریاضیدان ایرانی، عمر خیام، مطالعه شد.
