Комбинациялар
$n$ айырмаланган объекттен $k$ объектти тартипсиз тандоо (кайталоосуз)
1. Комбинация деген эмне?
Комбинация — бул чоңураак топтомдон кичи топтомду тандоо ыкмасы, мында топтун курамы гана маанилүү, элементтердин тандалган тартиби маанилүү эмес.
Негизги идея: $n$ элементтүү топтомдон $k$ элементтүү кичи топтомду тандаганда, биз кайсы элементтер тандалганына кызыгабыз, алар кандай тартипте тандалганына эмес.
Күнүмдүк мисалдар
- Комитеттер: 10 адамдан 3 адамды комитетке тандоо — {Айгүл, Бакыт, Чынара} тобу ким биринчи тандалганына карабастан бирдей.
- Карта колу: 52 карталуу калоддон 5 карталуу покер колу — {A♠, K♥, Q♦, J♣, 10♠} колу таратуу тартибине карабастан бирдей.
- Пицца кошумчалары: 8 кошумчадан 3 кошумчаны тандоо — пепперони-козу карын-зайтун пиццасы зайтун-пепперони-козу карын пиццасы менен бирдей.
- Лотерея сандары: 49 сандан 6 санды тандоо — утуш топтому тартылган тартибине карабастан бирдей.
Тартип маанилүү эмес
{A, B, C, D, E} топтомунан {A, B, C} тандоо:
| Жайгашуу | Бирдей комбинациябы? |
|---|---|
| A, B, C | ✓ Баары бирдей комбинация {A, B, C} |
| A, C, B | |
| B, A, C | |
| B, C, A | |
| C, A, B | |
| C, B, A |
Бул 6 = $3!$ жайгашуу баары бир комбинацияга айланат.
2. Комбинация формуласын чыгаруу
Кадам-кадам менен чыгаруу
Биз $n$ элементтен $k$ элементти тандап жайгаштыруу үчүн орун алмаштыруу формуласын билебиз:
$$ P(n,k) = \frac{n!}{(n-k)!} $$Эми, $k$ элементтен турган ар бир комбинацияны (тартипсиз топту) ички жактан кайра жайгаштырууга $k!$ жол бар. Демек, орун алмаштыруулардын жалпы саны комбинациялардын санын ички тартиптердин санына көбөйтүүгө барабар:
$$ P(n,k) = C(n,k) \times k! $$