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

ترکیب

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

تعریف

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

نماد

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

جستارهای وابسته

• جایگشت

منابع

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

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

عملیات دوتایی
عددی	تابعی	مجموعه‌ای	ساختاری
مقدماتی + جمع – تفریق × ضرب ÷ تقسیم ^ توان حسابی div خارج قسمت اقلیدسی mod باقی‌مانده اقلیدسی ∧ بزرگ‌ترین مقسوم‌علیه مشترک ∨ کوچک‌ترین مضرب مشترک ترکیباتی () ضریب دوجمله‌ای P جایگشت C ترکیب	∘ ترکیب ∗ کانولوشن	جبر مجموعه‌ها ∪ اجتماع \ متمم نسبی ∩ اشتراک Δ تفاضل متقارن ترتیب کلی min کمینه max بیشینه توری‌ها ∧ کرانه تحتانی ∨ کرانه فوقانی	مجموعه‌ها × ضرب دکارتی ⊔ اجتماع منفصل ^ توان مجموعه‌ای گروه‌ها ⊕ حاصل‌جمع مستقیم ∗ حاصل‌ضرب آزاد ≀ produit en couronne مدول‌ها ⊗ ضرب تانسوری Hom هومومورفیزم Tor پیچش Ext extensions	درخت‌ها ∨ enracinement واریته‌های متصل # جمع متصل فضاهای نقطه‌دار ∨ bouquet ∧ smash produit ∗ joint
	بُرداری
	(.) ضرب اسکالر ∧ ضرب برداری
	جبری
	[,] کروشه لی {,} کروشه پواسون ∧ ضرب خارجی
	هومولوژی
	∪ cup-produit • حاصل‌ضرب اشتراک	ترتیبی
		+ الحاق
منطق بولی
∧ عطف منطقی	∨ فصل منطقی	⊕ یای انحصاری	⇒ استلزام منطقی	⇔ اگر و فقط اگر