اصل ضرب – آنالیز ترکیبی (۱) – جلسهٔ اول

در این جلسه (ویدئوهای تدریس در ادامهٔ همین نوشته وجود دارد)، اصل ضرب بیان می‌شود و با حل مسئله‌های متنوع، روش‌های به‌کارگیری این اصل ضرب در حلّ مسائل شمارشی آموزش داده می‌شود.

اصل ضرب (صورت ساده)

فرض کنید نحوهٔ انجام کاری را بتوان به دو مرحله تجزیه کرد، مرحلهٔ او به \(m\) طریق و به‌ازای هر طریقِ نحوهٔ انجام مرحلهٔ اول، مرحلهٔ دوم به \(n\) طریق قابل انجام باشد. در این‌صورت، کل کار به \(m\times n\) طریق قابل انجام است.

اصل ضرب (صورت کلی)

فرض کنید نحوهٔ انجام کاری را بتوان به \(k\) مرحله تجزیه کرد. مرحلهٔ اول به \(n_1\) طریق قابل انجام باشد و به‌ازای هر \(i\)، \(2\leq i\leq k\)، مرحلهٔ \(i\)اُم مستقل از نحوهٔ انجام مراحل اول تا \((i-1)\)اُم به \(n_i\) طریق قابل انجام باشد. در این‌صورت، کل کار به \(n_1n_2\dots n_k\) طریق قابل انجام است.

نمونه‌ای از مسائل حل شده در این جلسه

1. یک مورچه روی رأس \(A\) از مربع \(ABCD\) قرار دارد. این مورچه هر دقیقه از یک رأس به یکی از رأس‌های مجاور می‌رود. این مورچه به چند طریق می‌تواند حرکت کند به‌گونه‌ای که در پایان دقیقهٔ هفتم روی رأس \(B\) باشد؟
2. یک آرایش مثلثی شامل \(6\) ردیف از توپ‌ها داده شده است. (در ردیف پایین \(6\) توپ، ردیف بالای آن \(5\) توپ، \(\dots\)، و ردیف بالا یک توپ قرار دارد و هر توپ روی دو توپ از ردیف پایینی قرار دارد.) به چند طریق می‌توان توپ‌ها را به \(6\) دسته تقسیم کرد به‌طوری که دستهٔ \(i\)اُم شامل \(i\) توپ باشد که همگی روی یک خط موازی یکی از اضلاع مثلث قرار داشته باشند؟ \((1\leq i\leq 6)\)
3. دو خانه اول از سطر اول یک جدول \(8\times8\) سیاه شده‌اند. به چند طریق می‌توان بقیه خانه‌های این جدول را سیاه و سفید کرد به‌گونه‌ای که در هر مربع \(2\times2\) از جدول، \(2\) خانهٔ سیاه و \(2\) خانهٔ سفید وجود داشته باشد؟
4. جدول \(3\times100\) را به چند طریق می‌توان با موزاییک‌هایی به شکل زیر، فرش کرد؟
   
5. در چند عدد \(5\) رقمی با رقم‌های ناصفر و متمایز، هر دو رقم نسبت‌‌به‌هم اول‌اند؟
   (دو عدد صحیح نسبت‌به‌هم اول‌اند اگر ب‌م‌م آنها برابر \(1\) باشد، یا معادلاً مقسوم‌علیه مشترکی بزرگ‌تر از \(1\) نداشته باشند.)

6. در هر خانهٔ سیاه از یک صفحهٔ شطرنجی \(4\times4\) یک مهرهٔ اسب قرار دارد. به چند طریق می‌توان هر مهرهٔ اسب را یک‌بار حرکت داد به‌گونه‌ای که در وضعیت جدید در هر خانهٔ سفید، یک مهره قرار داشته باشد؟

ویدئوهای جلسهٔ اول

فایل تختهٔ کلاس

دانلود فایل PDF کلاس

تکالیف جلسهٔ اول

کتاب آنالیز ترکیبی: مطالعهٔ صفحهٔ ۲ تا ۷، صفحهٔ ۸ مسائل ۱ تا ۱۵، ۱۷، ۲۱ تا ۳۲
کتاب روش‌های ترکیبیات ۱: صفحهٔ ۵ مسائل ۱، ۲، ۵ تا ۹، ۱۵

پرسش و پاسخ

سؤالاتتان دربارهٔ مسائل و محتوای تدریس شده در این جلسه را می‌توانید در بخش کامنت‌های زیر مطرح کنید.