شمارش، بدون شمردن (فصل 6 ریاضی 1) (علوم تجربی)

شمارش، بدون شمردن — از اصل ضرب تا بسط دوجمله‌ای

فصل ششم ریاضی ۱ ابزارهایی می‌سازد که با آن‌ها می‌شود تعداد حالت‌های ممکن را بدون شمردن یکی‌یکی حساب کرد؛ از دو اصل پایه شروع می‌شود و به جایگشت و ترکیب می‌رسد.

اصل جمع و اصل ضرب

اصل جمع برای کاری که فقط با یکی از چند روش انجام می‌شود: اگر روش اول $m$ راه و روش دوم $n$ راه داشته باشد (و هم‌زمان اتفاق نیفتند)، جمعاً $m+n$ راه هست. اصل ضرب برای کاری که همهٔ مراحلش باید انجام شود: اگر مرحلهٔ اول $m$ راه و مرحلهٔ دوم (برای هر حالت مرحلهٔ اول) $n$ راه داشته باشد، جمعاً $m\times n$ راه هست. کلید تشخیص سریع در کنکور: کلمهٔ «یا» معمولاً اصل جمع و کلمهٔ «و» معمولاً اصل ضرب را نشان می‌دهد.

مثال ترکیبی: مسیر تهران به اصفهان یا با اتومبیل (از قم، با $2\times3=6$ مسیر) یا با قطار (۳ مسیر مستقیم) — چون این دو حالت با هم اتفاق نمی‌افتند، جواب $6+3=9$ است.

ساخت اعداد چندرقمی

اصل مهم: رقم صفر نمی‌تواند در جایگاه با ارزش‌ترین رقم (مثل صدگان) قرار گیرد. برای ارقام $\{0,2,3,7\}$: تعداد اعداد سه‌رقمی $3\times4\times4=48$ است (صدگان ۳ حالت چون صفر نمی‌آید، بقیه هر کدام ۴ حالت). اگر تکرار مجاز نباشد: $3\times3\times2=18$. برای اعداد زوج بدون تکرار، باید یکان $0$ یا $2$ باشد و این دو حالت را جدا حساب کرد و جمع بست — روش تکمیلی هم جواب می‌دهد: $\text{زوج}=\text{کل}-\text{فرد}$.

فاکتوریل و جایگشت

جایگشت کامل یعنی چیدن $n$ شیء متمایز کنار هم: $P(n,n)=n!$. جایگشت ناقص یعنی انتخاب و چیدن $r$ شیء از $n$ شیء (با ترتیب):

مثال: تعداد کلمات سه‌حرفی بدون تکرار از ۷ حرف متمایز، $P(7,3)=7\times6\times5=210$. برای مسائل با قید، الگوریتم کلی این است: جایگاه‌های دارای قید را اول پر کن، سپس بقیه را. قید «کنار هم بودن» چند شیء را به یک واحد تبدیل می‌کند و بعد ترتیب درونی‌شان جدا ضرب می‌شود — مثلاً در کلمهٔ ۸حرفیِ «جهانگردی»، تعداد کلماتی که «جهان» کنار هم باشد برابر $5!\times4!=2880$ است (۵ واحد بیرونی × ۴ ترتیب درونی).

جایگشت با اشیای تکراری (فراتر از کتاب)

اگر از $n$ شیء برخی یکسان باشند:

مثال: کلمات ساخته‌شده از حروف «ماماما» (۳ «م» و ۳ «ا») برابر $\frac{6!}{3!\,3!}=20$ است.

ترکیب

تفاوت اصلی با جایگشت این‌ است که ترتیب مهم نیست:

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

مثال کامل — کمیتهٔ داوران (۴ ایرانی، ۳ ژاپنی، ۲ روسی): برای کمیتهٔ ۵نفره با حداقل ۳ ایرانی، دو حالت (۳ ایرانی یا ۴ ایرانی) جدا حساب و جمع می‌شوند: $\binom43\binom52+\binom44\binom51=40+5=45$. برای «حداقل یک ایرانی» در کمیتهٔ ۵نفره از ۹ نفر، روش تکمیلی سریع‌تر است: $\binom95-\binom55=126-1=125$.

مسائل هندسی با ترکیب

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

بسط دوجمله‌ای (فراتر از کتاب)

جملهٔ $(r+1)$اُم برابر $T_{r+1}=\binom{n}{r}a^{n-r}b^r$ است؛ مثلاً $T_3$ در بسط $(2x-3)^7$ برابر $\binom72(2x)^5(-3)^2=6048x^5$. جایگذاری $a=b=1$ همان فرمول تعداد زیرمجموعه‌ها را می‌دهد ($2^n$)، و جایگذاری $a=1,b=-1$ نتیجهٔ جالب $\sum(-1)^r\binom{n}{r}=0$ را می‌سازد.

جایگشت دوری و اصل شمول-طرد (فراتر از کتاب)

برای چیدن $n$ شیء دور یک میز (که چرخش‌ها یکسان حساب می‌شوند): $(n-1)!$؛ اگر آینه هم یکسان باشد (مثل گردنبند)، $\frac{(n-1)!}{2}$. اصل شمول و طرد برای دو یا سه مجموعه در مسائل شمارش کاربرد دارد:

نکات کنکوری و دام‌های رایج: قید «کنار هم نباشند» با روش فاصله حل می‌شود — ابتدا بقیهٔ اشیاء را می‌چینیم ($(n-k)!$ حالت)، سپس $k$ شیء ممنوع را در فاصله‌های ایجادشده ($n-k+1$ فاصله) قرار می‌دهیم. دام رایج دیگر این است که $6!\ne3!\times2!$ و $6!\ne3!+3!$ — این دو تساوی همیشه غلط‌اند و نباید فاکتوریل را جمع یا ضرب اجزا فرض کرد. و برای تشخیص سریع نوع مسئله: ساخت کلمه یا رمز معمولاً جایگشت است، انتخاب تیم یا کمیته معمولاً ترکیب.

ترکیب اصل جمع و ضرب در یک مسئله

بسیاری از مسائل واقعی هر دو اصل را همزمان لازم دارند. مثال رمز سه‌حرفی: رمزی از ۳ حرف که هر حرف یا فارسی (۳۲ حرف) یا انگلیسی (۲۶ حرف) است، با شرط این‌که حروف کنار هم از یک زبان نباشند. دو الگو ممکن است: فارسی‑انگلیسی‑فارسی ($32\times26\times32=26624$) یا انگلیسی‑فارسی‑انگلیسی ($26\times32\times26=21632$). چون این دو الگو با هم اتفاق نمی‌افتند، طبق اصل جمع جواب نهایی $26624+21632=48256$ می‌شود — نمونه‌ای که نشان می‌دهد اول باید حالت‌های جدا از هم را با اصل جمع کنار هم گذاشت و داخل هر حالت از اصل ضرب استفاده کرد.

جایگشت با قیدهای متعدد

وقتی چند جایگاه هم‌زمان شرط دارند، باید جایگاه‌های مقیّد را جداگانه و اول از همه پر کرد. مثال: چند عدد ۴رقمی از ارقام $\{1,2,3,4,5,6\}$ بدون تکرار وجود دارد که رقم اول زوج و رقم آخر فرد باشد؟ رقم اول از $\{2,4,6\}$ سه حالت، رقم آخر از $\{1,3,5\}$ سه حالت، و دو رقم میانی از ۴ رقم باقی‌مانده $4\times3=12$ حالت — در مجموع $3\times3\times12=108$.

برای کلمهٔ ۸حرفیِ «جهانگردی» (۸ حرف متمایز) چند نمونهٔ دیگر از تکنیک قید: کلماتی که به «ی» ختم شوند فقط ۷ حرف باقی‌مانده را می‌چینند ($7!=5040$)؛ کلماتی که «د» و «ی» کنار هم باشند، این دو حرف را یک واحد با دو ترتیب داخلی حساب می‌کنند ($2\times7!=10080$)؛ و کلماتی که با یکی از حروف نقطه‌دار («ج»، «ن»، «گ»، «ی» — ۴ حرف) شروع شوند، $4\times7!=20160$ حالت دارند.

دست‌دادن، زیرمجموعه‌ها و تقسیم گروهی (فراتر از کتاب)

اگر در گروهی $n$نفره همه با همه دست بدهند، تعداد دست‌دادن‌ها $\binom{n}{2}=\frac{n(n-1)}{2}$ است؛ برای ۱۰ نفر، $\binom{10}{2}=45$. برای زیرمجموعه‌های یک مجموعهٔ $n$عضوی:

تقسیم $n$ شیء به گروه‌های $k_1,k_2,\ldots,k_m$ نفره از فرمول $\dfrac{n!}{k_1!\,k_2!\cdots k_m!}$ به دست می‌آید؛ مثلاً تقسیم ۱۰ نفر به سه گروه ۳، ۳ و ۴نفره برابر $\frac{10!}{3!\,3!\,4!}=4200$ راه دارد. ترکیب با تکرار هم فرمول جداگانه‌ای دارد: انتخاب $r$ شیء از $n$ نوع با امکان تکرار، $\binom{n+r-1}{r}$ حالت دارد — مثلاً خرید ۳ نوشابه از ۵ طعم مختلف، $\binom{7}{3}=35$ راه.

مسیرهای شبکه‌ای (فراتر از کتاب، کنکوری)

در یک شبکهٔ مستطیلی $m\times n$، تعداد کوتاه‌ترین مسیرها از گوشهٔ پایین‌چپ به گوشهٔ بالا‑راست (فقط حرکت رو به بالا یا راست) برابر $\binom{m+n}{m}$ است؛ در شبکهٔ $3\times4$، این عدد $\binom{7}{3}=35$ می‌شود — چون هر مسیر ترکیبی از ۳ حرکت بالا و ۴ حرکت راست است که فقط ترتیب چیدنشان مهم است، نه هویتشان.

نکات کنکوری تکمیلی: برای معادلات فاکتوریلی، سه الگو رایج است: $n!=k\times(n-1)!\Rightarrow n=k$؛ $\frac{n!}{(n-2)!}=k\Rightarrow n(n-1)=k$؛ و $\binom{n}{r}=\binom{n}{s}\Rightarrow r=s$ یا $r+s=n$. و برای هر مسئله‌ای که کلمهٔ «حداقل» در آن دیده می‌شود، روش تکمیلی (کل منهای ناخواسته) معمولاً کوتاه‌ترین راه است، نه شمردن مستقیم هر حالت.