جایگشت و ترکیب به زبان ساده

اصل اساسی شمارش

مسئله‌های شمارش می‌پرسند چیزی به چند راه می‌تواند رخ دهد. پایهٔ کار اصل اساسی شمارش است: اگر یک انتخاب به $m$ راه و انتخاب دوم و مستقل به $n$ راه انجام شود، هر دو با هم به $m \times n$ راه انجام می‌شوند. این ایده به هر تعداد مرحله گسترش می‌یابد.

اگر 3 پیراهن، 4 شلوار و 2 جفت کفش داشته باشید، می‌توانید $3 \times 4 \times 2 = 24$ ترکیب لباس متفاوت بسازید. رمز چهاررقمی با رقم‌های 0 تا 9، با مجاز بودن تکرار، $10 \times 10 \times 10 \times 10 = 10^4 = 10{,}000$ حالت دارد. هر فرمول این مقاله میان‌بُری برای همین ضرب است، پس وقتی مسئله‌ای ناآشنا به نظر می‌رسد، برگشتن به شمارش مرحله‌به‌مرحله همیشه راه مطمئنی است.

فاکتوریل

برای چیدن همهٔ $n$ شیء متمایز در یک ردیف، برای جایگاه اول $n$ انتخاب، برای دوم $n - 1$ انتخاب و به همین ترتیب تا 1 داریم. این حاصل‌ضرب را $n$ فاکتوریل می‌نامند:

پس $5! = 120$: پنج کتاب را می‌توان به 120 ترتیب روی قفسه چید. طبق تعریف $0! = 1$ که فرمول‌های بعدی را سازگار نگه می‌دارد، چون برای چیدن هیچ‌چیز دقیقاً یک راه وجود دارد. فاکتوریل‌ها به‌طرز شگفت‌انگیزی سریع رشد می‌کنند: $10! = 3{,}628{,}800$ و یک دستهٔ ورق برزده $52!$ ترتیب ممکن دارد، عددی با 68 رقم.

جایگشت: ترتیب مهم است

جایگشت چیدمانی مرتب از $r$ شیء است که از میان $n$ شیء متمایز انتخاب شده‌اند. چون ترتیب مهم است، اول-دوم-سوم با سوم-دوم-اول فرق دارد. تعداد جایگشت‌ها برابر است با

نشاندن افراد دور میز گرد حالت خاصی است. جابه‌جا کردن همه به اندازهٔ یک صندلی همان چیدمان را می‌دهد، پس $n$ نفر به $(n-1)!$ راه متمایز می‌نشینند. شش نفر دور میز گرد $5! = 120$ چیدمان دارند، نه 720.

ترکیب: ترتیب مهم نیست

ترکیب انتخابی است که در آن فقط عضویت اهمیت دارد. انتخاب آنا، بن و کارا برای یک کمیته، با هر ترتیبی، همان کمیته است. هر گروه $r$تایی با $r!$ جایگشت متناظر است، پس آن را تقسیم می‌کنیم:

ترکیب‌ها متقارن‌اند: $\binom{n}{r} = \binom{n}{n-r}$، چون انتخاب 3 نفر برای حضور همان انتخاب 5 نفر برای کنار گذاشتن است. همچنین درایه‌های مثلث پاسکال و ضریب‌های بسط دوجمله‌ای $(a + b)^n$ هستند.

چطور بفهمیم کدام را به کار ببریم

فقط یک پرسش بپرسید: اگر دو مورد از انتخاب‌شده‌ها را جابه‌جا کنم، نتیجهٔ متفاوتی می‌گیرم؟ اگر بله، ترتیب مهم است و به جایگشت نیاز دارید. اگر نه، از ترکیب استفاده کنید.

• جایگاه‌ها، رتبه‌بندی‌ها، گذرواژه‌ها، نقشهٔ نشستن و برنامهٔ زمانی: جایگشت.
• تیم‌ها، کمیته‌ها، دست‌های ورق، بلیت‌های بخت‌آزمایی و مواد روی پیتزا: ترکیب.
• نقش‌ها درون یک گروه، مانند رئیس و خزانه‌دار، ترتیب را مهم می‌کنند، هرچند افراد از یک مجموعه انتخاب می‌شوند.

یک وارسی سریع: تعداد جایگشت‌ها همیشه $r!$ برابر تعداد ترکیب‌هاست. اگر دو جوابتان در این رابطه صدق نمی‌کنند، یکی از آن‌ها اشتباه است.

شمارش با تکرار و حروف تکراری

وقتی استفادهٔ دوباره از موردها مجاز است، فرمول‌ها تغییر می‌کنند. تعداد انتخاب‌های مرتب با تکرار $n^r$ است، مانند مثال رمز. تعداد انتخاب‌های نامرتب با تکرار، مانند انتخاب 3 اسکوپ بستنی از 5 طعم که می‌توانید طعمی را تکرار کنید، برابر است با

چیدن حروف با تکرار یک اصلاح دیگر لازم دارد: بر فاکتوریل تعداد هر حرف تکراری تقسیم کنید، چون جابه‌جا کردن حروف یکسان چیزی را عوض نمی‌کند. نام رود میسی‌سی‌پی در املای انگلیسی‌اش 11 حرف دارد که در آن حرف I 4 بار، حرف S 4 بار و حرف P 2 بار آمده است، پس $\frac{11!}{4!\,4!\,2!} = 34{,}650$ چیدمان متمایز دارد.

استفاده از شمارش برای یافتن احتمال

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

بازی‌های ورق تمرین بیشتری فراهم می‌کنند. $\binom{52}{5} = 2{,}598{,}960$ دست پنج‌کارتی ممکن وجود دارد. دستی که هر چهار آس را دارد فقط به یک کارت دیگر نیاز دارد که از 48 کارت دیگر انتخاب می‌شود، پس احتمالش $\frac{48}{2{,}598{,}960} = \frac{1}{54{,}145}$ است.

اشتباه‌های رایج

• استفاده از جایگشت برای تیم یا کمیته، که با ضریب $r!$ بیش‌شماری می‌کند.
• فراموش کردن اینکه $0! = 1$، که فرمول‌هایی مانند $\binom{n}{n}$ را خراب می‌کند.
• نادیده گرفتن موردهای یکسان، مانند چیدمان حروف تکراری.
• ضرب کردن مرحله‌هایی که مستقل نیستند بدون اصلاح تعدادهای بعدی.

ماشین‌حساب جایگشت و ترکیب مقدار ${}_nP_r$ و ${}_nC_r$ را همراه با گام‌های فاکتوریل حساب می‌کند و ماشین‌حساب احتمال این تعدادها را به احتمال تبدیل می‌کند.

مثلث پاسکال و زیرمجموعه‌ها

هر درایهٔ مثلث پاسکال مجموع دو درایهٔ بالای آن است و سطر $n$ مقدارهای $\binom{n}{0}, \binom{n}{1}, \ldots, \binom{n}{n}$ را فهرست می‌کند. سطر 4 به صورت 1، 4، 6، 4، 1 است که دقیقاً ضریب‌های $(a + b)^4 = a^4 + 4a^3b + 6a^2b^2 + 4ab^3 + b^4$ هستند. قاعده‌ای که مثلث را می‌سازد خودش یک واقعیت شمارشی است:

برای دیدن دلیلش، یک مورد مشخص را ثابت بگیرید. هر انتخاب $r$ مورد یا آن را شامل می‌شود و $r - 1$ مورد باید از $n - 1$ مورد دیگر انتخاب شود، یا آن را کنار می‌گذارد و هر $r$ مورد باید از $n - 1$ مورد دیگر انتخاب شود. جمع یک سطر کامل $2^n$ می‌شود، یعنی تعداد کل زیرمجموعه‌های یک مجموعهٔ $n$عضوی، چون هر عضو یا درون است یا بیرون. بنابراین پیتزافروشی‌ای با 8 نوع افزودنی می‌تواند $2^8 = 256$ پیتزای متفاوت بسازد، اگر پیتزای ساده را هم بشماریم.

تمرین‌ها

1. 4 کتاب از 7 کتاب متفاوت را به چند راه می‌توان روی قفسه چید؟ جواب: ${}_7P_4 = 7 \times 6 \times 5 \times 4 = 840$.
2. 4 افزودنی را از میان 10 افزودنی به چند راه می‌توان انتخاب کرد؟ جواب: $\binom{10}{4} = 210$.
3. حروف A، A، A، N، N و B چند چیدمان متمایز دارند؟ جواب: $\frac{6!}{3!\,2!} = 60$.
4. اگر تکرار مجاز باشد، با 26 حرف چند کد پنج‌حرفی می‌توان ساخت؟ جواب: $26^5 = 11{,}881{,}376$.

پرسش‌های متداول