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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

تعریف[ویرایش]

تعداد روش‌های انتخاب 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. 
  • ویکی‌پدیای انگلیسی

پیوند به بیرون[ویرایش]