فهرست مندرجات
ترکیب‌ها
از دیرباز، انتخاب کردن از چیزهایی بوده است که بشر با آن سر و کار زیادی داشته است. ترکیب‌ها، در واقع روی تعداد روش‌های انتخاب چند شیء از تعدادی شیء را مشخص می‌کنند.
تعریف ترکیب
ترکیب $r$ از $n$، برابر تعداد روش‌های انتخاب $r$ شیء از $n$ شیء متمایز است. ترکیب $r$ از $n$ با نمادهای $C_r^n$، $C(n, r)$ و $\binom{n}{r}$ نشان داده می‌شود. استفاده از نماد $\binom{n}{r}$، رایج‌تر است و «$r$ از $n$» خوانده می‌شود. حرف $C$ از کلمه‌ی combination می‌آید.
برای مثال، فرض کنید می‌خواهیم از حروف a, b, c, d دو حرف را انتخاب کنیم. روش‌های انتخاب ما می‌توانید به یکی از اشکال زیر باشد:
- {a, b}
- {a, c}
- {a, d}
- {b, c}
- {b, d}
- {c, d}
بنابراین $\binom{4}{2}=6$ است.
به راحتی می‌توانید بررسی کنید به ازای هر $n$ طبیعی، $\binom{n}{0}=1$ و $\binom{n}{1}=n$ است.
فرمول ترکیب
می‌خواهیم در حالت کلی، فرمولی برای $\binom{n}{r}$ بیابیم.
ابتدا بیایید بررسی کنیم ترکیب $r$ از $n$ با تبدیل $r$ از $n$ چه تفاوتی دارد. در تبدیل $r$ از $n$ یا $P_r^n$، ترتیب اعضایی که انتخاب می‌کنیم نیز مهم است و اعضای انتخابی، ترتیب دارند اما در ترکیب $r$ از $n$ یا $C_r^n$، ترتیب اعضایی که انتخاب می‌کنیم مهم نیست و تنها مهم است هر عضو انتخاب می‌شود یا نمی‌شود. برای مثال، همان مسئله‌ی انتخاب ۲ حرف از ۴ حرف که در بالا آمد را در نظر بگیرید. برای $P_2^4$ حالت‌های ab, ba, ac, ca, ad, da, bc, cb, bd, db, cd, dc وجود دارد. پس $P_2^4=12$. در واقع به ازای هر انتخاب ${x, y}$ از حروف کلمه، ۲ حالت برای تبدیل آن ۲ حرف وجود دارد (xy, yx).
حال بیایید در حالت کلی $\binom{n}{r}$ را در نظر بگیریم. به ازای هر حالت این ترکیب، $r!$ حالت برای تبدیل آن وجود دارد؛ زیرا برای $r$ عضو انتخاب شده، $r!$ حالت برای ترتیب دادن وجود دارد. پس در حالت کلی داریم: $$p_r^n=\binom{n}{r}\times{}r!$$ پس با توجه به فرمول تبدیل $r$ از $n$ داریم:
$$\binom{n}{r}=\frac{P_r^n}{r!}=\frac{n!}{r!\times{}(n-r)!}$$
از فرمول بالا به دست می‌آید $\binom{n}{r}=\binom{n}{n-r}$.
یک مثال
مثال: چند رشته از ارقام ۰ و ۱ شامل $m$ رقم ۰ و $n$ رقم ۱ وجود دارد؟
پاسخ
این رشته $m+n$ رقم دارد. کافی است جای $m$ رقم ۰ را مشخص کنیم. به طور یکتا در این جاها رقم ۰ و در بقیه‌ی جاها رقم ۱ قرار خواهد گرفت. برای مشخص کردن جای ارقام ۰، باید $m$ رقم از $m+n$ رقم رشته را انتخاب کنیم. پس پاسخ برابر $\binom{m+n}{m}$ است.
اگر با مشخص کردن جای ارقام ۱، مسئله را حل می‌کردیم، به پاسخ $\binom{m+n}{n}$ می‌رسیدیم که با توجه به نکته‌ی ذکر شده، این ۲ پاسخ با هم برابر هستند.
سایر مثال‌ها
توجه: سعی کنید ابتدا خودتان روی مسائل به قدر کافی فکر کنید و سپس به پاسخ مراجعه کنید.
مثال:
- یک $n$-ضلعی کوژ (محدب) در نظر بگیرید. چند مثلث با رئوس این چندضلعی وجود دارد؟
- یک دایره در نظر بگیرید. در این دایره ۴ نقطه در یک طرف قطر $AB$ و ۵ نقطه در طرف دیگر آن داده شده است. چند مثلث با این ۹ نقطه وجود دارد؛ طوری که هر ۳ رأس آن در یک طرف $AB$ نباشند؟
پاسخ
برای قسمت اول، هر ۳ رأس چندضلعی، یک مثلث می‌سازند. پس پاسخ برابر $\binom{n}{3}$ است.
برای قسمت دوم، آن طرفی از دایره که ۴ نقطه دارد را طرف چپ و طرف دیگر را طرف راست می‌نامیم. حالت‌بندی می‌کنیم:
- مثلث ما یک نقطه در طرف راست و دو نقطه در طرف چپ داشته باشد. این قسمت طبق اصل ضرب، $\binom{4}{1}\binom{5}{2}=4\times10=40$ حالت دارد.
- مثلث ما دو نقطه در طرف راست و یک نقطه در طرف چپ داشته باشد. این قسمت طبق اصل ضرب، $\binom{4}{2}\binom{5}{1}=6\times5=30$ حالت دارد.
پس در کل پاسخ طبق اصل جمع، برابر $40+30=70$ است.
توجه: می‌توانید برای تمرین، قسمت دوم سوال را با اصل متمم حل کنید و پاسخ را با پاسخ به دست آمده مقایسه کنید.
مثال: ثابت کنید حاصل‌ضرب هر $r$ عدد طبیعی متوالی، بر $r!$ بخش‌پذیر است.
پاسخ
فرض کنیم این $r$ عدد، از عدد $n+1$ شروع شوند. پس داریم: $$P=(n+1)(n+2)...(n+r)$$ با ضرب کردن یک $\frac{n!}{n!}$ در عبارت داریم: $$P=(n+1)(n+2)...(n+r)\frac{n!}{n!}=\frac{(n+r)!}{n!}$$ با ضرب کردن یک $\frac{r!}{r!}$ در عبارت داریم: $$P=\frac{(n+r)!}{n!}\frac{r!}{r!}=\binom{n+r}{n}\times{}r!$$ پس داریم: $$\binom{n+r}{n}=\frac{P}{r!}$$ از آن‌جایی که $\binom{n+r}{n}$ عددی طبیعی است، مقدار $\frac{P}{r!}$ نیز عددی طبیعی است. پس $P$ بر $r!$ بخش‌پذیر است.
مثال: چند رشته‌ی ۱۰ رقمی از ۴ رقم ۰ و ۶ رقم ۱ داریم؛ طوری که سومین رقم ۰ (از سمت چپ) در رقم ۷ ام رشته (از سمت چپ) ظاهر شده باشد؟
پاسخ
در ۶ رقم اول رشته، باید ۲ رقم ۰ و ۴ رقم ۱ داشته باشیم که طبق مثال‌های قبلی، $\binom{6}{2}$ حالت دارد. در ۳ رقم آخر رشته، باید ۱ رقم ۰ و ۲ رقم ۱ داشته باشیم که طبق مثال‌های قبلی، $\binom{3}{1}$ حالت دارد. پس در کل پاسخ برابر $\binom{6}{2}\binom{3}{1}=15\times3=45$ است.
مثال: به چند طریق می‌توان ۱۰ دختر و ۵ پسر را در یک ردیف چید؛ طوری که هیچ ۲ پسری کنار هم نباشند؟
پاسخ
بیایید ابتدا از ترتیب صرف نظر کنیم و صرفن جای پسرها در ردیف را مشخص کنیم. ابتدا ۱۰ دختر را می‌گذاریم. ۱۱ فضای خالی در کنار و بین دخترها وجود دارد که پسرها می‌توانند در آن‌ها قرار بگیرند. در هر فضای خالی، حداکثر یک پسر می‌تواند قرار بگیرد زیرا اگر ۲ پسر قرار بگیرد، آن ۲ پسر کنار هم قرار خواهند گرفت که خلاف فرض مسئله است. پس باید برای پسرها، از ۱۱ فضای خالی موجود، ۵ فضا را انتخاب کنیم. این کار به $\binom{11}{5}$ طریق، قابل انجام است.
حال که جای پسرها مشخص شد، باید ترتیب دخترها و ترتیب پسرها را مشخص کنیم. ترتیب دخترها $10!$ و ترتیب پسرها $5!$ حالت دارد.
پس پاسخ برابر $\binom{11}{5}\times{}10!\times{}5!$ است.
مثال: $2n$ نفر در یک گروه داریم.
- به چند طریق می‌توان این افراد را به $n$ گروه متمایز دو نفره تقسیم کرد؟
- به چند طریق می‌توان این افراد را به $n$ گروه دو نفره تقسیم کرد؟
پاسخ
قسمت دوم این مسئله را در اصل ضرب و جای‌گشت‌های خطی دیده بودیم. می‌خواهیم روشی دیگر ارائه کنیم.
در قسمت اول، گروه‌ها متمایز هستند. پس می‌توانیم آن‌ها را با شماره‌های $1, 2, ..., n$ شماره‌گذاری کنیم. برای افراد گروه اول، باید ۲ نفر انتخاب کنیم که $\binom{2n}{2}$ حالت دارد. برای افراد گروه دوم، از $2n-2$ نفر باقی‌مانده، باید ۲ نفر انتخاب کنیم که $\binom{2n-2}{2}$ حالت دارد و همین طور الا آخر. پس در کل $\binom{2n}{2}\binom{2n-2}{2}...\binom{2}{2}$ حالت داریم.
در قسمت دوم، گروه‌ها با هم فرقی ندارند. پس کافی است ترتیبی که به گروه‌ها در قسمت اول داده‌ایم را حذف کنیم. به ازای هر حالت از پاسخ این قسمت، $n!$ حالت برای ترتیب تیم‌ها در پاسخ قسمت اول وجود دارد. پس پاسخ برابر $\frac{\binom{2n}{2}\binom{2n-2}{2}...\binom{2}{2}}{n!}$ است.
مسائل نمونه
- سوال ۱ مرحله اول دوره ۵
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
