شمارش، جایگشت و ترکیب (ریاضی ۱)

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

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

اصل جمع: اگر کاری به دو روش قابل انجام باشد (روش اول $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$ادامهٔ فرمول را افقی ببینبزرگ‌نمایی.