نماد (n r) : کلید طلایی شمارش در ترکیبات
تعریف و شهود نماد (n r)
فرض کنید یک کیسه شامل n توپ متمایز (مثلاً 5 توپ با رنگهای مختلف) داریم. میخواهیم r تا از آنها را برداریم (مثلاً 3 تا). اگر ترتیب برداشتن توپها برایمان مهم نباشد و فقط به این فکر کنیم که کدام مجموعهٔ r تایی را در دست داریم، در این صورت با یک ترکیب مواجهیم. نماد (n r) که گاهی با C(n, r) نیز نشان داده میشود، دقیقاً تعداد این حالتها را به ما میدهد.
فرمول محاسباتی آن به صورت زیر است:
$ {n \choose r} = \frac{n!}{r! \times (n-r)!} $که در آن n! (خوانده میشود n فاکتوریل) حاصلضرب تمام اعداد طبیعی از 1 تا n است. برای درک بهتر، فرض کنید میخواهیم از میان 5 کتاب، 2 کتاب را برای مطالعه در سفر انتخاب کنیم. ترتیب مطالعه مهم نیست، بنابراین تعداد حالتها برابر است با:
$ {5 \choose 2} = \frac{5!}{2! \times 3!} = \frac{120}{2 \times 6} = 10 $یعنی 10 انتخاب متفاوت پیش رو داریم.
ارتباط با مثلث خیام-پاسکال و ضرایب دو جملهای
اگر مقادیر {n \choose r} را برای nهای مختلف به صورت یک مثلث مرتب کنیم، به مثلث خیام-پاسکال[1] میرسیم. در این مثلث، هر سطر متناظر با یک n است و اعداد داخل سطر، مقادیر {n \choose 0} تا {n \choose n} را نشان میدهند. این اعداد به دلیل خاصیت زیر، ضرایب دو جملهای[2] نیز نامیده میشوند.
وقتی عبارتی مانند (a + b)^n را بسط میدهیم، ضرایب هر جمله دقیقاً برابر با {n \choose r} است. به این قضیه، قضیهٔ دو جملهای میگویند:
$ (a + b)^n = \sum_{r=0}^{n} {n \choose r} a^{n-r} b^{r} $برای مثال، بسط (x + y)^4 به صورت زیر خواهد بود:
$ (x + y)^4 = {4 \choose 0} x^4 + {4 \choose 1} x^3 y + {4 \choose 2} x^2 y^2 + {4 \choose 3} x y^3 + {4 \choose 4} y^4 $$ = 1x^4 + 4x^3y + 6x^2y^2 + 4xy^3 + 1y^4 $
کاربردهای عملی در زندگی روزمره و مسائل علمی
نماد ترکیب فقط یک مفهوم انتزاعی نیست؛ در بسیاری از موقعیتهای واقعی به کار میآید:
- قرعهکشی و بازیها: احتمال برنده شدن در لوتوی 6 از 49 برابر است با $1 / {49 \choose 6}$.
- تشکیل تیم و کمیته: انتخاب یک کمیتهٔ 3 نفره از میان 10 نامزد، ${10 \choose 3} = 120$ حالت دارد.
- ژنتیک: در تعیین تعداد حالتهای ممکن برای ترکیب ژنها از والدین.
- رمزنگاری: در تحلیل تعداد کلیدهای ممکن برای سیستمهای رمزگذاری ساده.
برای درک عمیقتر، یک مثال کلاسیک از مسائل ترکیبی را بررسی میکنیم: «چند راه مختلف میتوانیم حروف کلمهٔ BOOK را مرتب کنیم؟» این مسئله با جایگشتهای دارای اشیاء تکراری حل میشود، اما ریشه در انتخاب جایگاه حروف دارد. اگر بخواهیم از میان 4 جایگاه، جایگاه حرف B و K را انتخاب کنیم، به ترکیبها برمیخوریم.
جدول مقایسه: ترکیب در برابر جایگشت
| ویژگی | ترکیب (n r) | جایگشت |
|---|---|---|
| نقش ترتیب | ترتیب مهم نیست | ترتیب مهم است |
| فرمول | $ \frac{n!}{r!(n-r)!} $ | $ \frac{n!}{(n-r)!} $ |
| مثال از ۵ شیء انتخاب ۲ تا | $\{A,B\}$ با $\{B,A\}$ یکی است | $AB$ و $BA$ دو حالت مجزا هستند |
چالشهای مفهومی
۱. چرا ${n \choose r} = {n \choose n-r}$؟
این تساوی یکی از مهمترین ویژگیهای نماد ترکیب است. انتخاب r عضو از n عضو، معادل است با انتخاب n-r عضوی که کنار میگذاریم. به بیان دیگر، تعداد راههای انتخاب اعضای یک تیم با تعداد راههای انتخاب اعضای ذخیره (غیرحاضر) برابر است.
۲. مقدار ${n \choose 0}$ چقدر است و چه معنایی دارد؟
بر اساس فرمول، ${n \choose 0} = \frac{n!}{0! \times n!} = 1. این یعنی تنها یک راه برای انتخاب صفر عضو از یک مجموعه وجود دارد: انتخاب هیچکدام! همچنین ${n \choose n} = 1$ به معنای یک راه برای انتخاب همهٔ اعضا است.
۳. اگر r > n باشد، ${n \choose r}$ چه میشود؟
در این حالت، نمیتوان r عضو از یک مجموعهٔ n عضوی انتخاب کرد. بنابراین، قرارداد میکنیم که ${n \choose r} = 0$. این با فرمول فاکتوریل نیز هماهنگی دارد زیرا فاکتوریل اعداد منفی تعریف نشده است.
پاورقی
[1] مثلث خیام-پاسکال: آرایش مثلثی از اعداد که در آن هر عدد حاصل جمع دو عدد بالای خود است. در غرب به نام پاسکال و در ایران به نام خیام[عمر خیام، ریاضیدان و شاعر ایرانی] شناخته میشود. کاربرد اصلی آن در محاسبهٔ ضرایب بسط دو جملهای است.
[2] ضرایب دو جملهای (Binomial Coefficients): اعداد {n \choose r} در بسط (a + b)^n ظاهر میشوند و نشاندهندهٔ تعداد حالتهای انتخاب r جملهٔ b از میان n عامل هستند.
