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

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

## تعریف
به هر انتخاب غیر مرتب  r  شیء از  n  شیء داده شده یک ترکیب  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    

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

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

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 \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_{10} = 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}}

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

{n+r-1 \choose r} 

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

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

{10+5-1 \choose 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!است.

## جستارهای وابسته
* جایگشت

## منابع

* 
* 
* 
* ویکی‌پدیای انگلیسی
* 

رده:ترکیبیات