اصل ضرب: کلید طلایی شمارش حالتهای ممکن
۱. تعریف و صورتبندی اصل ضرب
اگر بخواهیم عملی را در k مرحله پشت سر هم انجام دهیم، بهطوری که مرحله اول دارای n₁ حالت ممکن باشد، مرحله دوم n₂ حالت ممکن، و به همین ترتیب تا مرحله k که nₖ حالت ممکن داشته باشد، در این صورت تعداد کل حالتهای ممکن برای انجام این عمل برابر است با:۲. کاربرد اصل ضرب در مسائل روزمره و علمی
برای درک عمیقتر این مفهوم، چند مثال عینی را بررسی میکنیم:- مثال انتخاب وعده غذایی فرض کنید در یک رستوران برای شروع غذا ۳ نوع پیشغذا، برای وعده اصلی ۴ نوع غذا و برای دسر ۲ نوع دسر وجود دارد. اگر یک مشتری بخواهد یک پیشغذا، یک غذای اصلی و یک دسر سفارش دهد، به چند روش میتواند این کار را انجام دهد؟ طبق اصل ضرب، تعداد حالتها برابر است با $3 \times 4 \times 2 = 24$ حالت مختلف.
- مثال شماره تلفن در یک شهر، شماره تلفنها از ۷ رقم تشکیل شده است. اگر رقم اول بتواند از بین ۵ رقم (۵-۹) و هرکدام از ۶ رقم بعدی بتوانند هر رقمی از ۰ تا ۹ باشند، تعداد کل شمارههای ممکن چقدر است؟ پاسخ: $5 \times 10 \times 10 \times 10 \times 10 \times 10 \times 10 = 5 \times 10^6 = 5,000,000$ شماره.
۳. جدول مقایسه موارد استفاده از اصل ضرب
| نوع مسئله | شرح مراحل | محاسبه | تعداد کل |
|---|---|---|---|
| انتخاب لباس | ۴ شلوار، ۵ پیراهن، ۳ کت | $4 \times 5 \times 3$ | ۶۰ |
| پرتاب سکه و تاس | ۲ حالت سکه، ۶ حالت تاس | $2 \times 6$ | ۱۲ |
| شماره پلاک (۲ حرف و ۳ عدد) | ۲۶ حرف، ۱۰ رقم | $26^2 \times 10^3$ | ۶۷۶,۰۰۰ |
| رمزیابی | ۴ رقم (تکرار مجاز) | $10^4$ | ۱۰,۰۰۰ |
۴. اصل ضرب در حالتهای خاص: جایگشت و ترکیب
اصل ضرب زیربنای دو مفهوم مهم دیگر در ترکیبیات، یعنی جایگشت[2] و ترکیب[3] است. برای نمونه، تعداد جایگشتهای r شیء از n شیء متمایز (بدون تکرار) برابر است با:۵. چالشهای مفهومی
❓ چالش ۱: تفاوت اصل ضرب با اصل جمع در چیست؟
اصل جمع زمانی به کار میرود که کارها بر حسب «یا» از هم جدا باشند (انتخاب بین چند دسته مجزا)، در حالی که اصل ضرب برای کارهای متوالی و «و» بودن آنهاست. به بیان ساده، اگر کاری به دو روش مجزا قابل انجام باشد، از اصل جمع استفاده میکنیم، اما اگر کاری شامل چند مرحله متوالی باشد، اصل ضرب به کار میآید.
❓ چالش ۲: آیا اصل ضرب همیشه با ضرب کردن تعداد گزینههای هر مرحله بهدست میآید؟ تکلیف مراحل وابسته چه میشود؟
بله فرمول اصلی همان ضرب است، اما اگر مراحل وابسته باشند (مثلاً بعد از انتخاب یک عضو، دیگر نتوان آن را انتخاب کرد)، تعداد انتخابهای مرحله بعد کاهش مییابد. در این حالت نیز اصل ضرب برقرار است، فقط اعداد در هر مرحله تغییر میکنند. مثال: انتخاب یک نفر به عنوان رئیس و یک نفر به عنوان نایبرئیس از بین ۱۰ نفر: $10 \times 9 = 90$.
❓ چالش ۳: چگونه اصل ضرب میتواند به محاسبه تعداد حالتهای یک شبکه یا مسیریابی کمک کند؟
در یک شبکه، اگر بخواهیم از نقطه A به نقطه B برسیم و چند مسیر پیش رو داشته باشیم، و هر مسیر شامل گامهای مشخصی باشد، تعداد کل راهها با ضرب تعداد انتخابهای هر گام بهدست میآید. برای مثال در یک جدول $3 \times 4$ برای رفتن از خانه بالا چپ به پایین راست (با فرض حرکت فقط به راست و پایین)، تعداد مسیرها حاصل جمعی از ضرایب دوجملهای است که ریشه در اصل ضرب دارد.
۶. مثال عملی ترکیبی: طراحی یک رمز عبور امن
فرض کنید میخواهیم یک رمز عبور ۶ کاراکتری طراحی کنیم. شرایط به این شرح است:- کاراکتر اول: یک حرف بزرگ انگلیسی (۲۶ حالت).
- کاراکتر دوم: یک حرف کوچک انگلیسی (۲۶ حالت).
- کاراکتر سوم و چهارم: یک رقم (۱۰ حالت برای هرکدام).
- کاراکتر پنجم: یکی از نمادهای ! @ # $ % & * (۷ حالت).
- کاراکتر ششم: میتواند حرف بزرگ، کوچک، رقم یا نماد باشد (مجموعاً $26+26+10+7 = 69$ حالت).
پاورقی
[1] Fundamental Counting Principle: اصلی در ترکیبیات که بیان میکند اگر یک رویداد به m طریق و رویداد دیگر به n طریق رخ دهد، تعداد طریقهایی که این دو رویداد میتوانند با هم رخ دهند m × n است.
[2] Permutation: ترتیببندی تعدادی شیء در کنار هم؛ در جایگشت، ترتیب قرار گرفتن اشیا مهم است.
[3] Combination: انتخاب تعدادی شیء از یک مجموعه بدون در نظر گرفتن ترتیب.
