ترکیب (ریاضی)

ترکیب الگو:انگلیسی در حوزه ریاضیات مفهوم نزدیکی به جایگشت دارد. جایگشت (تبدیل) تعداد حالات چیده شدن تعدادی معین از اعضای یک مجموعه در مکان‌هایی معین است، در حالی که ترکیب تعداد حالات انتخاب تعدادی معین از اعضای یک مجموعه است.

تعریف

به هر انتخاب غیر مرتب $r$ شیء از $n$ شیء داده شده یک ترکیب $r$ شیء از این $n$ شیء گفته می‌شود

نماد

ترکیب را با نمادهای $𝐂 (n, r) = 𝐂_{r}^{n} =_{n} C_{r} = (\binom{n}{r})$ نمایش می‌دهند و آن را انتخاب $r$ از $n$ می‌خوانند.

محاسبه

می‌خواهیم از مجموعهٔ { $a_{1}, a_{2}, . . ., a_{n}$ } که تمامی اعضایش متمایزند، یک زیرمجموعهٔ $r$ عضوی انتخاب کنیم. برای این کار ابتدا سعی می‌کنیم تا $r$ عضو از این مجموعه را در یک ردیف به دنبال هم قرار دهیم که این همان جایگشت $r$ تایی از بین $n$ عضو است که بنابر محاسبه جایگشت‌ها، تعداد حالات انجام این کار برابر با $P_{r}^{n}$ است. با کمی دقت می‌توان دریافت که در حین این عملیات، ما هم $r$ عضو از بین $n$ عضو مجموعه اصلی انتخاب کردیم و هم آن‌ها را در یک ردیف چیدیم، در حالی که برای به دست آوردن تعداد ترکیب $r$ تایی از بین $n$ عضو تنها باید $r$ عضو انتخاب کرده و بخش دوم یعنی چیدن آن‌ها در یک ردیف را انجام ندهیم. برای رسیدن به این مطلوب، باید در نظر داشت که هر $r$ عضو { $a_{x_{1}}, a_{x_{2}}, . . ., a_{x_{r}}$ } به تعداد $r!$ جایگشت ایجاد می‌کنند که در ترکیب این جایگشت‌ها حالات تکراری محسوب می‌شوند در نتیجه باید پاسخ بر $r!$ تقسیم شود: الگو:چپ‌چین $(\binom{n}{r}) = \frac{P_{r}^{n}}{r!} = \frac{\frac{n!}{(n - r)!}}{r!}$

$(\binom{n}{r}) = \frac{n!}{r! \times (n - r)!}$ الگو:پایان چپ‌چین

فرمول‌های مفید

الگو:چپ‌چین $(\binom{n}{r}) = (\binom{n}{n - r})$ الگو:پایان چپ‌چین

الگو:چپ‌چین $(\binom{n}{r}) = (\binom{n - 1}{r}) + (\binom{n - 1}{r - 1})$ الگو:پایان چپ‌چین (فرمول پاسکال)

الگو:چپ‌چین $(\binom{n}{0}) + (\binom{n}{1}) + (\binom{n}{2}) + \dots + (\binom{n}{n}) = 2^{n}$ الگو:پایان چپ‌چین (مجموع ضرایب بسط دو جمله ای)

ترکیب‌های با تکرار

فرض کنید ۱۰ نوع کارت مختلف داریم (روی هر کارت شکل متفاوتی وجود دارد) و از هر نوع کارت به تعداد بی‌نهایت (البته به دلایلی که در ادامه آمده به جای واژهٔ بی‌نهایت می‌توان از ۵ استفاده کرد) در دسترس داریم. حال تعداد راه‌هایی که می‌توان ۵ کارت از بین کل کارت‌ها انتخاب کرد برابر است با تعداد جواب‌های معادله زیر: الگو:چپ‌چین $X_{1} + X_{2} + \dots + X_{10} = 5$ الگو:پایان چپ‌چین

در معادلهٔ بالا $X_{i}$ ها نمایندهٔ ۱۰ نوع کارت هستند و از آنجا که باید مجموع کارت‌ها ۵ شود، در سمت راست معادله عدد ۵ آمده است. حال هر جواب این معادله با یک جواب از مسئلهٔ اصلی (مسئلهٔ کارتها) متناظر است مثلاً جواب $X_{10} = 2$ ، $X_{2} = 1$ ، $X_{1} = 2$ در مسئلهٔ کارت‌ها به این معنا است که از کارت نوع ۱ به تعداد ۲ عدد، از کارت نوع ۲ به تعداد ۱ عدد و از کارت نوع ۱۰ تعداد ۲ عدد و از سایر کارت‌ها هیچی انتخاب نکرده‌ایم و به‌طور بلعکس جوابی که در مورد کارت‌ها در خط بالا مطرح شد خود یک جواب برای معادله به‌شمار می‌آید.

حال که تناظر بین هر جواب معادله و مسئلهٔ کارت‌ها مشخص شد می‌خواهیم به دنبال محاسبهٔ تعداد جواب‌های معادله فوق باشیم.

محاسبه

می‌خواهیم پاسخ معادلهٔ زیر را بیابیم: الگو:چپ‌چین $X_{1} + X_{2} + \dots + X_{n} = r$ الگو:پایان چپ‌چین الگو:چپ‌چین $0 \leq X_{i}$ الگو:پایان چپ‌چین

ادعا می‌کنیم که هر جایگشت دلخواه که با $n - 1$ تا $S$ و $r$ تا $U$ نوشته شود با یکی از جوابهای معادله فوق متناظر است. به این صورت که برای هر جایگشت دلخواه از $U$ و $S$ ها تعداد $U$ ‌هایی که قبل از اولین $S$ آمده نشان دهنده جوابی برای $X_{1}$ است و تعداد Uهای بین اولین و دومین $S$ نشان دهنده عدد متناظر با $X_{2}$ است … و در نهایت تعداد $U$ های بعد از آخرین $S$ نشان دهنده مقدار $X_{n}$ می‌باشد.

مثلاً برای معادله $X_{1} + X_{2} + \dots + X_{10} = 5$ جایگشت زیر معادل با جواب $X_{10} = 2$ ، $X_{2} = 1$ ، $X_{1} = 2$ است:

الگو:چپ‌چین

$\underset{X_{1}}{\underset{⏟}{U U}}$ S $\underset{X_{2}}{\underset{⏟}{U}}$ S $\underset{X_{3}}{⏟}$ S … S $\underset{X_{10}}{\underset{⏟}{U U}}$ الگو:پایان چپ‌چین

می‌دانیم که تعداد جایگشت‌های باتکرار برای $n - 1$ عنصر یکسان و $r$ عنصر یکسان دیگر در یک ردیف برابر است با:

الگو:چپ‌چین $(\binom{n + r - 1}{r})$ الگو:پایان چپ‌چین

بنابراین تعداد ترکیب‌های با تکرار برابر با مقدار فوق می‌باشد.

پس تعداد جواب مسئله کارت‌ها برابر است با:

الگو:چپ‌چین $(\binom{10 + 5 - 1}{5}) = 2002$ الگو:پایان چپ‌چین

مثال

به چند روش می‌توان از بین اعضای مجموعه ${a, b, c, d}$ ، ۲ عضو را انتخاب کرد؟ $(\binom{4}{2}) = 6$
در یک کلاس ۳۰ نفره، می‌خواهیم ۲ نفر را به عنوان معلم یار انتخاب کنیم، این کار به چند روش امکان‌پذیر است؟ $(\binom{30}{2}) = 435$
به چند طریق می‌توان ۱۰ دختر و ۵ پسر را در یک ردیف چید؛ طوری که هیچ ۲ پسری کنار هم نباشند؟ $(\binom{11}{5}) \times 10! \times 5!$
راه حل: بیایید ابتدا از ترتیب صرف نظر کنیم و صرفاً جای پسرها در ردیف را مشخص کنیم. ابتدا ۱۰ دختر را می‌گذاریم. ۱۱ فضای خالی در کنار و بین دخترها وجود دارد که پسرها می‌توانند در آن‌ها قرار بگیرند. در هر فضای خالی، حداکثر یک پسر می‌تواند قرار بگیرد زیرا اگر ۲ پسر قرار بگیرد، آن ۲ پسر کنار هم قرار خواهند گرفت که خلاف فرض مسئله است. پس باید برای پسرها، از ۱۱ فضای خالی موجود، ۵ فضا را انتخاب کنیم. این کار به $(\binom{11}{5})$ طریق، قابل انجام است. حال که جای پسرها مشخص شد، باید ترتیب دخترها و ترتیب پسرها را مشخص کنیم. ترتیب دخترها $10!$ حالت و ترتیب پسرها $5!$ حالت دارد. پس پاسخ برابر $(\binom{11}{5}) \times 10! \times 5!$ است.

جستارهای وابسته

جایگشت

منابع

الگو:پانویس

الگو:عملیات دوتایی

ترکیب (ریاضی)

فهرست

تعریف

نماد

محاسبه

فرمول‌های مفید

ترکیب‌های با تکرار

محاسبه

مثال

جستارهای وابسته

منابع

منوی ناوبری

ترکیب (ریاضی)

تعریف

نماد

محاسبه

فرمول‌های مفید

ترکیب‌های با تکرار

محاسبه

مثال

جستارهای وابسته

منابع

منوی ناوبری

جستجو