مرحله در شمارش: از انتخاب ساده تا اصل ضرب
مرحله چیست؟ قلب تپنده اصل ضرب
در زندگی روزمره، بسیاری از کارها را به صورت گامبهگام انجام میدهیم. برای مثال، وقتی میخواهید یک ساندویچ آماده کنید، ابتدا نان را انتخاب میکنید، سپس نوع گوشت یا پروتئین را برمیگزینید و در نهایت سس و مخلفات را اضافه میکنید. هر یک از این گامها، یک «مرحله» از یک فرآیند بزرگتر هستند. در علم شمارش که به آن ترکیبیات میگویند، به این گامها، «مرحله» (یا House) گفته میشود.
ویژگی اصلی یک مرحله این است که انتخابها در آن، مستقل از مراحل دیگر انجام میشوند. به عبارت دیگر، تعداد روشهایی که میتوانید یک مرحله را انجام دهید، تحت تأثیر انتخاب شما در مراحل قبلی یا بعدی نیست (یا اگر تأثیر بپذیرد، باز هم میتوان آن را با روشهای پیشرفتهتری مدلسازی کرد). این استقلال، پایه و اساس «اصل ضرب» را تشکیل میدهد.
تعریف ساده: مرحله، یک «بخش» یا «گام» از یک کار چندبخشی است که برای تکمیل کار اصلی باید انجام شود.
اصل ضرب: وقتی «و» به معنای «ضرب» است
اصل ضرب میگوید: «اگر انجام یک کار شامل k مرحله پشت سر هم باشد، به طوری که مرحلهٔ اول به n1 طریق، مرحلهٔ دوم به n2 طریق، ... و مرحلهٔ kام به nk طریق قابل انجام باشد، آنگاه کل کار به n1 × n2 × ... × nk طریق قابل انجام خواهد بود.» کلیدواژهای که به ما میگوید باید از اصل ضرب استفاده کنیم، کلمهٔ «و» است: ما باید مرحلهٔ اول و مرحلهٔ دوم و ... را انجام دهیم تا کار به پایان برسد .
$ \text{تعداد کل حالتها} = n_1 \times n_2 \times \dots \times n_k $
برای مثال، تصور کنید یک رستوران برای یک وعدهٔ غذایی کامل، ۳ نوع پیشغذا (سوپ، سالاد، فینگر فود)، ۴ نوع غذای اصلی (مرغ، ماهی، گوشت، گیاهی) و ۲ نوع دسر (بستنی، پودینگ) دارد .
- مرحلهٔ ۱ (انتخاب پیشغذا):3 حالت
- مرحلهٔ ۲ (انتخاب غذای اصلی):4 حالت
- مرحلهٔ ۳ (انتخاب دسر):2 حالت
طبق اصل ضرب، تعداد کل منوهای ممکن برابر است با: $3 \times 4 \times 2 = 24$ منوی مختلف. این یعنی شما میتوانید ۲۴ نوع وعدهٔ غذایی متفاوت را تجربه کنید، بدون آنکه نیاز باشد همهٔ آنها را یکبهیک لیست کنید .
اصل جمع در مقابل اصل ضرب: تمایز «یا» و «و»
یکی از چالشهای اصلی دانشآموزان، تشخیص موقعیت استفاده از اصل جمع و اصل ضرب است. تفاوت این دو در نوع نگاه ما به مسئله نهفته است .
- اصل جمع (قاعده «یا»): وقتی با یک «انتخاب» از میان چند دستهٔ مجزا روبرو هستیم و فقط یکی از آنها را انتخاب میکنیم، از اصل جمع استفاده میشود. به عبارت دیگر، کار ما یکمرحلهای است، اما گزینهها در گروههای مختلفی قرار دارند . مثال: میخواهید یک کتاب از قفسه بردارید. در قفسه، ۵ کتاب داستان یا ۳ کتاب شعر وجود دارد. تعداد انتخابهای شما $5 + 3 = 8$ است.
- اصل ضرب (قاعده «و»): وقتی کار ما چندمرحلهای است و باید تمام مراحل پشت سر هم انجام شوند، از اصل ضرب استفاده میکنیم. مثال: میخواهید یک کتاب داستان و یک کتاب شعر از دو قفسهٔ مجزا انتخاب کنید. تعداد انتخابها $5 \times 3 = 15$ است.
برای درک بهتر، جدول زیر را ببینید :
| ویژگی | اصل جمع | اصل ضرب |
|---|---|---|
| کلمه کلیدی | «یا» | «و» |
| تعداد مراحل | یکمرحلهای (انتخاب از چند گروه) | چندمرحلهای (گامهای پشت سر هم) |
| عملگر ریاضی | + (جمع) | × (ضرب) |
| مثال | انتخاب یک خودروی قرمز یا یک خودروی آبی | انتخاب رنگ بدنه و سپس انتخاب نوع موتور |
کاربرد عملی: از رمز عبور تا پلاک خودرو
مفهوم «مرحله» و اصل ضرب در دنیای واقعی کاربردهای فراوانی دارد. یکی از بارزترین مثالها، طراحی رمزهای عبور است .
مثال رمز عبور: فرض کنید یک رمز عبور ۴ کاراکتری دارید که هر کاراکتر میتواند یکی از ۲۶ حرف کوچک انگلیسی (a-z) یا یکی از ۱۰ رقم (۰-۹) باشد. در اینجا، انتخاب هر کاراکتر یک «مرحله» مستقل است.
- مرحلهها: ۴ مرحله (انتخاب کاراکتر اول، دوم، سوم و چهارم).
- تعداد حالت در هر مرحله:26 (حرف) + 10 (رقم) = 36 حالت.
طبق اصل ضرب، تعداد کل رمزهای عبور ممکن برابر است با: $36 \times 36 \times 36 \times 36 = 36^4 = 1,679,616$ رمز مختلف . این عدد به ما نشان میدهد که چرا استفاده از ترکیب حروف و اعداد، امنیت را به شدت افزایش میدهد.
مثال شمارهگذاری: در طراحی پلاک خودروها نیز از همین اصل استفاده میشود. اگر پلاکی به شکل XX 123 YY باشد (دو حرف، سه رقم، دو حرف)، با فرض ۲۶ حرف انگلیسی، تعداد پلاکهای ممکن، حاصل ضرب حالتهای هر مرحله است: $26 \times 26 \times 10 \times 10 \times 10 \times 26 \times 26$ که عدد بسیار بزرگی است و از تکرار پلاک جلوگیری میکند .
چالشهای مفهومی در تشخیص و بهکارگیری مراحل
❓ چالش ۱: چه زمانی دو کار، دو «مرحله» محسوب میشوند و چه زمانی دو «حالت» برای یک مرحله؟
پاسخ: این یک سؤال کلیدی است. اگر برای تکمیل کار نهایی، نیاز به انجام هر دو کار داشته باشیم، آن دو کار، «مرحله» هستند (اصل ضرب). اما اگر بتوانیم کار نهایی را با انجام یکی از آن دو کار به پایان برسانیم، آن دو کار، «حالتهای جایگزین» برای یک مرحله هستند (اصل جمع) . مثال: برای درست کردن یک سالاد، اگر هم نیاز به خرد کردن کاهو و هم نیاز به برش زدن گوجه داشته باشیم، این دو مرحله هستند. اما اگر سالاد را میتوان با سس سزار یا سس هزار جزیره درست کرد، انتخاب سس یک مرحله با دو حالت است.
❓ چالش ۲: اگر تعداد حالتهای یک مرحله به انتخاب مرحله قبل وابسته باشد، چه باید کرد؟ (مسئله انتخاب بدون جایگذاری)
پاسخ: این حالت، یک مسئلهٔ «جایگشت»2 است. به عنوان مثال، میخواهیم یک عدد سهرقمی با ارقام غیر تکراری از مجموعه {1,2,3,4} بنویسیم . مرحلهٔ اول (انتخاب رقم صدگان): 4 حالت. مرحلهٔ دوم (انتخاب رقم دهگان): چون یک رقم استفاده شده، 3 حالت. مرحلهٔ سوم (انتخاب رقم یکان): 2 حالت. در اینجا، اصل ضرب همچنان برقرار است، اما تعداد حالتهای مراحل بعدی تحت تأثیر مراحل قبلی کاهش مییابد. جواب: $4 \times 3 \times 2 = 24$.
❓ چالش ۳: چگونه مسائل ترکیبی (جمع و ضرب همزمان) را حل کنیم؟
پاسخ: بسیاری از مسائل، ترکیبی از این دو اصل هستند. در چنین مواردی، ابتدا مسئله را به چند حالت بزرگ (که با «یا» از هم جدا میشوند) تقسیم کرده (اصل جمع)، سپس درون هر کدام از این حالتها، مراحل را شناسایی کرده و تعداد حالتها را ضرب میکنیم (اصل ضرب) . مثال: میخواهیم از بین ۳ مرد و ۴ زن، یک تیم ۲ نفره شامل یک مرد و یک زن تشکیل دهیم. حالتها: (انتخاب مرد اول و زن اول) یا (مرد اول و زن دوم) یا ... اما روش هوشمندانهتر: مرحلهٔ اول انتخاب مرد (۳ حالت) و مرحلهٔ دوم انتخاب زن (۴ حالت) => $3 \times 4 = 12$ تیم.
پاورقیها
1ترکیبیات (Combinatorics): شاخهای از ریاضیات که به مطالعهٔ روشهای شمارش، چیدمان و ترکیب اعضای مجموعههای متناهی میپردازد .
2جایگشت (Permutation): هر نوع چیدمان یا مرتبسازی از یک مجموعه اشیا که در آن ترتیب قرار گرفتن اشیا مهم باشد . در مسائل بدون تکرار، از جایگشت استفاده میشود.
