ترکیبات در ریاضیات

تعریف

تعداد روش‌های انتخاب r شی از n شی به طوریکه ترتیب در انتخاب r شی اهمیت نداشته باشد. گاهی تعریف دیگری برای ترکیب ارائه می‌شود که شامل انتخاب زیر مجموعه r عضوی از یک مجموعه n عضوی می‌باشد.در تعریف دوم نیز مسلما ترتیب اعضا اهمیتی ندارد جراکه از تعریف مجموعه چنین برمی آید.

نماد

ترکیب را با نمادهای $\mathbf{C}(n,r) = \mathbf{C}_r^n= {_nC_r} = {n \choose 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 تقسیم شود:

${n \choose r} = \frac{P_r^n}{r!} = \frac{\frac{n!}{(n-r)!}}{r!}$

${n \choose r} = \frac{n!}{r!\times(n-r)!}$

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

${n \choose r} = {n \choose n-r}$

${n \choose r} = {n-1 \choose r} + {n-1 \choose r-1}$

(فرمول پاسکال)

${n \choose 0} + {n \choose 1} + {n \choose 2} + \dots + {n \choose n} = 2^n$

(مجموع ضرایب بسط دو جمله ای)

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

فرض کنید 10 نوع کارت مختلف داریم(روی هر کارت شکل متفاوتی وجود دارد)و از هر نوع کارت به تعداد بی نهابت(البته به دلایلی که در ادامه آمده به جای واژه بی نهایت می‌توان از 5 استفاده کرد) تا در دسترس داریم.حال تعداد راه‌هایی که می‌توان 5 کارت از بین کل کارت‌ها انتخاب کرد برابر است با تعداد جواب‌های معادله زیر:

$X_1 + X_2 + \dots + X_10 = 5$

در معادله بالا $X i$ ها نماینده 10 نوع کارت هستند و از آنجا که باید مجموع کارتها 5 شود در سمت راست معادله عدد 5 آمده است.حال هر جواب این معادله با یک جواب از مسئله اصلی(مسئله کارتها)متناظر است مثلا جواب $X 1 0 = 2$ ، $X 2 = 1$ ، $X 1 = 2$ در مسئله کارتها به این معنا است که از کارت نوع 1 به تعداد 2 عدد و از کارت نوع دوم به تعداد یکی، از کارت نوع 10 تعداد 2 تا و از سایر کارت‌ها هیچی انتخاب نکرده ایم و به طور بلعکس جوابی که در مورد کارتها در خط بالا مطرح شد خود یک جواب برای معادله به شمار می‌آید.

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

محاسبه

می خواهیم پاسخ معادله زیر را بیابیم:

$X_1 + X_2 + \dots + X_n = r$

$0 \le 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 1 0 = 2$ ، $X 2 = 1$ ، $X 1 = 2$ است:

$\underbrace{ UU }_{X_1}$ S $\underbrace{ U }_{X_2}$ S $\underbrace{ }_{X_3}$ S ... S $\underbrace{ UU }_{X_{10}}$