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

برای دیگر کاربردها، ترکیب (ابهام‌زدایی) را ببینید.

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

تعریف

تعداد روش‌های انتخاب 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$

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

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

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

$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$

منابع

• عباس ثروتی، سعید نعمتی. ترکیبیات. چاپ اول بهار 1384. انتشارات خوشخوان. ISBN 964-8601-36-4. 
• حسین ربیعی، حسین غفاری. اصول و فنون ترکیبیات. چاپ اول بهار 1384. نشر سالمی. ISBN 964-6947-07-7. 
• ایوان نیون. ریاضیات انتخاب. چاپ چهارم 1381. مرکز نشر دانشگاهی. ISBN 964-01-0457-3. 
• ویکی‌پدیای انگلیسی

پیوندهای خارجی

• روش های محاسبه ترکیب دو عدد