تعمیم اصل ضرب: کلید گشایش قفل شمارش حالتها
مرحلهبندی مسئله: درک ساختار گامها
برای استفاده از اصل ضرب، اولین و مهمترین گام، شناسایی درست مراحل انجام یک کار است. هر مرحله باید یک انتخاب مستقل از مراحل دیگر باشد. به بیان دیگر، نتیجه مرحله اول نباید بر تعداد گزینههای مرحله دوم تأثیر بگذارد، مگر اینکه در صورت وابستگی، بتوانیم آن را با اصل جمع یا روشهای پیشرفتهتر ترکیب کنیم. در این مقاله، بر روی حالت پایهای و مستقل بودن مراحل تمرکز میکنیم. این مستقل بودن، همان چیزی است که سادگی و قدرت اصل ضرب را نمایان میکند.
بهعنوان مثال، فرض کنید میخواهید یک شماره تلفن 4 رقمی با ارقام 0-9 بسازید. این کار شامل 4 مرحله است (انتخاب هر رقم). مرحله اول 10 روش دارد. اگر تکرار رقم مجاز باشد، مرحله دوم نیز 10 روش خواهد داشت و به همین ترتیب. در اینجا هر مرحله کاملاً مستقل از مراحل قبل است. اما اگر شرط کنیم رقم اول نباید صفر باشد، مرحله اول 9 روش و مراحل بعدی همچنان 10 روش خواهند داشت. در هر دو حالت، اصل ضرب به سادگی قابل اعمال است.
فرمولبندی و نمادگذاری ریاضی
به زبان ریاضی، اگر یک فرآیند تصمیمگیری شامل n گام پیاپی باشد و تعداد حالات ممکن در گام iام برابر n_i باشد، آنگاه تعداد کل حالات ممکن برای کل فرآیند عبارت است از:
این فرمول که به نام اصل ضرب1 یا قاعده بنیادی شمارش شناخته میشود، در حقیقت بیانگر تعداد اعضای حاصلضرب دکارتی مجموعههای متناهی است. اگر مجموعه راهحلهای مرحله اول $A_1$ با اندازه $n_1$ و مرحله دوم $A_2$ با اندازه $n_2$ باشد، آنگاه تعداد زوجهای مرتب $(a_1, a_2)$ که $a_1 \in A_1$ و $a_2 \in A_2$ است، برابر $n_1 \times n_2$ خواهد بود. این ایده برای $k$ مجموعه به سادگی قابل تعمیم است.
کاربرد عملی: از منوی رستوران تا طراحی رمز عبور
اصل ضرب در زندگی روزمره ما جاری است، بدون آنکه متوجه باشیم. یک منوی رستوران را در نظر بگیرید که در آن 3 نوع پیشغذا، 5 نوع غذای اصلی و 2 نوع دسر وجود دارد. برای انتخاب یک وعده غذایی کامل شامل یک پیشغذا، یک غذای اصلی و یک دسر، با استفاده از اصل ضرب، تعداد کل منوهای ممکن برابر است با:
این یعنی شما میتوانید 30 شب به این رستوران بروید و هر بار یک ترکیب جدید از غذاها را تجربه کنید! در دنیای دیجیتال، طراحی یک رمز عبور امن نیز از همین قانون پیروی میکند. فرض کنید رمز عبوری از 8 کاراکتر تشکیل شده باشد که هر کاراکتر میتواند یکی از 26 حرف کوچک انگلیسی باشد. تعداد کل رمزهای عبور ممکن برابر است با:
اگر به این رمز، اعداد (10 گزینه) و حروف بزرگ (26 گزینه) را هم اضافه کنیم، تعداد گزینهها برای هر کاراکتر به $26+26+10=62$ میرسد و تعداد کل حالات به $62^8$ (حدود 218 تریلیون) افزایش مییابد که نشاندهنده قدرت شگفتانگیز اصل ضرب در ایجاد تنوع است.
| کاربرد | تعداد مراحل (k) | روش هر مرحله (m_i) | تعداد کل حالات |
|---|---|---|---|
| شماره تلفن 4 رقمی (با تکرار) | 4 | 10 | $10^4 = 10000$ |
| پرچم 3 راهرنگ (با رنگهای مجزا از 7 رنگ) | 3 | $7, 6, 5$ | $7 \times 6 \times 5 = 210$ |
| انتخاب لباس (4 شلوار، 5 پیراهن، 3 کت) | 3 | $4, 5, 3$ | $4 \times 5 \times 3 = 60$ |
| حالت پرتاب 2 تاس | 2 | $6, 6$ | $6 \times 6 = 36$ |
چالشهای مفهومی در بهکارگیری اصل ضرب
❓ چالش اول: آیا ترتیب اهمیت دارد؟
پاسخ: بله، در اصل ضرب، ترتیب اهمیت دارد زیرا ما با دنبالهای از رویدادها سروکار داریم. به عنوان مثال، انتخاب شماره تلفن 1234 با 4321 متفاوت است. اگر ترتیب مهم نباشد، باید از ترکیبات (نه جایگشت) استفاده کنیم که فرمول متفاوتی دارد. اصل ضرب برای موقعیتهایی که اشیاء را پشت سر هم و به ترتیب انتخاب میکنیم، کاربرد دارد.
❓ چالش دوم: تفاوت اصل ضرب و اصل جمع در چیست؟
پاسخ: اصل جمع زمانی به کار میرود که ما با دو یا چند حالت جدا از هم روبرو باشیم. به عبارت دیگر، اگر یک کار به چند روش مختلف (و غیرهمپوشان) قابل انجام باشد، تعداد کل روشها برابر جمع روشهای هر حالت است. اما اصل ضرب زمانی استفاده میشود که یک کار شامل چند مرحله متوالی باشد. مثال کلاسیک: برای انتخاب یک خودرو اگر بتوان بین 3 مدل داخلی یا 2 مدل خارجی یکی را انتخاب کرد، از اصل جمع ($3+2=5$) استفاده میکنیم. اما اگر بخواهیم برای خودرو، هم مدل و هم رنگ (مثلاً 4 رنگ) را انتخاب کنیم، از اصل ضرب ($5 \times 4 = 20$) استفاده میکنیم.
❓ چالش سوم: اگر تعداد گزینههای یک مرحله به انتخابهای قبلی وابسته باشد، چه باید کرد؟
پاسخ: در این حالت، اصل ضرب به شکل ساده خود کارساز نیست و باید آن را با احتیاط به کار برد. برای مثال، انتخاب سه نماینده از بین 10 نفر برای پستهای رئیس، نایبرئیس و منشی. تعداد گزینهها برای انتخاب رئیس 10 است. پس از آن، برای نایبرئیس 9 گزینه و برای منشی 8 گزینه باقی میماند. در اینجا، اگرچه تعداد گزینهها وابسته است، اما میتوانیم از اصل ضرب به صورت $10 \times 9 \times 8 = 720$ استفاده کنیم. این حالت خاصی از اصل ضرب است که به آن جایگشت2 میگوییم و زمانی کاربرد دارد که اعضا بدون تکرار و با در نظر گرفتن ترتیب انتخاب میشوند.
تمرین عملی گامبهگام
برای تثبیت یادگیری، یک مسئله را گامبهگام حل میکنیم. فرض کنید یک صفحهکلید دارای 26 حرف و 10 رقم (0-9) است. میخواهیم یک کد 5 کاراکتری بسازیم که شرط آن این است که کاراکتر اول یک حرف و کاراکترهای دوم تا پنجم میتوانند حرف یا رقم باشند.
- گام 1 (تحلیل مراحل): مسئله شامل 5 مرحله انتخاب کاراکتر است.
- گام 2 (تعیین تعداد روش هر مرحله):
- مرحله اول (انتخاب کاراکتر اول): فقط حروف ⇒ $m_1 = 26$ روش.
- مرحله دوم (انتخاب کاراکتر دوم): حروف و اعداد ⇒ $m_2 = 26 + 10 = 36$ روش.
- مرحله سوم: مشابه مرحله دوم ⇒ $m_3 = 36$ روش.
- مرحله چهارم: ⇒ $m_4 = 36$ روش.
- مرحله پنجم: ⇒ $m_5 = 36$ روش.
- گام 3 (اعمال اصل ضرب): تعداد کل کدهای ممکن برابر است با:
$N = m_1 \times m_2 \times m_3 \times m_4 \times m_5 = 26 \times 36 \times 36 \times 36 \times 36$
- گام 4 (محاسبه نهایی):
$N = 26 \times (36)^4 = 26 \times 1,679,616 = 43,670,016$
بنابراین، بیش از 43 میلیون کد 5 کاراکتری مختلف میتوانیم داشته باشیم.
پاورقیها
1اصل ضرب (Multiplication Principle): قاعدهای در ترکیبیات که بیان میکند اگر رویداد A به m طریق و رویداد B به n طریق مستقل از A رخ دهد، آنگاه مجموع طرق وقوع هر دو رویداد به ترتیب (A و سپس B) برابر $m \times n$ است.
2جایگشت (Permutation): به هر ترتیب خاصی از چیدن چند شیء متمایز در کنار هم، یک جایگشت گویند. اگر از بین $n$ شیء متمایز، $k$ شیء را با در نظر گرفتن ترتیب انتخاب کنیم، تعداد جایگشتها برابر $P(n,k) = n \times (n-1) \times \dots \times (n-k+1)$ است.
