اصل جمع: پایه و اساس شمارش حالتها
با اصل جمع، تعداد راههای انجام یک کار را در شرایط گوناگون محاسبه کنید
در این مقاله با اصل جمع[1]، یکی از پایهایترین اصول علم ترکیبیات[2] آشنا میشویم. این اصل بیان میکند که اگر یک کار به چند روش ناسازگار (یا به عبارتی، روشهایی که نمیتوانند همزمان اتفاق بیفتند) قابل انجام باشد، تعداد کل حالتها برابر است با مجموع حالتهای هر روش. با مثالهای متنوع و کاربردی، از انتخاب غذا گرفته تا مسائل پیشرفتهتر، این مفهوم را به زبانی ساده فرا خواهید گرفت.
بیان ساده اصل جمع و پیشنیازهای آن
فرض کنید میخواهید از نقطه الف به نقطه ب بروید. دو مسیر پیادهروی و سه مسیر دوچرخهسواری وجود دارد. این مسیرها با یکدیگر تداخل ندارند و شما نمیتوانید همزمان هم پیاده بروید و هم دوچرخهسواری کنید. در این صورت، طبق اصل جمع، تعداد کل راهها برای رسیدن از الف به ب برابر است با مجموع راههای پیادهروی و دوچرخهسواری، یعنی $2 + 3 = 5$ راه. این همان جوهره اصلی اصل جمع است. شرط اصلی برای استفاده از این اصل، ناسازگاری روشها است؛ یعنی هیچ حالتی متعلق به دو روش همزمان نباشد. به این حالت، روشهای «جدای از هم» یا «متفرق» نیز میگویند.
مثالهای روزمره از اصل جمع
فرض کنید در یک کتابخانه، 12 کتاب ریاضی، 8 کتاب فیزیک و 5 کتاب شیمی داریم. اگر بخواهیم فقط یک کتاب از این کتابخانه امانت بگیریم، به چند روش میتوانیم این کار را انجام دهیم؟ از آنجا که انتخاب هر کتاب از یک شاخه، با انتخاب کتاب از شاخه دیگر ناسازگار است (یک کتاب نمیتواند همزمان ریاضی و فیزیک باشد)، تعداد کل حالتها برابر است با $12 + 8 + 5 = 25$. مثال دیگر: در یک منوی رستوران، 6 نوع پیشغذا و 4 نوع دسر داریم. اگر مشتری بخواهد تنها یکی از این دو (یک پیشغذا یا یک دسر) را سفارش دهد، به $6+4=10$ روش میتواند این کار را انجام دهد.
| موقعیت | روش اول (تعداد حالت) | روش دوم (تعداد حالت) | تعداد کل حالتها |
|---|---|---|---|
| انتخاب یک کتاب | ریاضی (12) | فیزیک (8) | $12+8=20$ |
| انتخاب پیشغذا یا دسر | پیشغذا (6) | دسر (4) | $6+4=10$ |
| شمارهگذاری با ارقام خاص | ارقام زوج (5) | ارقام فرد (5) | $5+5=10$ |
کاربرد عملی اصل جمع در رمزگذاری و مسائل امنیتی
فرض کنید قصد داریم یک رمز عبور چهار رقمی با ارقام 0 تا 9 بسازیم که با یکی از دو شرط زیر مطابقت داشته باشد: شرط اول اینکه رقم اول زوج باشد، یا شرط دوم اینکه رقم اول فرد باشد. بدیهی است که این دو شرط با یکدیگر ناسازگارند، زیرا یک رقم نمیتواند همزمان زوج و فرد باشد. اگر بخواهیم تعداد کل رمزهای عبوری که در یکی از این دو دسته قرار میگیرند را محاسبه کنیم، از اصل جمع استفاده میکنیم:
- حالتهای با رقم اول زوج: رقم اول میتواند یکی از 5 رقم $\{0,2,4,6,8\}$ باشد. برای سه رقم بعدی، هر کدام 10 انتخاب دارند. بنابراین تعداد این حالتها برابر $5 \times 10 \times 10 \times 10 = 5000$ است.
- حالتهای با رقم اول فرد: رقم اول میتواند یکی از 5 رقم $\{1,3,5,7,9\}$ باشد. به طریق مشابه، تعداد این حالتها نیز $5 \times 10 \times 10 \times 10 = 5000$ است.
چالشهای مفهومی در بهکارگیری اصل جمع
۱. چگونه بفهمیم که دو روش، «ناسازگار» هستند؟
پاسخ: دو روش ناسازگارند اگر نتوانند همزمان رخ دهند. یعنی اشتراک مجموعه حالتهای آنها تهی باشد. در مثال کتابخانه، یک کتاب مشخص نمیتواند هم در قفسه ریاضی باشد و هم در قفسه فیزیک. پس انتخاب کتاب ریاضی و انتخاب کتاب فیزیک دو روش ناسازگار هستند. اگر اشتراکی وجود داشته باشد (مثلاً در یک نظرسنجی، فردی همزمان دو نظر داشته باشد)، اصل جمع به سادگی قابل استفاده نیست و باید از اصل شامل و عدم شمول[3] استفاده کرد.
پاسخ: دو روش ناسازگارند اگر نتوانند همزمان رخ دهند. یعنی اشتراک مجموعه حالتهای آنها تهی باشد. در مثال کتابخانه، یک کتاب مشخص نمیتواند هم در قفسه ریاضی باشد و هم در قفسه فیزیک. پس انتخاب کتاب ریاضی و انتخاب کتاب فیزیک دو روش ناسازگار هستند. اگر اشتراکی وجود داشته باشد (مثلاً در یک نظرسنجی، فردی همزمان دو نظر داشته باشد)، اصل جمع به سادگی قابل استفاده نیست و باید از اصل شامل و عدم شمول[3] استفاده کرد.
۲. آیا اصل جمع فقط برای دو روش کاربرد دارد؟
پاسخ: خیر، اصل جمع برای هر تعداد متناهی از روشهای ناسازگار قابل تعمیم است. اگر روشهای $A_1, A_2, ..., A_n$ دو به دو ناسازگار باشند (یعنی اشتراک هیچ دوتایی از آنها تهی نباشد)، آنگاه تعداد کل حالتها برابر است با $|A_1| + |A_2| + ... + |A_n|$.
پاسخ: خیر، اصل جمع برای هر تعداد متناهی از روشهای ناسازگار قابل تعمیم است. اگر روشهای $A_1, A_2, ..., A_n$ دو به دو ناسازگار باشند (یعنی اشتراک هیچ دوتایی از آنها تهی نباشد)، آنگاه تعداد کل حالتها برابر است با $|A_1| + |A_2| + ... + |A_n|$.
۳. تفاوت اصلی اصل جمع و اصل ضرب در چیست؟
پاسخ: اصل جمع در جایی به کار میرود که یک کار را از میان چند راهحل یا گزینه (روشهای ناسازگار) انتخاب میکنیم (انتخاب «یا»-ی انحصاری). اما اصل ضرب زمانی استفاده میشود که یک کار شامل چند مرحله متوالی است (انتخاب «و»-ی همزمان). به عنوان مثال، انتخاب یک کتاب از قفسه ریاضی یا فیزیک، کاربرد اصل جمع است. اما انتخاب یک کتاب ریاضی و یک کتاب فیزیک (یک جفت کتاب) کاربرد اصل ضرب است ($12 \times 8$ حالت).
پاسخ: اصل جمع در جایی به کار میرود که یک کار را از میان چند راهحل یا گزینه (روشهای ناسازگار) انتخاب میکنیم (انتخاب «یا»-ی انحصاری). اما اصل ضرب زمانی استفاده میشود که یک کار شامل چند مرحله متوالی است (انتخاب «و»-ی همزمان). به عنوان مثال، انتخاب یک کتاب از قفسه ریاضی یا فیزیک، کاربرد اصل جمع است. اما انتخاب یک کتاب ریاضی و یک کتاب فیزیک (یک جفت کتاب) کاربرد اصل ضرب است ($12 \times 8$ حالت).
با اصل جمع، شمارش حالتها در مسائل گسسته به سادگی جمع اعداد تبدیل میشود، به شرطی که از ناسازگاری و جدایی روشها از یکدیگر اطمینان داشته باشیم. این اصل بنیادی، همراه با اصل ضرب، پایه و اساس علم ترکیبیات را تشکیل میدهد و در حل مسائل پیچیدهتر، مانند محاسبه احتمالات و طراحی الگوریتمها، نقشی کلیدی ایفا میکند. تسلط بر این مفهوم ساده اما قدرتمند، درک عمیقتری از جهان گسسته پیرامون ما فراهم میآورد.
پاورقی
1 اصل جمع (Sum Rule / Addition Principle): اصلی در ترکیبیات که بیان میدارد اگر کاری به $k$ طریق مختلف قابل انجام باشد، به طوری که این طرق دو به دو ناسازگار باشند، آنگاه تعداد کل روشهای انجام آن کار، مجموع تعداد روشهای هر طریق است.
2 ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعه روشهای شمارش، ترکیب و مرتبسازی اعضای مجموعههای گسسته میپردازد.
3 اصل شمول و عدم شمول (Inclusion–Exclusion Principle): روشی برای شمارش اعضای اجتماع چند مجموعه که اشتراکهای غیرتهی دارند. این اصل، اشتراکها را از مجموع ساده کم میکند تا از شمارش مضاعف جلوگیری شود.
2 ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعه روشهای شمارش، ترکیب و مرتبسازی اعضای مجموعههای گسسته میپردازد.
3 اصل شمول و عدم شمول (Inclusion–Exclusion Principle): روشی برای شمارش اعضای اجتماع چند مجموعه که اشتراکهای غیرتهی دارند. این اصل، اشتراکها را از مجموع ساده کم میکند تا از شمارش مضاعف جلوگیری شود.
