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

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

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

ترکیب را با نمادهای ${\displaystyle \mathbf {C} (n,r)=\mathbf {C} _{r}^{n}={_{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\}$، ۲ عضو را انتخاب کرد؟ ${\displaystyle {\binom {4}{2}=6}$
• در یک کلاس ۳۰ نفره، می‌خواهیم ۲ نفر را به عنوان معلم یار انتخاب کنیم، این کار به چند روش امکان‌پذیر است؟ ${\displaystyle {\binom {30}{2}=435}$
• به چند طریق می‌توان ۱۰ دختر و ۵ پسر را در یک ردیف چید؛ طوری که هیچ ۲ پسری کنار هم نباشند؟ ${\displaystyle {\binom {11}{5}\times 10!\times 5!}$
• راه حل: بیایید ابتدا از ترتیب صرف نظر کنیم و صرفاً جای پسرها در ردیف را مشخص کنیم. ابتدا ۱۰ دختر را می‌گذاریم. ۱۱ فضای خالی در کنار و بین دخترها وجود دارد که پسرها می‌توانند در آن‌ها قرار بگیرند. در هر فضای خالی، حداکثر یک پسر می‌تواند قرار بگیرد زیرا اگر ۲ پسر قرار بگیرد، آن ۲ پسر کنار هم قرار خواهند گرفت که خلاف فرض مسئله است. پس باید برای پسرها، از ۱۱ فضای خالی موجود، ۵ فضا را انتخاب کنیم. این کار به ${\displaystyle {\binom {11}{5}$طریق، قابل انجام است. حال که جای پسرها مشخص شد، باید ترتیب دخترها و ترتیب پسرها را مشخص کنیم. ترتیب دخترها ${\displaystyle 10!}$ حالت و ترتیب پسرها ${\displaystyle 5!}$ حالت دارد. پس پاسخ برابر ${\displaystyle {\binom {11}{5}\times 10!\times 5!}$است.

• جایگشت

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