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

جلسه‌ی 6: ترکیب: انتخاب گروه Combinations: Choosing a Group

وقتی ترتیب مهم نیست، فقط «چه کسانی» مهم است. انتخاب k نفر از n نفر، دست دادن‌ها و قطرهای چندضلعی، مثلث خیام‌پاسکال، و کمیته‌هایی با شرط.

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

درس

از ۵ دوست باید ۲ نفر برای تیم انتخاب شوند. روی آن‌ها بزن و گروه بساز. اگر 🐼🦊 را انتخاب کنی و بعد 🦊🐼، گروه تازه‌ای نساخته‌ای! چند گروهِ متفاوت هست؟

اگر ترتیب مهم بود (کاپیتان و معاون)، ⁦۵ × ۴ = ۲۰⁩ حالت داشتیم. ولی در گروه ترتیب مهم نیست و هر گروهِ دونفره دو بار شمرده شده: ⁦۲۰ ÷ ۲ = ۱۰⁩.
در حالت کلی، تعداد انتخاب k چیز از n چیز را «ترکیب n و k» می‌گوییم و ⁦C(n, k)⁩ می‌نویسیم:
⁦C(n, k)⁩ = (تعداد ترتیب‌های k تا از n) ÷ k!
مثلاً ⁦C(۶, ۳) = (۶ × ۵ × ۴) ÷ (۳ × ۲ × ۱) = ۲۰⁩.

دو استفاده‌ی معروف:
🤝 دست دادن: n نفر هر کدام یک بار با هر نفر دیگر دست می‌دهند. هر دست دادن یعنی انتخاب ۲ نفر: ⁦C(n, ۲) = n × (n−۱) ÷ ۲⁩. برای ۱۰ نفر: ۴۵.
🔷 قطرهای چندضلعی: هر دو رأس یک پاره‌خط می‌سازند: ⁦C(n, ۲)⁩. ولی n تا از آن‌ها ضلع‌اند، نه قطر: قطرها = ⁦C(n, ۲) − n⁩. شش‌ضلعی: ⁦۱۵ − ۶ = ۹⁩.
یک نکته‌ی قشنگ: انتخاب k نفر برای تیم همان انتخاب ⁦n − k⁩ نفرِ بیرون است، پس ⁦C(n, k) = C(n, n − k)⁩.

مثلث خیام‌پاسکال: هر عدد = جمع دو عددِ بالای سرش. سطر n عددهای ⁦C(n, ۰)⁩، ⁦C(n, ۱)⁩، … است. چرا؟ برای انتخاب k نفر از n نفر، به یک نفر مثل علی نگاه کن: یا علی در گروه است (باید ⁦k − ۱⁩ نفر دیگر از ⁦n − ۱⁩ نفر انتخاب کنی) یا نیست (k نفر از ⁦n − ۱⁩). پس ⁦C(n, k) = C(n−۱, k−۱) + C(n−۱, k)⁩. همین جمع زدن را در شمردن مسیرها هم می‌بینی!

کمیته با شرط: از ۵ پسر و ۴ دختر، یک کمیته‌ی ۳ نفره.
«دقیقاً یک دختر»: یک دختر از ۴ (۴ حالت) و دو پسر از ⁦۵ (C(۵, ۲) = ۱۰)⁩: ⁦۴ × ۱۰ = ۴۰⁩.
«دست‌کم یک دختر»: باز ترفند «همه منهای هیچ‌کدام»: همه ⁦C(۹, ۳) = ۸۴⁩، بدون دختر ⁦C(۵, ۳) = ۱۰⁩، جواب ۷۴.
اشتباه رایج برای «دست‌کم یک دختر»: «یک دختر انتخاب کن (۴ حالت)، بعد ۲ نفر از ۸ نفرِ باقی ⁦(۲۸)⁩» = ۱۱۲. این غلط است چون کمیته‌هایی که دو دختر دارند چند بار شمرده می‌شوند.

چالش‌ها

  1. Cleaning Duty (آسان)
  2. Seven Friends Shake Hands (آسان)
  3. Octagon Diagonals (متوسط)
  4. Exactly One Girl (متوسط)
  5. At Least One Girl (سخت)
  6. Cutting a Stamp Sheet (سخت)

← جلسه‌ی 5: جایگشت: همه‌ی ترتیب‌ها جلسه‌ی 7: مسیرها روی جدول →