تعداد ترکیب‌های rتایی از n شیء متمایز: تعداد انتخاب‌های rتایی بدون توجه به ترتیب که با C(n,r) یا (n r) نمایش داده می‌شود

بروزرسانی شده در: 16:48 1404/12/8 مشاهده: 26 دسته بندی: کپسول آموزشی

تعداد ترکیب‌های rتایی از n شیء متمایز

آشنایی با مفهوم انتخاب بدون ترتیب، فرمول محاسبه، ویژگی‌ها و کاربردهای ضریب دوجمله‌ای در مسائل شمارش

خلاصه در این مقاله با مفهوم اصلی ترکیب¹ یا انتخاب‌های rتایی از اشیاء متمایز آشنا می‌شویم. بر خلاف جایگشت² که در آن ترتیب اهمیت دارد، در ترکیب‌ها تنها انتخاب اعضا مهم است. نماد $C(n,r)$ یا $\binom{n}{r}$ را معرفی کرده و با مثال‌های عینی از جمله انتخاب تیم، دسته‌های کارتی و مسائل شمارش، کاربرد آن را بررسی خواهیم کرد. همچنین به ویژگی‌های مهم این اعداد، ارتباط آنها با مثلث خیام-پاسکال و چالش‌های مفهومی رایج می‌پردازیم.

تعریف ترکیب و تفاوت آن با جایگشت

ترکیب‌های rتایی از n شیء متمایز، به هر انتخاب نا مرتب از r شیء از میان این n شیء گفته می‌شود. به بیان دیگر، در یک ترکیب، مجموعه‌های حاصل با هم برابرند اگر اعضایشان یکی باشد، صرف‌نظر از اینکه به چه ترتیبی کنار هم قرار گرفته‌ باشند. برای درک بهتر، فرض کنید می‌خواهیم از بین 3 دوست به نام‌های علی، حسن و محمد، یک تیم 2 نفره برای خرید انتخاب کنیم. حالت‌های ممکن عبارتند از: {علی، حسن}، {علی، محمد} و {حسن، محمد}. دقت کنید که مجموعه {علی، حسن} با {حسن، علی} تفاوتی ندارد، زیرا هر دو به یک انتخاب (همان دو نفر) اشاره می‌کنند. اینجا $C(3,2)=3$ است. اگر ترتیب مهم بود (یعنی جایگشت)، تعداد حالت‌ها $P(3,2)=6$ می‌شد.

فرمول اصلی تعداد ترکیب‌های rتایی از n شیء متمایز از رابطه‌ی زیر به‌دست می‌آید: $C(n,r) = \binom{n}{r} = \frac{n!}{r! \cdot (n-r)!}$ که در آن $n!$ (خوانده می‌شود n فاکتوریل) حاصلضرب اعداد طبیعی از 1 تا n است. این فرمول تضمین می‌کند که ترتیب اضافی ناشی از جایگشت‌های r عنصر ($r!$) از تعداد کل جایگشت‌ها ($P(n,r)=\frac{n!}{(n-r)!}$) حذف شود.

ویژگی‌های کلیدی اعداد ترکیب

اعداد ترکیب دارای ویژگی‌های جالبی هستند که محاسبات را در بسیاری از مسائل ساده‌تر می‌کند. درک این ویژگی‌ها برای حل مسائل پیشرفته‌تر شمارش ضروری است. دو ویژگی بسیار پرکاربرد عبارتند از:

ویژگی مکمل:$\binom{n}{r} = \binom{n}{n-r}$. به این معنا که انتخاب $r$ شیء از $n$ شیء، دقیقاً برابر است با انتخاب آن $n-r$ شیئی که انتخاب نمی‌کنیم. مثلاً انتخاب 2 نفر برای خرید از بین 5 نفر، معادل است با انتخاب 3 نفری که در خانه می‌مانند.
اتحاد پاسکال:$\binom{n}{r} = \binom{n-1}{r-1} + \binom{n-1}{r}$. این اتحاد پایه و اساس مثلث خیام-پاسکال است و در استقراهای ریاضی و اثبات‌های ترکیبیاتی کاربرد فراوان دارد. تفسیر آن این است: برای شمارش ترکیب‌های $r$تایی از $n$ شیء، می‌توانیم یک شیء خاص را در نظر بگیریم. اگر آن شیء در انتخاب ما باشد ($\binom{n-1}{r-1}$) و اگر نباشد ($\binom{n-1}{r}$).

مفهوم	ترتیب اهمیت دارد؟	فرمول	مثال (انتخاب ۲ از {الف، ب، ج})
ترکیب (Combination)	خیر	$\binom{n}{r}$	{الف، ب}، {الف، ج}، {ب، ج} ($\binom{3}{2}=3$)
جایگشت (Permutation)	بلی	$P(n,r) = \frac{n!}{(n-r)!}$	(الف، ب)، (ب، الف)، (الف، ج)، (ج، الف)، (ب، ج)، (ج، ب) ($P(3,2)=6$)

کاربردهای ترکیب در مسائل دنیای واقعی

مفهوم ترکیب صرفاً یک انتزاع ریاضی نیست، بلکه در بسیاری از زمینه‌های روزمره و علمی کاربرد دارد. در ادامه چند مثال عینی و ملموس بررسی می‌شود:

تشکیل کمیته: اگر در یک کلاس 30 نفره بخواهیم یک کمیته 4 نفره تشکیل دهیم، تعداد حالات ممکن برابر است با $\binom{30}{4}$. این عدد نشان می‌دهد که بدون توجه به سمت‌های افراد در کمیته، چند گروه متفاوت می‌توانیم داشته باشیم.
انتخاب تیم ورزشی: یک مربی می‌خواهد از بین 12 بازیکن، 5 نفر را برای بازی انتخاب کند. تعداد تیم‌های ممکن $\binom{12}{5}$ است. (این انتخاب قبل از تعیین پست‌ها و ترکیب اصلی است).
دست در بازی پوکر: در بازی پوکر، هر بازیکن 5 کارت از یک دسته 52 کارتی دریافت می‌کند. تعداد کل دست‌های اولیه (بدون توجه به ترتیب کارت‌ها در دست) برابر $\binom{52}{5}$ است که عددی بسیار بزرگ (بیش از دو میلیون و نیم) می‌باشد.
انتخاب سوالات امتحان: استاد از میان 10 سوال موجود، قصد دارد 7 سوال را برای امتحان انتخاب کند. تعداد راه‌های انتخاب سوالات $\binom{10}{7} = \binom{10}{3}$ است. همانطور که می‌بینید استفاده از ویژگی مکمل محاسبه را ساده‌تر می‌کند.

چالش‌های مفهومی

❓ چالش اول: آیا $\binom{n}{r}$ همواره یک عدد صحیح است؟ چرا؟
بله، این عبارت همیشه یک عدد صحیح مثبت (برای $0 \le r \le n$) است. دلیل آن این است که این عدد در واقع شمارشگر تعداد زیرمجموعه‌های $r$عضوی از یک مجموعه $n$عضوی است و تعداد این زیرمجموعه‌ها نمی‌تواند کسری باشد. هرچند در فرمول $\frac{n!}{r!(n-r)!}$ از تقسیم استفاده شده، اما همواره این تقسیم باقیمانده ندارد و به یک عدد صحیح منجر می‌شود.

❓ چالش دوم: چرا $\binom{n}{0}=1$ است؟ انتخاب $0$ شیء به چه معناست؟
$\binom{n}{0}=1$ به این معناست که دقیقاً یک راه برای انتخاب هیچ‌کدام از اشیاء وجود دارد. این "یک راه" همان انتخاب مجموعه تهی (Ø) است. به طور مشابه، $\binom{n}{n}=1$ است که نشان‌دهنده یک راه برای انتخاب همه اشیاء است. این قراردادها باعث می‌شوند فرمول‌ها و اتحادها مانند اتحاد پاسکال برای همه مقادیر معتبر باقی بمانند.

❓ چالش سوم: در یک مساله، من باید بدانم که آیا با ترکیب روبرو هستم یا جایگشت. چه سوالی از خود بپرسم؟
بهترین سوال این است: "آیا جابه‌جا کردن دو عنصر انتخاب شده، یک حالت جدید ایجاد می‌کند یا خیر؟" اگر پاسخ مثبت است، مساله از نوع جایگشت است. اگر پاسخ منفی است (یعنی جابه‌جایی دو عنصر تغییری در حالت ایجاد نمی‌کند)، مساله از نوع ترکیب است. مثلاً در انتخاب نمایندگان کلاس، اگر هر فرد یک نقش مشخص (رئیس، منشی) داشته باشد، جایگشت است؛ اگر همه نقش‌ها یکسان باشند، ترکیب است.

نکته پایانی مفهوم ترکیب، سنگ بنای آنالیز ترکیبی و نظریه احتمالات است. با درک تفاوت آن با جایگشت و تسلط بر فرمول و ویژگی‌های آن، می‌توانید طیف وسیعی از مسائل شمارش را که در آنها ترتیب بی‌اهمیت است، به سادگی مدل‌سازی و حل کنید. این دانش پایه‌ای برای مطالعه مباحث پیشرفته‌تری مانند قضیه دو جمله‌ای $(a+b)^n = \sum_{r=0}^{n} \binom{n}{r} a^{n-r} b^{r}$ خواهد بود.

پاورقی

¹ ترکیب (Combination): به انتخاب مجموعه‌ای از اشیاء از یک مجموعه بزرگتر گفته می‌شود، به طوری که ترتیب قرار گرفتن اشیاء در انتخاب اهمیت نداشته باشد.
² جایگشت (Permutation): به چیدمان اشیاء در یک ترتیب خاص گفته می‌شود و در آن ترتیب قرار گرفتن عناصر مهم است.