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