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

از ویکی‌پدیا، دانشنامهٔ آزاد

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

فهرست مندرجات

۱ تعریف
- ۱.۱ نماد
۲ محاسبه
۳ فرمول های مفید
۴ ترکیب های با تکرار
- ۴.۱ محاسبه
۵ منابع

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

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

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

[ویرایش] ترکیب های با تکرار

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

‎

$X_1 + X_2 + \dots + X_10 = 5$

در معادله بالا $X i$ ها نماینده 10 نوع کارت هستند و از آنجا که باید مجموع کارتها 5 شود در سمت راست معادله عدد 5 آمده است.حال هر جواب این معادله با یک جواب از مسئله اصلی(مسئله کارتها)متناظر است مثلا جواب $X 1 0 = 2$ ، $X 2 = 1$ ، $X 1 = 2$ در مسئله کارتها به این معنا است که از کارت نوع 1 به تعداد 2 عدد و از کارت نوع دوم به تعداد یکی ، از کارت نوع 10 تعداد 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 1 0 = 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. ‏
ویکی‌پدیای انگلیسی

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

از ویکی‌پدیا، دانشنامهٔ آزاد

فهرست مندرجات

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

[ویرایش] نماد

[ویرایش] محاسبه

[ویرایش] فرمول های مفید

[ویرایش] ترکیب های با تکرار

[ویرایش] محاسبه

[ویرایش] منابع

بازدیدها

ابزارهای شخصی

گشتن

جستجو

جعبه‌ابزار

زبان‌های دیگر