ترکیبیات (ابزارهای شمارشی)

مقدمه‌ ای بر شمارش

شاید شمارش در نظر برخی افراد، یک مهارت با اهمیت ریاضی نباشد و تنها یک عمل ساده باشد، اما آیا واقعا شمردن همیشه آسان است؟

می‌دانید که دو اتومبیل نباید پلاک یکسان داشته باشند.

با پلاک‌هایی به‌صورت زیر، با استفاده از حروف و اعداد، چند اتومبیل را می‌توان شماره گذاری کرد؟

امروزه به افراد جهت شناسایی آنها شناسه‌های مختلفی نسبت می‌دهند، از جمله:

• شماره شناسنامه
• کد ملی
• پلاک ماشین

نیز جهت تعیین مالکیت آنها، شماره و کدهایی نسبت داده می‌شود که گاهی از چند رقم یا حروفی در کنار هم تشکیل شده‌اند.

در این بخش به دنبال یافتن روش‌هایی برای شمارش اعضای یک مجموعه محدود با قوانین معین و تعیین تعداد حالات ممکنه بدون شمردن هر یک از حالات هستیم به‌عبارت دیگر آنالیز ترکیبی روش‌های شمارش را ارائه می‌دهد.

اصل جمع

اگر برای انجام عمل $A$ تعداد $n\left(A\right)$ روش و برای انجام عمل $B$ تعداد $n\left(B\right)$ روش وجود داشته باشد، با فرض مستقل بودن دو عمل آن‌گاه تعداد روش‌های انجام عمل $A$ (یا) عمل $B$ عبارت است از:

$n\left(A\right)+n\left(B\right)$

اصل جمع را می‌توان برای $n$ عمل $A_n,\mathrm{...},A_2,A_1$ که به‌ترتیب به $n\left(A_n\right),\mathrm{...},n\left(A_2\right),n\left(A_1\right)$ روش انجام آنها امکان پذیر است، تعمیم داد که در این‌صورت تعداد روش‌های انجام عمل $A_1$ (یا) $A_2$ (یا) .... (یا) $A_n$ عبارت است از:

$\sum _{i=1}^{n}n\left(A_i\right)=n\left(A_1\right)+n\left(A_2\right)+\cdot \cdot \cdot +n\left(A_n\right)$

اصل ضرب

اگر برای انجام عمل $A$ تعداد $n\left(A\right)$ روش و برای انجام عمل $B$ تعداد $n\left(B\right)$ روش وجود داشته باشد، با فرض مستقل بودن دو عمل آن‌گاه تعداد روش‌های انجام عمل $A$ (و) عمل $B$ عبارت است از:

$n\left(A\right)\times n\left(B\right)$

اصل ضرب را می‌توان برای $n$ عمل $A_n,\mathrm{...},A_2,A_1$ که به‌ترتیب به $n\left(A_n\right),\mathrm{...},n\left(A_2\right),n\left(A_1\right)$ روش انجام آنها امکان پذیر است، تعمیم داد که در این‌صورت تعداد روش‌های انجام عمل $A_1$ (و) $A_2$ (و) .... (و) $A_n$ عبارت است از:

$\prod _{i=1}^{n}n\left(A_i\right)=n\left(A_1\right)\times \cdot \cdot \cdot \times n\left(A_n\right)$