نماد C(n,r) : نمادی برای تعداد ترکیبهای rتایی از n شیء متمایز
ترکیب چیست؟ تفاوت با جایگشت
در زندگی روزمره بارها با موقعیتهایی مواجه میشویم که میخواهیم تعدادی شیء را از بین چندین شیء انتخاب کنیم، بدون اینکه ترتیب انتخاب برایمان مهم باشد. برای مثال، انتخاب 3 نفر از میان 10 نفر برای تشکیل یک تیم. در این حالت، تیمی که از افراد A, B, C تشکیل شده است، با تیم C, B, A تفاوتی ندارد. این مفهوم در ریاضیات «ترکیب» نامیده میشود. نماد C(n,r) یا \binom{n}{r} دقیقاً برای نشان دادن تعداد این حالتها به کار میرود.
در مقابل، اگر ترتیب انتخاب اهمیت داشته باشد، با مفهوم «جایگشت» سر و کار داریم. برای نمونه، انتخاب سه نفر از ده نفر برای تصدی پستهای رئیس، نایبرئیس و منشی، یک جایگشت است، زیرا تخصیص A به عنوان رئیس و B به عنوان نایبرئیس، حالتی متفاوت از رئیس بودن B و نایبرئیس بودن A ایجاد میکند. تفاوت اساسی ترکیب و جایگشت در همین «ترتیب» خلاصه میشود. به بیان دیگر، در ترکیبها، یک مجموعه صرفاً بر اساس اعضایش شناسایی میشود، نه چینش آنها.
برای روشن شدن موضوع، به مثال زیر توجه کنید: فرض کنید سه حرف A, B, C داریم. میخواهیم 2 حرف از آنها را انتخاب کنیم.
- ترکیبها (بدون توجه به ترتیب):{A,B}, {A,C}, {B,C}. تعداد آنها C(3,2)=3 است.
- جایگشتها (با توجه به ترتیب):(A,B), (B,A), (A,C), (C,A), (B,C), (C,B). تعداد آنها P(3,2)=6 است.
فرمول محاسبهی C(n,r) و نماد فاکتوریل
برای محاسبه تعداد ترکیبها، از نماد فاکتوریل استفاده میکنیم. فاکتوریل یک عدد طبیعی مانند n که با n! نشان داده میشود، حاصلضرب تمام اعداد طبیعی از 1 تا n است. به طور قراردادی 0! = 1 تعریف میشود. فرمول اصلی محاسبه ترکیب به صورت زیر است:
$C(n, r) = \binom{n}{r} = \frac{n!}{r! \times (n-r)!}$در این فرمول:
- n: تعداد کل اشیاء متمایز.
- r: تعداد اشیایی که میخواهیم انتخاب کنیم (0 \le r \le n).
- n!: فاکتوریل n.
مثال: میخواهیم بدانیم از بین 5 کتاب مختلف، چند راه برای انتخاب 2 کتاب وجود دارد؟ با استفاده از فرمول داریم:
$C(5, 2) = \frac{5!}{2! \times (5-2)!} = \frac{5 \times 4 \times 3 \times 2 \times 1}{(2 \times 1) \times (3 \times 2 \times 1)} = \frac{120}{2 \times 6} = \frac{120}{12} = 10$بنابراین 10 راه متفاوت برای انتخاب 2 کتاب از 5 کتاب وجود دارد.
| n (تعداد کل) | r (تعداد انتخاب) | محاسبه | C(n, r) |
|---|---|---|---|
| 4 | 2 | $\frac{4!}{2!2!}$ | 6 |
| 6 | 3 | $\frac{6!}{3!3!}$ | 20 |
| 8 | 1 | $\frac{8!}{1!7!}$ | 8 |
| 10 | 4 | $\frac{10!}{4!6!}$ | 210 |
ویژگیهای کلیدی و اتحادهای مهم ترکیب
نماد C(n,r) دارای ویژگیهای جالبی است که محاسبات را در بسیاری از مسائل سادهتر میکند.
- خاصیت مکملی (تقارن):$C(n, r) = C(n, n-r)$. این ویژگی بیان میکند که انتخاب r شیء از n شیء، با انتخاب n-r شیء (یعنی کنار گذاشتن آنها) برابر است. برای مثال، $C(7, 2) = C(7, 5)$ زیرا هر دو برابر 21 هستند.
- اتحاد پاسکال:$C(n, r) = C(n-1, r-1) + C(n-1, r)$. این اتحاد پایه و اساس ساخت مثلث خیام-پاسکال است. برای درک آن، فرض کنید یکی از n شیء را مشخص میکنیم. تعداد کل ترکیبها برابر است با مجموع ترکیبهایی که آن شیء خاص را شامل میشوند ($C(n-1, r-1)$) و ترکیبهایی که شامل آن نمیشوند ($C(n-1, r)$).
- مقادیر ویژه:
- $C(n, 0) = C(n, n) = 1$ (یک راه برای انتخاب هیچکدام یا انتخاب همه).
- $C(n, 1) = n$ (انتخاب یک شیء از n شیء، n راه دارد).
- $C(n, 2) = \frac{n(n-1)}{2}$ (تعداد دستدادنهای بین n نفر).
کاربردهای عملی C(n,r) در مسائل روزمره و علمی
نماد ترکیب کاربردهای گستردهای در علوم کامپیوتر، آمار، زیستشناسی و حتی تصمیمگیریهای روزمره دارد. در ادامه به چند مثال عینی اشاره میکنیم:
- تشکیل کمیته و تیمها: اگر بخواهیم از میان 12 نفر، یک کمیته 5 نفره تشکیل دهیم، تعداد حالات ممکن برابر است با $C(12, 5) = 792$ حالت.
- احتمال در بازیها: در یک کیسه 10 توپ رنگی داریم که 4 تای آنها قرمز هستند. اگر 3 توپ به طور تصادفی برداریم، تعداد حالتهایی که هر 3 توپ قرمز باشند، $C(4, 3) = 4$ است. تعداد کل حالتهای ممکن برای انتخاب 3 توپ از 10 توپ، $C(10, 3) = 120$ میباشد. بنابراین احتمال این رویداد $\frac{4}{120} = \frac{1}{30}$ است.
- شبکه و مسیریابی: فرض کنید در یک شهر با خیابانهای شطرنجی، میخواهیم از نقطه A به نقطه B برویم که نیاز به 4 حرکت به راست و 3 حرکت به بالا دارد. تعداد کل مسیرها برابر است با انتخاب جایگاه 4 حرکت به راست از میان 7 حرکت کلی: $C(7, 4) = 35$ مسیر.
- ضرایب بسط دو جملهای: در بسط $(x+y)^n$، ضریب جملهی $x^{n-r}y^r$ برابر با $C(n, r)$ است. این همان قضیهی معروف بسط دو جملهای است. برای مثال $(x+y)^3 = x^3 + 3x^2y + 3xy^2 + y^3$ که ضرایب $1, 3, 3, 1$ در واقع $C(3,0), C(3,1), C(3,2), C(3,3)$ هستند.
چالشهای مفهومی
۱. چرا در فرمول ترکیب بر $r!$ تقسیم میکنیم؟
فرمول جایگشت $P(n,r)$ تعداد راههای انتخاب و مرتب کردن r شیء را نشان میدهد. در ترکیب، ترتیب مهم نیست و هر مجموعه از r شیء، دقیقاً به تعداد $r!$ حالت مختلف در جایگشتها ظاهر میشود. بنابراین برای بهدست آوردن تعداد ترکیبها، باید تعداد جایگشتها را بر $r!$ تقسیم کنیم: $C(n,r) = \frac{P(n,r)}{r!} = \frac{n!}{(n-r)! \times r!}$.
۲. آیا $C(n, r)$ برای اعداد غیرصحیح یا منفی نیز تعریف میشود؟
در سطح دبیرستان و در علم ترکیبیات کلاسیک، $n$ و $r$ اعداد صحیح و نامنفی هستند و شرط $0 \le r \le n$ برقرار است. اگر $r$ از $n$ بزرگتر باشد، مقدار ترکیب صفر در نظر گرفته میشود، زیرا نمیتوان بیش از تعداد کل اشیاء، انتخاب انجام داد. در ریاضیات پیشرفتهتر، مفهوم «ضریب دو جملهای تعمیمیافته» برای اعداد حقیقی وجود دارد که در محاسبات سریها کاربرد دارد.
۳. تفاوت بین «ترکیب با تکرار» و «ترکیب بدون تکرار» چیست؟
نماد $C(n,r)$ که در این مقاله بررسی شد، برای حالت «بدون تکرار» است؛ یعنی هر شیء حداکثر یکبار میتواند انتخاب شود. در حالتی که امکان انتخاب مکرر یک شیء وجود داشته باشد (مثلاً انتخاب 3 نوع میوه از بین 5 نوع میوه با این اجازه که یک نوع میوه را چند بار انتخاب کنیم)، از «ترکیب با تکرار» استفاده میشود که فرمول آن $C(n+r-1, r)$ است.
پاورقیها
1ترکیب (Combination): انتخاب تعدادی شیء از یک مجموعه، بدون توجه به ترتیب قرارگیری آنها.
2جایگشت (Permutation): چیدمان تعدادی شیء در یک ترتیب مشخص.
3فاکتوریل (Factorial): حاصلضرب تمام اعداد صحیح مثبت از 1 تا n که با نماد n! نمایش داده میشود. به عنوان مثال 5! = 5 \times 4 \times 3 \times 2 \times 1 = 120.
