اصل شمارش با تقسیمبندی حالتها: تفکیک و جمعآوری هوشمندانه
مفهوم اصلی: شمارش از طریق دستهبندی (اصل جمع)
فرض کنید میخواهید برای مهمانی لباسی انتخاب کنید. کمد شما شامل 3 تیشرت و 2 پیراهن است. واضح است که تعداد کل انتخابهای شما 3+2=5 گزینه است. این سادهترین شکل «اصل جمع» است. اما در مسائل دنیای واقعی، دستهبندیها پیچیدهتر و ظریفتر هستند. اصل جمع (قانون جمع) [2] میگوید: اگر بخواهیم تعداد کل راههای انجام یک کار را محاسبه کنیم و این کار به چند حالت مجزا (که هیچ اشتراکی با هم ندارند) قابل تقسیم باشد، آنگاه تعداد کل راهها برابر است با مجموع تعداد راههای هر یک از این حالتها. شرط اصلی «مجزا بودن» یا «نااشتراک» بودن حالتهاست. یعنی یک حالت نباید در دو دستهٔ متفاوت شمرده شود.گامهای طلایی در حل مسائل به روش حالتبندی
برای استفاده از این روش، یک نقشهٔ راه ساده اما مؤثر وجود دارد:- گام اولتشخیص معیار دستهبندی: به مسئله نگاه کنید و ببینید بر اساس چه ویژگیای میتوان تمام حالتهای ممکن را به چند گروه تقسیم کرد. این معیار باید طوری انتخاب شود که حالتهای هر گروه درون خودشان شبیه باشند و بین گروهها هیچ حالت مشترکی وجود نداشته باشد.
- گام دومشمارش درون هر گروه: برای هر کدام از حالتهایی که تعریف کردیم، تعداد اعضای آن گروه را با استفاده از روشهای ساده شمارش (مثل اصل ضرب) محاسبه کنید.
- گام سومجمعبندی نتایج: اعداد بهدستآمده از همهٔ گروهها را با هم جمع کنید. حاصل، پاسخ نهایی مسئله است.
گام اول: کتابهای ریاضی را یک مجموعه و کتابهای فیزیک را یک مجموعه در نظر میگیریم. این دو مجموعه میتوانند در قفسه به 2 صورت قرار گیرند: (ریاضی، فیزیک) یا (فیزیک، ریاضی).
گام دوم: در هر کدام از این 2 حالت، کتابهای ریاضی به 3! حالت و کتابهای فیزیک به 2! حالت جابهجا میشوند. پس تعداد حالتها در هر گروه اصلی برابر است با (3! × 2!).
گام سوم: مجموع کل حالتها: 2 × (3! × 2!) = 2 × (6 × 2) = 24.
کاربرد عملی: شمارش اعداد با شرایط خاص
یکی از رایجترین کاربردهای این روش، در مسئله «شمارش اعداد با شرایط خاص» است. به مثال زیر توجه کنید: مسئله: از بین اعداد 3 رقمی (از 100 تا 999)، چند عدد وجود دارد که حداقل یک بار رقم 5 در آن دیده شود؟ راهحل مستقیم: میتوانیم اعداد را بر اساس محل قرارگیری رقم 5 دستهبندی کنیم.- حالت اول (رقم ۵ در صدگان): رقم صدگان 5 است. رقم دهگان و یکان میتوانند هر رقمی از 0 تا 9 باشند (به جز حالتی که هر دو رقم دیگر هم 5 باشند که اشکالی ندارد). تعداد این اعداد: 1 × 10 × 10 = 100 عدد.
- حالت دوم (رقم ۵ در دهگان، ولی صدگان ۵ نباشد): رقم دهگان 5 است. رقم صدگان میتواند 1 تا 9 باشد به جز 5 (چون حالت اول حساب شد) یعنی 8 حالت. رقم یکان هر رقمی از 0 تا 9 میتواند باشد. تعداد: 8 × 1 × 10 = 80 عدد.
- حالت سوم (رقم ۵ در یکان، ولی در صدگان و دهگان ۵ نباشد): رقم یکان 5 است. رقم صدگان میتواند 1 تا 9 باشد به جز 5 (8 حالت) و رقم دهگان میتواند 0 تا 9 باشد به جز 5 (9 حالت). تعداد: 8 × 9 × 1 = 72 عدد.
مقایسه روشها: مستقیم در مقابل حالتبندی
برای درک بهتر قدرت این روش، آن را با روش «شمارش مکمل» مقایسه میکنیم. در مثال قبل، محاسبهٔ «تعداد اعداد سهرقمی که رقم 5 ندارند» و کسر آن از کل، راهحل کوتاهتری دارد. اما همیشه اینطور نیست. جدول زیر موارد کاربرد هر روش را نشان میدهد:| روش شمارش | زمان کاربرد | مثال مناسب |
|---|---|---|
| تقسیمبندی حالتها | وقتی شرایط مسئله به راحتی قابل دستهبندی در چند حالت مجزا باشد. | شمارش اعداد با حداقل یک رقم مشخص |
| شمارش مکمل | وقتی حالتهای نقض شرط، سادهتر از حالتهای اصلی شمارش شوند. | شمارش اعداد بدون یک رقم خاص |
| اصل ضرب مستقیم | وقتی انتخابها مستقل از یکدیگر باشند و شرط خاصی وجود نداشته باشد. | تعداد تمام اعداد سهرقمی ( 9×10×10 ) |
چالشهای مفهومی در تقسیمبندی حالتها
❓ سوال ۱: در مسئله چیدن 5 کتاب مختلف روی قفسه، اگر فقط بخواهیم دو کتاب خاص کنار هم باشند، چرا نمیتوانیم بگوییم یا این دو کتاب در سمت چپ هستند یا در سمت راست؟ مشکل کجاست؟
✅ پاسخ: مشکل اینجاست که این دو کتاب میتوانند در هر جای قفسه و با کتابهای دیگری در بین آنها باشند. دستهبندی درست این است که این دو کتاب را یک «بسته» در نظر بگیریم (حالت کنار هم بودن) و سپس این بسته را با 3 کتاب دیگر جابهجا کنیم (4! حالت) و سپس جای دو کتاب داخل بسته را عوض کنیم (2! حالت). این یعنی دستهبندی بر اساس «یکپارچگی» بسته، نه بر اساس موقعیت مطلق.
❓ سوال ۲: برای شمارش تعداد زیرمجموعههای یک مجموعهٔ n عضوی که حداقل یک عضو دارند، آیا میتوانیم آن را به حالتهای «شامل عضو اول»، «شامل عضو دوم» و ... تقسیم کنیم؟
✅ پاسخ: خیر! زیرا این حالتها نااشتراک نیستند. یک زیرمجموعه میتواند هم شامل عضو اول و هم شامل عضو دوم باشد و در دو حالت شمرده شود. روش صحیح، تقسیمبندی بر اساس تعداد اعضای زیرمجموعه است: زیرمجموعههای 1 عضوی، 2 عضوی، ...، n عضوی. سپس جمع C(n,1) + C(n,2) + ... + C(n,n) که برابر 2^n - 1 است.
❓ سوال ۳: در پرتاب همزمان دو تاس، چند حالت داریم که مجموع اعداد زوج باشد؟ چرا دستهبندی بر اساس زوج یا فرد بودن تاس اول اشتباه است؟
✅ پاسخ: دستهبندی بر اساس تاس اول درست است به شرطی که آن را کامل کنیم. میتوانیم به دو حالت «تاس اول زوج» و «تاس اول فرد» تقسیم کنیم. اگر تاس اول زوج باشد، برای زوج شدن مجموع، تاس دوم باید زوج باشد (3 × 3 = 9 حالت). اگر تاس اول فرد باشد، تاس دوم باید فرد باشد (3 × 3 = 9 حالت). جمعاً 18 حالت. اشتباه رایج این است که فقط یک حالت را بشماریم یا حالتها را اشتباه ترکیب کنیم.
پاورقیها
- 1شمارش (Enumeration): در ریاضیات، به فرایند تعیین تعداد اعضای یک مجموعهٔ متناهی، «شمارش» گویند. این کار معمولاً بدون شمردن تکتک اعضا و با استفاده از قواعد ترکیبیات انجام میشود.
- 2اصل جمع (Rule of Sum): یک اصل بنیادی در ترکیبیات که بیان میکند اگر کاری را بتوان به دو روش مجزا (با شرط نبودن اشتراک) انجام داد، تعداد کل روشها برابر مجموع روشهای هر دو حالت است.
