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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• به چند روش می توان از بین اعضای مجموعه ${\displaystyle \{a,b,c,d\}}$، 2 عضو را انتخاب کرد؟ ${\displaystyle {\binom {4}{2}}=6}$
• در یک کلاس 30 نفره، می خواهیم 2 نفر را به عنوان معلم یار انتخاب کنیم، این کار به چند روش امکان پذیر است؟ ${\displaystyle {\binom {30}{2}}=435}$
• به چند طریق می‌توان 10 دختر و 5 پسر را در یک ردیف چید؛ طوری که هیچ 2 پسری کنار هم نباشند؟ ${\displaystyle {\binom {11}{5}}\times 10!\times 5!}$

• جایگشت

• عباس ثروتی، سعید نعمتی (اول بهار 1384)، ترکیبیات، انتشارات خوشخوان، شابک ۹۶۴-۸۶۰۱-۳۶-۴ تاریخ وارد شده در |سال= را بررسی کنید (کمک)
• حسین ربیعی، حسین غفاری (اول بهار 1384)، اصول و فنون ترکیبیات، نشر سالمی، شابک ۹۶۴-۶۹۴۷-۰۷-۷ تاریخ وارد شده در |سال= را بررسی کنید (کمک)
• ایوان نیون (چهارم 1381)، ریاضیات انتخاب، مرکز نشر دانشگاهی تاریخ وارد شده در |سال= را بررسی کنید (کمک)
• ویکی‌پدیای انگلیسی
• علیرضا علیپور (چهارم-1394)، آنالیزترکیبی، الگو، شابک ۹۷۸-۶۰۰-۶۹۲۴-۲۴-۳ تاریخ وارد شده در |سال= را بررسی کنید (کمک)

آروین ساعی اشجعی