ترکیب و جایگشت

شما ممکن است فکر کنید همه چیز را در مورد شمارش می دانید. از این گذشته، شما از وقتی که سه سالتان بوده است شمارش را بلد بودید، چند تا انگشت دارید، چند تا کلوچه در بشقاب هست. شمارش انگشتان و کلوچه ها کار آسانی است. چالش از آنجا آغاز می شود که بخواهید مجموعه های خیلی خیلی بزرگ را شمارش کنید. خوشبختانه جبر برای شما چندین تکنیک فراهم آورده است که با استفاده از آنها می توانید به صورت موثر مجموعه های بزرگ را شمارش کنید: اصل ضرب (multiplication principle)، جایگشت ها (permutations)، و ترکیبات (combinations) . (برای آشنایی عمیقتر با این موضوعات می توانید کتاب Probability For Dummies که در مورد آموزش احتمال می باشد را مطالعه نمایید.) قطعاً هر کدام از این تکنیکها را در موقعیتهای مختلف مورد استفاده قرار خواهید داد، اگرچه، تصمیم گیری در مورد اینکه کدام تکنیک را باید استفاده کنید، غالباً بزرگترین چالش کار است.

به کار بردن اصل ضرب بر روی مجموعه ها

قوانین جبر: اصل ضرب (multiplication principle) زمانی به کار شما می آید که بخواهید مجموع تعداد روش هایی را که کارها یا سایر چیزها می توانند انجام شوند را بدانید، برای این کار شما تعداد اعضاء مجموعه ها را در یکدیگر ضرب می کنید. اگر شما بتوانید کار $1$ را با $m_1$ روش انجام دهید، و کار $2$ را با $m_2$ روش، کار $3$ با $m_3$ روش، و به همین ترتیب، شما می توانید تمامی این کارها را با $m_1 \cdot m_2 \cdot m_3 \cdot ...$ روش انجام بدهید.

به عنوان مثال، اگر شما شش پیراهن، چهار شلوار، هشت جفت جوراب، و دو جفت کفش داشته باشید، می توانید آنها را به $6 \cdot 4 \cdot 8 \cdot 2 = 384$ روش مختلف بپوشید. البته، در این مسأله هماهنگ بودن رنگ یا مدل لباسها با یکدیگر، به حساب آورده نشده اند.

با در نظر گرفتن قوانین زیر، چند پلاک وسیلۀ نقلیه متفاوت می تواند در یک ایالت وجود داشته باشد:

تمامی پلاکها شامل سه حرف الفبا هستند که به دنبال آنها دو عدد آمده است.
اولین حرف نمی تواند O باشد.
اولین عدد نمی تواند صفر یا یک باشد.

به این مسأله به عنوان کاندیدای اول برای اصل ضرب فکر کنید. در اینجا اولین قانون برای پلاک ها را داریم:
$$
\text{# of ways letter } 1 \cdot \text{ # of ways letter } 2 \cdot \text{ # of ways letter } 3 \cdot \\
\text{# of ways number } 1 \cdot \text{ # of ways number } 2
$$

# : تعداد
of ways letter : تعداد روش هایی که حرفِ
of ways number: تعداد روش هایی که عددِ

شما نمی توانید از O برای حرف اول استفاده کنید، بنابراین تعداد $25$ روش برای حرف اول وجود خواهد داشت. حرف دوم و سوم هیچ محدودیتی ندارند، بنابراین شما می توانید هر کدام از $26$ حرف الفبا را برای آنها انتخاب کنید. اولین عدد نمی تواند صفر یا یک باشد، بنابراین هشت انتخاب برای شما باقی می ماند. دومین عدد هیچ محدودیتی ندارد و شما تمامی ده رقم ممکن از صفر تا نه را در اختیار دارید. شما به سادگی این انتخابهای ممکن را در یکدیگر ضرب می کنید تا به پاسخ مدنظر برسید: $25 \cdot 26 \cdot 26 \cdot 8 \cdot 10 = 1,352,000$ . از آنجا که فقط حدود یک میلیون انتخاب برای پلاکها موجود است می توانید فرض کنید که این ایالت نباید ایالت خیلی بزرگی باشد. و به من اعتماد کنید، استفاده از اصل ضرب برای یافتن پاسخ این سوال، ساده تر از مراجعه به مرکز شماره گذاری خودروها می باشد!

سازماندهی جایگشت مجموعه ها

جایگشتِ (permutation) چند مجموعه از اعضاء، برابر با بازچینش ترتیب آن اعضاء می باشد. به عنوان مثال، شما می توانید حروف موجود در کلمۀ act را بازچینش کنید تا شش کلمۀ محتمل دیگر را با آنها بسازید (این کلمات الزاماً معنادار نیستند): act, cat, atc, cta, tac, tca . بنابراین، در اینجا می گویید که در مورد کلمۀ act ، شما شش جایگشت برای سه عضو دارید.

شمارش جایگشت ها

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

قوانین جبر: شما تعداد جایگشت هایِ $n$ عضو را که هر بار به تعداد $r$ گرفته می شوند، با فرمول زیر بدست می آورید (تعداد جایگشت ها را با $P$ نشان می دهند):
$$ _nP_r = \frac{n!}{(n-r)!} $$

به عنوان مثال، اگر بخواهید چهار تا از شش گلدان موجود در یک قفسه را باز چینش کنید، چند چینش (ترتیب) مختلف میسر است؟ اگر شما گلدان ها را با حروف A, B, C, D, E, F برچسب گذاری کنید، برخی از این چینش ها عبارتند از: ABCD, ABCE, ABCF, BCFD, BFDC و به همین ترتیب.

با استفاده از فرمول جایگشت، شما $n=6$ و $r=4$ را دارید:
$$ _6P_4=\frac{6!}{(6-4)!}=\frac{6!}{2!}=\frac{6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{2 \cdot 1}=6 \cdot 5 \cdot 4 \cdot 3=360 $$
با این عددی که بدست آمده است، امیدوارم برنامه نداشته باشید که از هر کدام از حالتها عکس بگیرید!

در اینجا مثالی داریم که مشاهدات گسترده تری را از جایگشت تشرح می کند. فرض کنید که هفت کوتوله بخواهند برای یک عکس خانوادگی به خط شوند. به چند روش مختلف این کوتوله ها می توانند برای این عکس، به خط شوند؟ به لحاظ جبری، شما به دنبال جایگشت هفت چیز که، هر بار هفت چیز گرفته میشود، می باشید. با استفاده از فرمول جایگشت داریم:
$$ _7P_7=\frac{7!}{(7-7)!}=\frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{1}=7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1=5,040 $$
اکنون می توانید ببینید که چرا ریاضیدانان $0!=1$ تعریف کرده اند. در این فرمول، شما به یک $0$ در مخرج کسر بر می خورید، زیرا تعداد آیتم های انتخاب شده با تعداد آیتم های موجود برابر می باشند. با فرض کردن اینکه $0!=1$ ، مخرج کسر تبدیل به $1$ می شود، و پاسخ مقدار موجود در صورت کسر می شود.

یادتان باشد: هنگامی که از فرمول جایگشت $n$ عضو که هر بار تعداد $r$ از آن گرفته می شود، استفاده می کنیم، داریم:

$_nP_n=\frac{n!}{(n-n)!}=\frac{n!}{0!}=n!$ . هنگامی که از تمامی اعضاء در بازچینش استفاده می کنید، صرفاً نیاز دارید تا $n!$ را بدست آورید.
$\require{cancel}
_nP_1=\frac{n!}{(n-1)!}=\frac{n \cdot \cancel{(n-1)} \cdot \cancel{(n-2)} \cdot \cancel{(n-3)} \cdot \text{ ...} \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{\cancel{(n-1)} \cdot \cancel{(n-2)} \cdot \cancel{(n-3)} \cdot \text{ ...} \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}=n $ . هنگامیکه فقط یکی از اعضاء را از بین تمامی انتخابهای ممکن، در نظر می گیرید، شما فقط $n$ بازچینش مختلف خواهید داشت.
$_nP_0=\frac{n!}{(n-0)!}=\frac{n!}{n!}=1$ . هنگامی که هیچکدام از اعضاء مجموعه را انتخاب نمی کنید، فقط یک روش ممکن در اختیار دارید.

برخی از مشکلات نیاز به ترکیبی از جایگشت ها و اصل ضرب دارند. به عنوان مثال، فرض کنید می خواهید یک کلمۀ عبور جدید برای حساب کامپیوتری خودتان بسازید. اولین قانون اینست که دو ورودی اول باید حروف الفبا باشند ـــ بدون تکرار، و شما نمی توانید از حروف O یا I استفاده کنید. چهار ورودی بعدی باید رقم باشند ـــ بدون هیچ محدودیتی. سپس می توانید دو حرف الفبای دیگر بدون هیچ محدودیتی وارد کنید. در پایان، سه ورودیِ آخر باید سه رقم بدون تکرار باشند. چند کلمۀ عبور مختلف ممکن است؟

این مسأله را به چهار بخش مختلف تقسیم کنید، اصل ضرب را ایجاد کنید:

$$ \text{ 2 letters, no repeats, no O or I × 4 digits × 2 letters × 3 digits, no repeats } $$

دو حرف الفبا، بدون تکرار، بدون حروف O یا I $\times$ چهار رقم $\times$ دو حرف الفبا $\times$ سه رقم، بدون تکرار

اکنون می توانید جایگشت ها را ایجاد کنید:

سازماندهی دو حرف الفبای اول جایگشتی از $24$ عضو می باشد که هر بار $2$ تا از آنها گرفته می شوند.
چهار رقم بعدی به شما $10$ انتخاب در هر مرحله می دهند ـــ در یکدیگر ضرب می شوند.
دو حرف بعدی هر بار $26$ انتخاب به شما می دهند ـــ در یکدیگر ضرب می شوند.
سه رقم نهایی نشان دهندۀ جایگشتی از $10$ عضو هستند که هر بار $3$ تا از آنها گرفته می شوند.

محاسبات به شکل زیر ادامه می یابند:
$$
_{24}P_2 \times 10 \cdot 10 \cdot 10 \cdot 10 \times 26 \cdot 26 \times _{10}P_3 \\[2ex]
=\frac{24!}{22!} \times 10^4 \times 26^2 \times \frac{10!}{7!} \\[2ex]
=552 \times 10,000 \times 676 \times 720 \\[2ex]
=2,686,694,400,000
$$
شما بیش از دو و نیم تریلیون کلمۀ عبور مختلف را محاسبه کردید. خوشبختانه، این قوانین هکرها را دور نگه می دارند. اکنون فقط کافیست این کلمۀ عبور را به خاطر داشته باشید!

جایگشت های قابل تشخیص

اگر کتابهای موجود در قفسۀ کتابتان را بر اساس رنگ آنها مرتب سازی کرده باشید ـــ به خاطر چشم نواز بودنشان ـــ و نه بر اساس موضوع یا مولف آنها، شما نمی توانید بین کتابهای قرمز و کتابهای آبی مختلف تمایز قائل شوید. و اگر بخواهید تا تعداد جایگشت های حروف کلمۀ cheese را بدانید، نمی توانید بین cheese و cheese که در آنها جای دو e کنار هم تغییر یافته اند، تمایزی قائل شوید. بنابراین بازچینش حروف یکسان را در جایگشت های مختلف شمارش نمی کنید. روشی که شمارندۀ شما بتواند این تاثیر را لحاظ کند، استفاده از فرمول جایگشت های قابل تشخیص (distinguishable permutations) می باشند.

قوانین جبر: اگر یک مجموعه از $n$ شیء دارای $k_1$ عضو مشابه باشند، $k_2$ عضو مشابه باشند، و به همین ترتیب، شما تعداد جایگشت های قابل تشخیص آن $n$ شیء را با فرمول زیر بدست می آورید:
$$ \frac{n!}{k_1!k_2!k_3!...} $$

با استفاده از این فرمول، شما می توانید تعداد جایگشت های قابل تشخیص کلمۀ cheese را تعیین کنید:
$$
\require{cancel}
\frac{6!}{3!}=\frac{6 \cdot 5 \cdot 4 \cdot \cancel{3!}}{\cancel{3!}}=120
$$
کلمۀ Cheese روی هم رفته دارای شش حرف می باشد، و سه e همگی یکسان می باشند.

شما همچنین می توانید این فرمول را بر روی کتابهای موجود در قفسه بکار ببندید. فرض کنید ده کتاب آبی، پنج کتاب قرمز، شش کتاب سیاه، یک کتاب سبز، و یک کتاب خاکستری دارید. شما $8 \times 10^{10}$ بازچینش قابل تشخیص ممکن از کتابها را دارید. شما می توانید این تعداد را با استفاده از فرمول جایگشت های قابل تشخیص تعیین کنید:
$$
\frac{23!}{10!5!6!}=8.245512475 \times 10^{10}
$$
اکنون فرض کنید می خواهید تمامی کتابهای همرنگ را کنار یکدیگر قرار دهید، و به ترتیب کتابها در هر گروه از رنگها، اهمیتی نمی دهید. چند چینش مختلف میسر است؟ این مسأله، جایگشت پنج رنگ (آبی، قرمز، سیاه، سبز، و خاکستری) می باشد. جایگشت $5$ عضو که در هر بار $5$ تا گرفته می شود برابر با $5!=120$ چینش متفاوت می باشد.

اگر شما یک دکوراتیو متوجه جزئیات باشید، تصمیم می گیرید که چینش داخل هر کدام از رنگها حائز اهمیت می باشد، و می خواهید کتابها در گروههایی با رنگهایی یکسان چینش گردند. چند چینش متفاوت میسر است؟ این مسأله در ابتدا شامل جایگشت رنگهای مختلف و سپس جایگشت کتابها در رنگ آبی، قرمز، و مشکی می باشد. با عملیات ریاضی به نتایج زیر می رسید:
$$
\text{Colors} \times \text{Blues} \times \text{Reds} \times \text{Blacks} \\[2ex]
=(_5P_5) \times (_{10}P_{10}) \times (_5P_5) \times (_6P_6) \\[2ex]
=5! \times 10! \times 5! \times 6! \\[2ex]
=3.76233984 \times 10^{13}
$$
به طور کلی شما چندین روش برای چینش کتابها در قفسه دارید. شاید ترتیب الفبایی از همه معنادارتر باشد.

ترکیب در مجموعه ها

ترکیب (Combination) یک واژۀ دقیق ریاضی است و به این اشاره دارد که چگونه می توانید تعداد خاصی عناصر را از یک مجموعه انتخاب کنید. در ترکیب ها، ترتیبی که عناصر ظاهر می گردند، اهمیتی ندارد. به عنوان مثال، ترکیب ها به شما امکان می دهند تا تعیین کنید به چند روش مختلف می توانید سه نفر را به عنوان عضوی از یک کمیته انتخاب کنید (ترتیبی که آنها را انتخاب می کنید، حائز اهمیت نمی باشد).

قوانین جبر: شما تعداد روشهای ممکن انتخاب $r$ عضو از مجموعه ای که شامل $n$ عضو باشد را با فرمول زیر بدست می آورید و آن را $C$ می نامید:
$$ _nC_r=\frac{n!}{(n-r)!r!} $$

بخش اعظم این فرمول باید آشنا به نظر برسد؛ این فرمول تعداد جایگشت های $n$ عضو که هر بار تعداد $r$ از آنها گرفته می شود، می باشد ـــ البته با یک فاکتور اضافی در مخرج کسر. این فرمول در واقع همان فرمول جایگشت است که بر $r!$ تقسیم شده است.

نکته: شما همچنین می توانید ترکیبات را با دو نماد دیگر نیز نشان دهید:
$$
C(n,r)\\
{n \choose r}
$$

نمادهای مختلف همگی معنای یکسانی می دهند و دارای پاسخ یکسانی می باشند. بیشتر اوقات، نمادی که انتخاب می کنید بستگی به سلیقۀ شخصی شما یا چیزی که بر روی ماشین حسابتان می یابید، دارد. شما تمامی این نمادها را به شکل $n \text{ choose } r$ می خوانید.

به عنوان مثال، فرض کنید بلیت هایی برای تئاتر دارید، و می خواهید سه نفر را انتخاب کنید تا به شما ملحق شوند. اگر پنج دوست نزدیک برای انتخاب کردن داشته باشید، به چند روش مختلف می توانید آن سه نفر را انتخاب کنید؟ دوستان شما عبارت از Violet, Wally, Xanthia, Yvonne, Zeke می باشند. شما می توانید این انتخابها را داشته باشید:

{Violet, Wally, Xanthia}

{Violet, Wally, Yvonne}

{Violet, Wally, Zeke}

{Wally, Xanthia, Yvonne}

{Wally, Xanthia, Zeke}

{Xanthia, Yvonne, Zeke}

شما شش زیرمجموعۀ مختلف را یافته اید. آیا همه اش همین است؟ آیا چیزی را فراموش کرده اید؟

شما می توانید کارتان را با فرمول تعداد ترکیبات پنج عضو که در هربار سه تا از آنها گرفته می شوند، درست آزمایی کنید:
$$
\require{cancel}
_5C_3=\frac{5!}{(5-3)!3!}=\frac{5 \cdot \cancel{4}^2 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1}}{ \cancel{2} \cdot 1 \cdot \cancel{3} \cdot \cancel{2} \cdot \cancel{1} }=10
$$
اوه! شما باید برخی از ترکیبات را فراموش کرده باشید.

آموزش قبلی صفحۀ اصلی دوره آموزش بعدی