بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 5: جایگشت: همه‌ی ترتیب‌ها Permutations: Every Order

چند جور می‌شود چند چیز را در یک ردیف چید؟ فاکتوریل، چیدن فقط چند تا، کلمه‌هایی با حرف تکراری، میز گرد، و ترفند «چسباندن» دو نفری که باید کنار هم باشند.

در این جلسه یاد می‌گیری

درس

سه حیوان می‌خواهند برای عکس در یک ردیف بایستند: 🐱 🐶 🐭. به ترتیب روی آن‌ها بزن تا بایستند. چند ترتیبِ متفاوت پیدا می‌کنی؟

به هر ترتیب از چند چیزِ متفاوت در یک ردیف «جایگشت» می‌گوییم. با اصل ضرب: جای اول ۳ انتخاب، جای دوم ۲، جای سوم ۱: ⁦۳ × ۲ × ۱ = ۶⁩. برای n چیز می‌شود ⁦n × (n−۱) × … × ۲ × ۱⁩ که اسمش «n فاکتوریل» است و ⁦n!⁩ می‌نویسیم.
⁦۱! = ۱⁩، ⁦۲! = ۲⁩، ⁦۳! = ۶⁩، ⁦۴! = ۲۴⁩، ⁦۵! = ۱۲۰⁩، ⁦۶! = ۷۲۰⁩. ببین چقدر زود بزرگ می‌شود!

گاهی فقط چند جا داریم. از ۴ میوه، دو تا را به ترتیب در دو بشقاب (اول و دوم) بگذار. بشقاب اول ۴ انتخاب، بشقاب دوم ۳: ⁦۴ × ۳ = ۱۲⁩. امتحان کن:

حرف‌های تکراری: کلمه‌ی NOON چند ترتیبِ متفاوت دارد؟ اگر دو N و دو O با هم فرق داشتند، ⁦۴! = ۲۴⁩ ترتیب بود. ولی جابه‌جا کردن دو N چیزی را عوض نمی‌کند (⁦۲!⁩ حالت یکی می‌شوند) و جابه‌جا کردن دو O هم (⁦۲!⁩ حالت). پس ⁦۲۴ ÷ (۲ × ۲) = ۶⁩: NNOO، NONO، NOON، ONNO، ONON، OONN.
قانون: تعداد کل حرف‌ها فاکتوریل، تقسیم بر فاکتوریلِ تعدادِ هر حرف تکراری.

میز گرد: ۴ نفر دور یک میز گرد. اگر همه یک صندلی بچرخند، باز همان نشستن است (هر کس همان همسایه‌ها را دارد). پس هر ۴ ترتیبِ ردیفی که با چرخش به هم تبدیل می‌شوند یکی‌اند: ⁦۴! ÷ ۴ = ۳! = ۶⁩. برای n نفر: ⁦(n−۱)!⁩. ترفند ساده‌تر: یک نفر را ثابت بنشان و بقیه را نسبت به او بچین.

ترفند چسب: ۵ نفر در یک ردیف، ولی علی و سارا باید کنار هم باشند. آن دو را با هم یک «بسته» فرض کن: حالا ۴ چیز داریم (بسته و ۳ نفر دیگر) که ⁦۴! = ۲۴⁩ ترتیب دارند. داخل بسته هم علی‌سارا یا ساراعلی: × ۲. جواب: ۴۸.
اشتباه رایج: فراموش کردن ترتیبِ داخل بسته.

چالش‌ها

  1. Four for a Photo (آسان)
  2. Two-Letter Words (آسان)
  3. The Word LEVEL (متوسط)
  4. The Round Table (متوسط)
  5. Best Friends Side by Side (سخت)
  6. Keep the Twins Apart (سخت)
  7. Try It in Python: The Twins Apart (سخت)

← جلسه‌ی 4: اصل جمع و اصل ضرب جلسه‌ی 6: ترکیب: انتخاب گروه →