جلسهی 5: جایگشت: همهی ترتیبها Permutations: Every Order
چند جور میشود چند چیز را در یک ردیف چید؟ فاکتوریل، چیدن فقط چند تا، کلمههایی با حرف تکراری، میز گرد، و ترفند «چسباندن» دو نفری که باید کنار هم باشند.
در این جلسه یاد میگیری
- میدانی n چیز به n! ترتیب در یک ردیف میایستند.
- تعداد ترتیبهای چند تا از n چیز و ترتیب حرفهای یک کلمه با حرف تکراری را میشماری.
- ترتیب دور میز گرد و ترتیب با شرط «کنار هم» را میشماری.
درس
سه حیوان میخواهند برای عکس در یک ردیف بایستند: 🐱 🐶 🐭. به ترتیب روی آنها بزن تا بایستند. چند ترتیبِ متفاوت پیدا میکنی؟
به هر ترتیب از چند چیزِ متفاوت در یک ردیف «جایگشت» میگوییم. با اصل ضرب: جای اول ۳ انتخاب، جای دوم ۲، جای سوم ۱: ۳ × ۲ × ۱ = ۶. برای n چیز میشود n × (n−۱) × … × ۲ × ۱ که اسمش «n فاکتوریل» است و n! مینویسیم.
۱! = ۱، ۲! = ۲، ۳! = ۶، ۴! = ۲۴، ۵! = ۱۲۰، ۶! = ۷۲۰. ببین چقدر زود بزرگ میشود!
گاهی فقط چند جا داریم. از ۴ میوه، دو تا را به ترتیب در دو بشقاب (اول و دوم) بگذار. بشقاب اول ۴ انتخاب، بشقاب دوم ۳: ۴ × ۳ = ۱۲. امتحان کن:
حرفهای تکراری: کلمهی NOON چند ترتیبِ متفاوت دارد؟ اگر دو N و دو O با هم فرق داشتند، ۴! = ۲۴ ترتیب بود. ولی جابهجا کردن دو N چیزی را عوض نمیکند (۲! حالت یکی میشوند) و جابهجا کردن دو O هم (۲! حالت). پس ۲۴ ÷ (۲ × ۲) = ۶: NNOO، NONO، NOON، ONNO، ONON، OONN.
قانون: تعداد کل حرفها فاکتوریل، تقسیم بر فاکتوریلِ تعدادِ هر حرف تکراری.
میز گرد: ۴ نفر دور یک میز گرد. اگر همه یک صندلی بچرخند، باز همان نشستن است (هر کس همان همسایهها را دارد). پس هر ۴ ترتیبِ ردیفی که با چرخش به هم تبدیل میشوند یکیاند: ۴! ÷ ۴ = ۳! = ۶. برای n نفر: (n−۱)!. ترفند سادهتر: یک نفر را ثابت بنشان و بقیه را نسبت به او بچین.
ترفند چسب: ۵ نفر در یک ردیف، ولی علی و سارا باید کنار هم باشند. آن دو را با هم یک «بسته» فرض کن: حالا ۴ چیز داریم (بسته و ۳ نفر دیگر) که ۴! = ۲۴ ترتیب دارند. داخل بسته هم علیسارا یا ساراعلی: × ۲. جواب: ۴۸.
اشتباه رایج: فراموش کردن ترتیبِ داخل بسته.
چالشها
- Four for a Photo (آسان)
- Two-Letter Words (آسان)
- The Word LEVEL (متوسط)
- The Round Table (متوسط)
- Best Friends Side by Side (سخت)
- Keep the Twins Apart (سخت)
- Try It in Python: The Twins Apart (سخت)
← جلسهی 4: اصل جمع و اصل ضرب جلسهی 6: ترکیب: انتخاب گروه →