فصل ششم: شمارش، بدون شمردن

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

اصل جمع: اگر کاری به دو روش قابل انجام باشد (روش اول $m$ انتخاب، روش دوم $n$ انتخاب) و این دو روش همزمان اتفاق نیفتند (یا این یا آن)، تعداد کل روش‌ها $\boxed{m_1+m_2+\cdots+m_k}$ است. مثال: امین می‌خواهد دوستش را به رستوران (۲ نوع غذا) یا آبمیوه‌فروشی (۳ نوع) دعوت کند: $2+3=5$ انتخاب.

اصل ضرب: اگر کاری شامل چند مرحله باشد که همهٔ آن‌ها باید انجام شوند (مرحلهٔ اول $m$ روش، مرحلهٔ دوم برای هر حالت مرحلهٔ اول $n$ روش)، تعداد کل $\boxed{m_1\times m_2\times\cdots\times m_k}$ است. مثال: سفر تهران به اصفهان از طریق قم با ۲ مسیر تا قم و ۳ مسیر از قم به اصفهان: $2\times3=6$ مسیر.

نکتهٔ کنکوری: کلمهٔ «یا» معمولاً اصل جمع، کلمهٔ «و» معمولاً اصل ضرب را نشان می‌دهد.

ترکیب دو اصل (مثال): اگر همان مسیر تهران-اصفهان با اتومبیل (از قم) یا با قطار طی شود: با اتومبیل $2\times3=6$ مسیر، با قطار مستقیم $3$ مسیر؛ چون «یا» است، جمع می‌بندیم: $6+3=9$. مثال پیشرفته‌تر — رمز سه‌حرفی از حروف فارسی (۳۲تایی) یا انگلیسی (۲۶تایی) که حروف کنار هم از یک زبان نباشند: حالت فارسی-انگلیسی-فارسی $=32\times26\times32=26624$ و حالت انگلیسی-فارسی-انگلیسی $=26\times32\times26=21632$؛ با اصل جمع، پاسخ $=48256$.

مسائل ساخت عدد (روش جایگاهی): هر رقم یک جایگاه است و رقم صفر نمی‌تواند در جایگاه صدگان (سمت چپ) بیاید. مثال کامل با ارقام $\{0,2,3,7\}$: تعداد اعداد سه‌رقمی $=3\times4\times4=48$ (صدگان ۳ حالت چون صفر مجاز نیست)؛ بدون تکرار رقم: $3\times3\times2=18$؛ اعداد فرد بدون تکرار: یکان باید ۳ یا ۷ باشد $\Rightarrow2\times2\times2=8$؛ اعداد زوج بدون تکرار (یکان ۰ یا ۲، باید دو حالت جدا بررسی شود) $=4+6=10$. روش تکمیلی: جواب زوج $=$ جواب کل $-$ جواب فرد $=18-8=10$ ✓.

جایگشت

فاکتوریل: $\boxed{n!=n\times(n-1)\times\cdots\times2\times1}$ با قرارداد $0!=1$؛ و $\dfrac{n!}{(n-r)!}=n(n-1)\cdots(n-r+1)$.

جایگشت کامل ($n$ از $n$): تعداد چیدن $n$ شیء متمایز: $\boxed{P(n,n)=n!}$ (با اصل ضرب: جایگاه اول $n$ انتخاب، دوم $n-1$، ...، آخر $1$).

جایگشت ناقص ($r$ از $n$): انتخاب و چیدن $r$ شیء از $n$ شیء با رعایت ترتیب:

مثال: کلمات سه‌حرفی از ۷ حرف متمایز بدون تکرار: $P(7,3)=7\times6\times5=210$.

مسائل با قید (مثال کامل — کلمهٔ «جهانگردی»، ۸ حرف متمایز): کلمات بدون تکرار: $8!=40320$؛ ختم به «ی»: هفت حرف باقی را می‌چینیم، $7!=5040$؛ کنار هم بودن «د» و «ی»: این دو را یک واحد می‌گیریم با دو ترتیب داخلی، $2\times7!=10080$؛ چهار حرف اول «جهان» و چهار حرف آخر «گردی» به‌ترتیب دلخواه: $4!\times4!=576$؛ کنار هم بودن «جهان» (به‌عنوان یک واحد از ۵ شیء): $5!\times4!=2880$.

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

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

مثال: کلمات با حروف «ماماما» (۳ «م» و ۳ «ا»): $\dfrac{6!}{3!3!}=20$.

جایگشت دوری (فراتر از کتاب): نشستن $n$ نفر دور یک میز که چرخش‌ها یکسان‌اند: $\boxed{(n-1)!}$؛ اگر آینه هم یکسان باشد (گردنبند): $\dfrac{(n-1)!}{2}$.

جدول مقایسهٔ سریع:

ترکیب

تفاوت با جایگشت: در ترکیب ترتیب اهمیت ندارد. تعریف:

خواص: تقارن $\boxed{\binom nr=\binom{n}{n-r}}$؛ هویت پاسکال $\boxed{\binom nr=\binom{n-1}{r-1}+\binom{n-1}{r}}$ (که مثلث پاسکال از آن ساخته می‌شود: هر عدد مجموع دو عدد بالای خودش است)؛ و $\sum_{r=0}^n\binom nr=2^n$ (تعداد کل زیرمجموعه‌های یک مجموعهٔ $n$عضوی).

مثال کامل — کمیتهٔ داوران (۴ ایرانی، ۳ ژاپنی، ۲ روسی، جمعاً ۹ نفر): کمیتهٔ ۴نفره از همه: $\binom94=126$؛ از هر کشور یک نفر: $\binom41\binom31\binom21=24$؛ دقیقاً ۲ ایرانی در کمیتهٔ ۵نفره: $\binom42\times\binom53=6\times10=60$؛ حداقل ۳ ایرانی در کمیتهٔ ۵نفره (حالت ۳ ایرانی + حالت ۴ ایرانی): $\binom43\binom52+\binom44\binom51=40+5=45$؛ حداقل یک ایرانی (روش تکمیلی): $\binom95-\binom55=126-1=125$.

مسائل ترکیب با قید: عضو خاص حتماً باشد: $\binom{n-1}{r-1}$؛ عضو خاص نباشد: $\binom{n-1}{r}$؛ حداقل یکی از گروه خاص (روش تکمیلی): $\binom nr-\binom{n-k}{r}$.

کاربردهای هندسی: تعداد مثلث از $n$ نقطه (هیچ سه‌تایی هم‌خط نباشند): $\binom n3$؛ تعداد قطرهای چندضلعی $n$ضلعی: $\dfrac{n(n-3)}2$.

بسط دوجمله‌ای (کنکور):

جملهٔ $(r+1)$اُم: $T_{r+1}=\binom nr a^{n-r}b^r$. مثال: جملهٔ سوم بسط $(2x-3)^7$: $\binom72(2x)^5(-3)^2=6048x^5$.

ترکیب با تکرار (فراتر از کتاب): انتخاب $r$ شیء از $n$ نوع با امکان تکرار: $\boxed{\binom{n+r-1}{r}}$؛ مثال: خرید ۳ نوشابه از ۵ طعم: $\binom73=35$.

تقسیم‌بندی به گروه‌ها: تقسیم $n$ شیء به گروه‌های $k_1,\ldots,k_m$: $\dfrac{n!}{k_1!\cdots k_m!}$؛ مثال: تقسیم ۱۰ نفر به گروه‌های ۳،۳،۴: $\dfrac{10!}{3!3!4!}=4200$.

اصل شمول و طرد (فراتر از کتاب): برای دو مجموعه $|A\cup B|=|A|+|B|-|A\cap B|$؛ برای سه مجموعه:

تعداد زیرمجموعه‌ها: برای مجموعهٔ $n$عضوی — زیرمجموعه‌های $r$عضوی: $\binom nr$؛ کل زیرمجموعه‌ها: $2^n$؛ زیرمجموعه‌های غیرتهی: $2^n-1$.

هویت‌های دوجمله‌ای مهم: $\binom nr+\binom n{r+1}=\binom{n+1}{r+1}$ و $\binom n0+\binom n2+\binom n4+\cdots=2^{n-1}$.

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

نکات کنکوری جامع

تشخیص نوع مسئله: سؤال کلیدی «آیا ترتیب مهم است؟» — ترتیب مهم $\Rightarrow$ جایگشت؛ ترتیب مهم نیست $\Rightarrow$ ترکیب. ساخت کلمه/رمز/ترتیب مسابقه = جایگشت؛ انتخاب تیم/کمیته = ترکیب.

روش تکمیلی: برای «حداقل یک» یا «حداقل...» همیشه: $\text{خواسته}=\text{کل}-\text{ناخواسته}$.

دام‌های رایج: فراموش‌کردن ممنوعیت صفر در صدگان؛ اشتباه در «حداقل» (باید تکمیلی زد)؛ در قید «کنار هم» فراموش‌کردن به‌روزرسانی تعداد شیءها پس از یکی‌کردن؛ $6!\neq3!\times2!$ و $6!\neq3!+3!$؛ و $\binom nr$ برای $r>n$ صفر یا تعریف‌نشده است.

قانون دست‌دادن (فراتر از کتاب): در گروه $n$نفره که همه با هم دست می‌دهند: $\binom n2=\dfrac{n(n-1)}2$.