اصل شمارش، جایگشت و ترکیب (هنر)

شمارش، بدون شمردن (هنر)

پرسشی که طراح‌ها زیاد می‌پرسند

با ۵ رنگ و ۳ نوار در یک پوستر، چند ترکیب‌بندیِ متفاوت می‌شود ساخت؟ با ۸ حرف چند کلمه؟ برای یک قفلِ رمزی چند رمز؟ شمردنِ یکی‌یکی زود از دست می‌رود، پس دو اصلِ ساده را جایش می‌گذاریم.

اصلِ جمع — وقتی کار فقط با یکی از راه‌ها انجام می‌شود («یا این یا آن»):

اصلِ ضرب — وقتی کار از چند مرحله ساخته شده و همهٔ مرحله‌ها باید انجام شوند («هم این و هم آن»):

مثالِ روشن: اگر از تهران به قم ۲ مسیر و از قم به اصفهان ۳ مسیر باشد، کلِ مسیرها $2 \times 3 = 6$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است؛ اما اگر بخواهید دوستتان را به رستوران یا آبمیوه‌فروشی ببرید و اولی ۲ گزینه و دومی ۳ گزینه داشته باشد، $2+3=5$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی انتخاب دارید.

کلمهٔ «یا» معمولاً نشانهٔ جمع است و کلمهٔ «و» نشانهٔ ضرب. اما هر دو اصل اغلب با هم لازم می‌شوند: مثلاً اگر همان سفر را با اتومبیل (۶ مسیر) یا قطار (۳ مسیر) بروید، $6+3=9$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

ساختنِ عدد: هر رقم یک جایگاه

نمونهٔ کامل با ارقامِ $\{0,2,3,7\}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی:

الف) چند عددِ سه‌رقمی می‌توان ساخت؟ صدگان نمی‌تواند صفر باشد، پس $3 \times 4 \times 4 = 48$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

ب) با ارقامِ غیرتکراری؟ $3 \times 3 \times 2 = 18$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

پ) سه‌رقمیِ فردِ غیرتکراری؟ یکان باید $3$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی یا $7$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی باشد ($2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی حالت)، بعد صدگان $2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و دهگان $2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی حالت: $2 \times 2 \times 2 = 8$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

ت) سه‌رقمیِ زوجِ غیرتکراری؟ اینجا باید دو حالت را جدا کرد. اگر یکان $=2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی: صدگان ۲ حالت و دهگان ۲ حالت، یعنی $4$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. اگر یکان $=0$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی: صدگان ۳ و دهگان ۲ حالت، یعنی $6$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. جمعاً $10$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. (کنترل: $18-8=10$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی ✓)

قاعدهٔ طلایی: جایگاهی که قید دارد را اول پر کنید. و همیشه صفر را در جایگاهِ پرارزش جداگانه بررسی کنید.

روشِ تکمیلی: خیلی وقت‌ها شمردنِ موارد ناخواسته آسان‌تر است: خواسته = کل $-$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی ناخواسته. هر جا «حداقل یکی» دیدید، اول به این فکر کنید.

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

به هر حالتِ چیدنِ چند شیءِ متمایز کنارِ هم، یک جایگشت می‌گوییم. ابزارش فاکتوریل است:

چیدنِ همهٔ $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شیء: $P(n,n) = n!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. چیدنِ فقط $r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا از $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا:

مثلاً تعدادِ کلمه‌های سه‌حرفی از ۷ حرفِ متمایز: $P(7,3) = 7 \times 6 \times 5 = 210$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

قیدهای پرتکرار — با کلمهٔ «جهانگردی» (۸ حرفِ متمایز):

• کلِ کلمه‌های ۸ حرفی: $8! = 40320$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی
• کلمه‌هایی که به «ی» ختم شوند: حرفِ آخر ثابت است، پس $7! = 5040$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی
• کلمه‌هایی که «د» و «ی» کنارِ هم باشند: آن دو را یک واحد بگیرید ($7$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شیء) و درونشان هم دو ترتیب دارید: $2 \times 7! = 10080$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی
• کلمه‌هایی که «جهان» کنارِ هم بیاید: چهار حرف یک واحد می‌شود، پس $5$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی شیء داریم و درونِ واحد هم $4!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی حالت: $5! \times 4! = 2880$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی
• کلمه‌هایی که با حرفِ نقطه‌دار شروع شوند: حروفِ نقطه‌دار «ج، ن، گ، ی» چهار تا هستند: $4 \times 7! = 20160$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی

پس دو قاعده:

«کنارِ هم»: شیءهای چسبیده را یک واحد بگیرید، تعداد را به‌روز کنید، و درونِ واحد را جداگانه بچینید.
«کنارِ هم نباشند»: اول بقیه را بچینید ($(n-k)!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی)، بعد شیءهای ممنوع را در فاصله‌های ایجادشده جای دهید ($n-k+1$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی فاصله، شاملِ ابتدا و انتها).

اگر بعضی از اشیاء یکسان باشند، باید تکرارها را خنثی کرد:

مثلاً با ۳ حرفِ «م» و ۳ حرفِ «ا»، تعدادِ چیدمان‌های متمایز $\frac{6!}{3!\,3!} = 20$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.

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

انتخابِ سه رنگ برای یک پالت، انتخابِ اعضای یک گروه، یا انتخابِ سه نقطه برای ساختنِ یک مثلث — در همهٔ این‌ها «الف و ب و پ» با «پ و ب و الف» یکی است.

منطقش این است که هر ترکیبِ $r$ادامهٔ فرمول را افقی ببینبزرگ‌نماییتایی، $r!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی جایگشت می‌سازد، پس $\binom{n}{r} = \frac{P(n,r)}{r!}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

خواصِ لازم:

تقارن از این می‌آید که انتخابِ $r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا، همان کنار گذاشتنِ $n-r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تاست. رابطهٔ دوم (پاسکال) هم شهودِ ساده‌ای دارد: یک عضوِ خاص یا در انتخاب هست ($\binom{n-1}{r-1}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی) یا نیست ($\binom{n-1}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی). همین دو، مثلثِ پاسکال را می‌سازند که هر عدد جمعِ دو عددِ بالای خودش است.

سه الگویِ قیددار:

• عضوِ خاص حتماً باشد: $\binom{n-1}{r-1}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی
• عضوِ خاص نباشد: $\binom{n-1}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی
• حداقل یکی از گروهی $k$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نفره باشد: $\binom{n}{r} - \binom{n-k}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی

نمونهٔ کامل — کمیتهٔ داوران. از ۴ داورِ ایرانی، ۳ ژاپنی و ۲ روسی (جمعاً ۹ نفر):

کمیتهٔ ۴ نفره از میانِ همه: $\binom{9}{4} = 126$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

کمیتهٔ ۳ نفره با یک نفر از هر کشور: $\binom{4}{1}\binom{3}{1}\binom{2}{1} = 24$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

کمیتهٔ ۵ نفره با دقیقاً ۲ ایرانی: $2$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نفر از ۴ ایرانی و $3$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نفر از ۵ غیرایرانی، یعنی $\binom{4}{2}\binom{5}{3} = 6 \times 10 = 60$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

کمیتهٔ ۵ نفره با حداقل ۳ ایرانی: حالتِ ۳ ایرانی $\binom{4}{3}\binom{5}{2} = 40$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و حالتِ ۴ ایرانی $\binom{4}{4}\binom{5}{1} = 5$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی؛ جمعاً $45$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

ترکیب در هندسه

از $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نقطه که هیچ سه‌تایشان هم‌خط نیستند:

اگر $k$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا از آن نقطه‌ها هم‌خط باشند، آن $\binom{k}{3}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی حالت مثلث نمی‌سازند و باید کم شوند. تعدادِ قطرهای یک $n$ادامهٔ فرمول را افقی ببینبزرگ‌نماییضلعی هم $\frac{n(n-3)}{2}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است، یعنی همهٔ پاره‌خط‌های ممکن منهای خودِ ضلع‌ها: $\binom{n}{2} - n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

دو کاربردِ دمِ دستیِ دیگر: در جمعی $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نفره اگر همه با هم دست بدهند $\binom{n}{2}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی دست‌دادن رخ می‌دهد، و در یک شبکهٔ $m \times n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تعدادِ کوتاه‌ترین مسیرها از گوشه‌ای به گوشهٔ روبه‌رو $\binom{m+n}{m}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.

چند فرمولِ تکمیلی

• جایگشتِ دوری (چیدنِ $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نفر دورِ میز، که چرخش‌ها یکی حساب می‌شوند): $(n-1)!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی. اگر آینه هم فرقی نکند (مثلِ گردنبند): $\frac{(n-1)!}{2}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.
• ترکیب با تکرار (انتخابِ $r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا از $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی نوع، با اجازهٔ تکرار): $\binom{n+r-1}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.
• بسطِ دوجمله‌ای: $(a+b)^n = \sum_{r=0}^{n}\binom{n}{r}a^{n-r}b^r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی و جملهٔ $(r+1)$ادامهٔ فرمول را افقی ببینبزرگ‌نماییام برابرِ $\binom{n}{r}a^{n-r}b^r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی است.
• رابطهٔ پل بینِ دو مفهوم: $P(n,r) = r! \cdot \binom{n}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.

تعدادِ زیرمجموعه‌ها

برای مجموعه‌ای $n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی عضوی: زیرمجموعه‌های $r$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی عضوی $\binom{n}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا هستند، کلِ زیرمجموعه‌ها $2^n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا، و زیرمجموعه‌های غیرتهی $2^n - 1$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی تا. همین $2^n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی از این می‌آید که هر عضو دو سرنوشت دارد: یا در زیرمجموعه هست یا نیست.

دام‌های رایج

• فراموش‌کردنِ صفر در جایگاهِ پرارزشِ عدد.
• در «کنارِ هم»، به‌روز نکردنِ تعدادِ شیءها بعد از یکی‌کردن.
• استفاده از اصلِ ضرب بدونِ تقسیم بر $r!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی جایی که ترتیب اهمیت ندارد — همان‌جا جایگشت به‌جای ترکیب می‌نشیند.
• تساوی‌های نادرستی مثلِ $6! = 3! \times 2!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی یا $6! = 3! + 3!$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.
• $\binom{n}{r}$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی برای $r>n$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی صفر است، نه عددی مثبت.

پرسشِ اولی که باید بپرسید: آیا جابه‌جا کردنِ دو عضو، حالتِ جدیدی می‌سازد؟ اگر بله، جایگشت؛ اگر نه، ترکیب. کلمه‌سازی و رمز و ترتیبِ مسابقه جایگشت‌اند؛ انتخابِ تیم و کمیته و زیرمجموعه ترکیب.