اصل جمع: بنیاد شمارش در ریاضیات گسسته
۱. مفهوم اصلی و شرط اساسی: جداسازی روشها
قلب تپندهی اصل جمع در یک کلمه خلاصه میشود: «یا». هرگاه در یک مسئله با کلمهی «یا» مواجه شدیم، به طور بالقوه با اصل جمع سر و کار داریم. برای مثال، اگر بپرسیم: «میخواهم یک کتاب بخرم، یا از فروشگاه A که ۵ کتاب مورد علاقهام را دارد، یا از فروشگاه B که ۳ کتاب مورد علاقهام را دارد؟» تعداد کل انتخابهای من چندتاست؟ پاسخ ۵ + ۳ = ۸ کتاب است.
اما اینجا یک شرط بسیار مهم وجود دارد که اگر رعایت نشود، پاسخ ما اشتباه خواهد بود: روشها باید مجزا یا به عبارت دقیقتر، ناسازگار[n] باشند. یعنی هیچ انتخابی نباید در دو روش به طور همزمان امکانپذیر باشد. در مثال بالا، فرض کنید فروشگاهها متفاوت هستند و یک کتاب مشخص نمیتواند همزمان در هر دو فروشگاه باشد، پس شرط برقرار است. اما اگر یک کتاب خاص در هر دو فروشگاه وجود داشته باشد و من آن را به عنوان یک انتخاب واحد در نظر بگیرم، آنگاه روشها همپوشانی پیدا میکنند و برای محاسبهی صحیح باید از اصل شمول و طرد [n] استفاده کرد که حالت پیشرفتهتری از شمارش است.
به بیان مجموعهها، اگر $A_1, A_2, \dots, A_k$ مجموعهی حالتهای ممکن برای هر روش باشند و این مجموعهها دو به دو مجزا باشند (اشتراک آنها تهی باشد)، آنگاه تعداد کل حالتها در اجتماع آنها برابر است با حاصلجمع تعداد اعضای هر مجموعه :
(به شرطی که $A_i \cap A_j = \emptyset$ برای هر $i \neq j$)
۲. کاربردهای عملی و روزمرهی اصل جمع
برای درک بهتر، بیایید چند مثال عینی و کاربردی را بررسی کنیم که در زندگی روزمره با آن مواجه میشویم.
- انتخاب وسیلهی نقلیه: فرض کنید برای سفر به یک شهر دیگر، سه خط اتوبوسرانی با ۴ حرکت مختلف و دو خط راهآهن با ۳ حرکت مختلف وجود داشته باشد. اگر بتوانید فقط با یکی از این وسایل سفر کنید، چند گزینه برای سفر دارید؟
حل از آنجا که نمیتوانید همزمان با اتوبوس و قطار سفر کنید، این دو روش (اتوبوس و قطار) مجزا هستند. پس تعداد کل گزینهها برابر است با ۴ + ۳ = ۷ گزینه. - منوی رستوران: در یک فستفود، منوی غذا شامل ۵ نوع پیتزا و ۴ نوع ساندویچ است. اگر مشتری بخواهد فقط یک آیتم از منو انتخاب کند، چند انتخاب دارد؟
حل انتخاب پیتزا یا انتخاب ساندویچ دو حالت مجزا هستند. پس تعداد کل ۵ + ۴ = ۹ انتخاب است. - انتخاب رمز عبور: یک وبسایت برای رمز عبور به ما اجازه میدهد یا از یک کد ۴ رقمی (۱۰۰۰۰ حالت) و یا از یک کلمهی عبور ۵ حرفی (حروف کوچک انگلیسی، ۲۶^۵ حالت) استفاده کنیم. چند رمز عبور منحصربهفرد میتوانیم داشته باشیم؟
حل چون این دو دسته مجزا هستند (یک رمز نمیتواند هم عددی و هم حرفی باشد)، تعداد کل برابر است با: ۱۰۰۰۰ + ۲۶^۵ = ۱۰۰۰۰ + ۱۱۸۸۱۳۷۶ = ۱۱۸۹۱۳۷۶ حالت.
| مثال عملی | انتخابهای روش اول | انتخابهای روش دوم | تعداد کل |
|---|---|---|---|
| انتخاب یک خودروی داخلی یا خارجی | ۱۲ مدل داخلی | ۸ مدل خارجی | ۲۰ |
| خرید یک توپ از فروشگاه لوازم ورزشی | ۶ نوع توپ والیبال | ۵ نوع توپ بسکتبال | ۱۱ |
| یک شمارهی تلفن همراه (۰۹۱۲ یا ۰۹۳۵) | ۱۰۰۰۰۰ شماره ممکن (پیششماره ۰۹۱۲) | ۱۰۰۰۰۰ شماره ممکن (پیششماره ۰۹۳۵) | ۲۰۰۰۰۰ |
۳. تعمیم اصل جمع به بیش از دو روش
زیبایی اصل جمع در قابلیت تعمیم آن به هر تعداد روش است. اگر به جای دو روش، k روش برای انجام یک کار وجود داشته باشد و همهی این روشها دو به دو مجزا باشند، باز هم تعداد کل حالتها از جمع سادهی حالتهای هر روش به دست میآید .
برای نمونه، یک دانشآموز را در نظر بگیرید که برای مطالعهی درس ریاضی میتواند از سه منبع استفاده کند: کتاب درسی (۱۰ فصل)، کتاب کمکآموزشی (۸ فصل) و جزوهی معلم (۵ فصل). اگر او بخواهد دقیقاً یک فصل را از یکی از این منابع مطالعه کند، چند فصل برای انتخاب دارد؟ از آنجا که این سه منبع جدا از هم در نظر گرفته میشوند و فصول آنها با هم همپوشانی ندارند، تعداد کل برابر است با ۱۰ + ۸ + ۵ = ۲۳ فصل.
در اینجا، اصل جمع برای سه مجموعهی مجزا به کار رفته است: $|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3|$.
۴. کاربرد در مسائل ترکیبیاتی و شمارش اعداد
اصل جمع یکی از ابزارهای قدرتمند برای حل مسائل پیچیدهتر شمارش است. این اصل اغلب در ترکیب با اصل ضرب به کار میرود . بیایید با یک مثال کلاسیک این موضوع را بررسی کنیم.
مسئله: تعداد اعداد طبیعی دو رقمی که بر ۳ یا بر ۵ بخشپذیرند، چندتاست؟
تحلیل: اعداد دو رقمی از ۱۰ تا ۹۹ هستند. برای حل این مسئله، میتوانیم مسئله را به سه روش مجزا تقسیم کنیم:
- روش اول (A): اعداد بخشپذیر بر ۳.
- روش دوم (B): اعداد بخشپذیر بر ۵.
اما نکته اینجاست: اعدادی که هم بر ۳ و هم بر ۵ بخشپذیرند (یعنی بر ۱۵ بخشپذیرند) در هر دو روش قرار میگیرند. پس روشهای A و Bمجزا نیستند. در اینجا نمیتوانیم مستقیماً از اصل جمع ساده استفاده کنیم، بلکه باید تعداد اعضای اشتراک آنها را از مجموع کم کنیم.
حل گامبهگام
- تعداد اعداد دو رقمی بخشپذیر بر ۳: کوچکترین (۱۲)، بزرگترین (۹۹)، تعداد: $(99-12)/3 + 1 = 87/3 + 1 = 29 + 1 = 30$.
- تعداد اعداد دو رقمی بخشپذیر بر ۵: کوچکترین (۱۰)، بزرگترین (۹۵)، تعداد: $(95-10)/5 + 1 = 85/5 + 1 = 17 + 1 = 18$.
- تعداد اعداد دو رقمی بخشپذیر بر ۱۵ (اشتراک): کوچکترین (۱۵)، بزرگترین (۹۰)، تعداد: $(90-15)/15 + 1 = 75/15 + 1 = 5 + 1 = 6$.
پس تعداد اعداد دودرصدی که بر ۳ یا ۵ بخشپذیرند برابر است با $۳۰ + ۱۸ - ۶ = ۴۲$.
۵. چالشهای مفهومی و پرسشهای متداول
❓ چالش اول: چه زمانی باید از اصل جمع استفاده کنم و چه زمانی از اصل ضرب؟
این یک سوال کلیدی است. قانون کلی این است: اگر انتخابها به صورت «یا» مطرح شوند (انتخاب از بین دستههای مختلف)، از اصل جمع استفاده کنید. اگر انتخابها به صورت «و» و پشت سر هم باشند (ابتدا این کار، سپس آن کار)، از اصل ضرب استفاده میکنیم. به عنوان مثال، انتخاب یک نوشیدنی (چای یا قهوه) اصل جمع است، اما انتخاب یک نوشیدنی و یک خوراکی اصل ضرب است.
❓ چالش دوم: آیا اصل جمع همیشه به این سادگی است؟ اگر روشها کاملاً مجزا نباشند چه؟
خیر، مهمترین نکته همین جاست! اگر روشها مجزا نباشند (یعنی برخی حالتها در دو روش مشترک باشند)، جمع ساده باعث میشود آن حالتها دوبار شمرده شوند. در این مواقع باید از فرمول کلیتر شمول و طرد استفاده کنیم که برای دو مجموعه به صورت |A∪B| = |A| + |B| - |A∩B| است. برای مثال، اگر بخواهیم از بین دانشجویان ورزشکار، کسانی را که فوتبال یا والیبال بازی میکنند بشماریم، باید آنهایی که هر دو را بازی میکنند یک بار کم کنیم.
❓ چالش سوم: چگونه میتوانم تشخیص دهم که یک مسئله، چند روش مجزا دارد؟
برای تشخیص روشهای مجزا، به دنبال کلمهی «یا» بگردید و سعی کنید مسئله را بر اساس یک ویژگی به چند دستهی بدون اشتراک تقسیم کنید. مثلاً در مسئلهی «انتخاب یک کارت از یک دسته»، میتوانیم بر اساس رنگ (قرمز یا سیاه) یا بر اساس خال (پیک، دل، خشت، گشنیز) دستهبندی کنیم. اگر دستهبندی به گونهای باشد که یک کارت نتواند همزمان در دو دسته قرار گیرد (مثلاً یک کارت نمیتواند هم پیک باشد هم دل)، آنگاه دستهها مجزا هستند و میتوان از اصل جمع استفاده کرد.
? نکتهی نهایی
اصل جمع، یک ابزار ساده اما قدرتمند است که پایه و اساس بسیاری از محاسبات پیچیدهتر در ریاضیات گسسته و احتمال را تشکیل میدهد. با درک درست شرط «مجزا بودن» روشها و تشخیص بهموقع آن در مسائل، میتوانید از این اصل بهدرستی استفاده کنید و از اشتباهات رایج در شمارش جلوگیری نمایید. این اصل نهتنها در ریاضیات، بلکه در برنامهنویسی، تصمیمگیریهای روزمره و هر جایی که پای انتخاب و گزینههای ممکن در میان باشد، کاربرد دارد.
پاورقیها
[n]روشهای ناسازگار (Mutually Exclusive): در نظریهی احتمال و شمارش، دو پیشامد یا روش را ناسازگار گویند اگر وقوع همزمان آنها غیرممکن باشد. به عبارت دیگر، اشتراک آنها تهی است.
[n]اصل شمول و طرد (Inclusion-Exclusion Principle): یک تکنیک شمارش است که برای محاسبهی تعداد اعضای اجتماع چند مجموعه که ممکن است اشتراک داشته باشند، به کار میرود. فرمول سادهی آن برای دو مجموعه A و B به صورت $|A \cup B| = |A| + |B| - |A \cap B|$ است.
[n]اصل جمع (Addition Principle): اصلی بنیادین در ترکیبیات که بیان میکند اگر مجموعهای از روشها برای انجام یک کار وجود داشته باشند که هیچ دو روشی نتوانند همزمان رخ دهند، تعداد کل روشها برابر با مجموع تعداد حالتهای هر روش است .