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

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

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

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

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

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

مثالِ روشن: اگر از تهران به قم ۲ مسیر و از قم به اصفهان ۳ مسیر باشد، کلِ مسیرها $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$ صفر است، نه عددی مثبت.

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