جلسهی 6: ترکیب: انتخاب گروه Combinations: Choosing a Group
وقتی ترتیب مهم نیست، فقط «چه کسانی» مهم است. انتخاب k نفر از n نفر، دست دادنها و قطرهای چندضلعی، مثلث خیامپاسکال، و کمیتههایی با شرط.
در این جلسه یاد میگیری
- فرق ترتیب (جایگشت) و گروه (ترکیب) را میدانی.
- تعداد انتخاب 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(۵, ۳) = ۱۰، جواب ۷۴.
اشتباه رایج برای «دستکم یک دختر»: «یک دختر انتخاب کن (۴ حالت)، بعد ۲ نفر از ۸ نفرِ باقی (۲۸)» = ۱۱۲. این غلط است چون کمیتههایی که دو دختر دارند چند بار شمرده میشوند.
چالشها
- Cleaning Duty (آسان)
- Seven Friends Shake Hands (آسان)
- Octagon Diagonals (متوسط)
- Exactly One Girl (متوسط)
- At Least One Girl (سخت)
- Cutting a Stamp Sheet (سخت)
← جلسهی 5: جایگشت: همهی ترتیبها جلسهی 7: مسیرها روی جدول →