Комбинации

Комбинации използваме, когато от дадено множество от обекти избираме определен брой обекти, като редът, в който ги избираме, няма значение. Типична задача е тотото 6 от 49 – в урната има 49 числа и от тях теглим 6, като е все едно в какъв ред ги изтеглим.

Извеждане на формулата

Колело на късмета

Нека имаме някакво множество M, например M = {a, b, c, d, e}. Тогава комбинация от k-ти клас е подмножество K ⊆ M, което съдържа точно k елемента. Тъй като K е множество, редът, разбира се, няма значение. Следователно комбинация от трети клас на множеството M може да бъде {a, b, d} или {b, c, d}.

Разликата спрямо вариациите е, че при вариациите редът имаше значение, така че (a; b; e) и (e; b; a) са различни вариации, но са една и съща комбинация, защото и (a; b; e), и (e; b; a) съдържат едни и същи елементи; че са в различен ред, при комбинациите не ни интересува.

Можем обаче да използваме вариациите, за да получим формула за броя на всички различни комбинации. Знаем, че вариациите от k-ти клас на множество с n елемента са точно

$V_{n}^{k} = \frac{n!}{(n - k)!} .$

Ако пресметнем броя на всички вариации от трети клас на предишното множество M = {a, b, c, d, e}, ще получим $V_{5}^{3} = 60$ различни вариации. Но за всяка тройка там имаме и всичките ѝ пермутации. Т.е. имаме тройката abc, но и тройките acb, bac, bca, cab и cba. Това са шест различни вариации, но една комбинация, защото всички имат едни и същи елементи.

Ако имаме някаква тройка, колко различни пермутации на тази тройка съществуват? Точно 3!. С други думи, вариациите от трети клас са точно 3! пъти повече от комбинациите от трети клас. Вместо да броим една комбинация, броим 3! вариации – по една за всяка пермутация на дадената тройка. Затова ако разделим броя на вариациите на 3!, получаваме броя на комбинациите.

Горния подход можем да обобщим и да кажем, че ако търсим броя на всички различни комбинации от k-ти клас на множество с големина n, този брой, който ще означим с $C_{n}^{k}$ , е равен на

$C_{n}^{k} = \frac{V_{n}^{k}}{k!},$

т.е. броят на вариациите, делен на k!, което е броят на пермутациите на всяка k-торка. Формулата можем да преобразуваме, като разпишем формулата за вариациите:

$C_{n}^{k} = \frac{V_{n}^{k}}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Пример: броят на комбинациите от втори клас на множеството {a, b, c} е

$C_{3}^{2} = \frac{3!}{1! \cdot 2!} = 3$

и те са: {a, b}, {a, c} и {b, c}. За комбинациите от трети клас на първоначалното множество M = {a, b, c, d, e} бихме получили броя

$C_{5}^{3} = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

и те са: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

Биномен коефициент

Предишният запис на формулата чрез $C_{n}^{k}$ не се използва особено често и вместо него се използва т.нар. биномен коефициент. Той има следния вид

$(\binom{n}{k})$

и представлява нещо като дроб без дробна черта (която обаче по навик пак ще пишеш), но със скоби (те не са по желание, трябва да ги има). Биномния коефициент четем „ен над ка“. Стойността му е същата като на $C_{n}^{k}$ .

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

Така че ако имаме множество с 5 елемента и избираме четворки от него, общият им брой ще бъде

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Основни зависимости

За биномния коефициент и n ∈ ℕ е в сила:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Освен това за n, k ∈ ℕ₀ и k ≤ n е в сила

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

А за n, k ∈ ℕ₀ и k < n е в сила

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Калкулатор

Следният калкулатор пресмята биномния коефициент n над k.

Решени примери

Ще започнем с вече споменатото тото 6 от 49. В него от урна с 49 топки се теглят общо 6 топки. Колко различни възможности могат да бъдат изтеглени?

На първо място – редът на теглене на числата има ли значение? Няма, залагаме само числата, не и реда им. Ще използваме комбинации. Имаме общо 49 топки, теглим 6 топки, получаваме биномния коефициент

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13 983 816$

Съществуват общо 13 983 816 възможности, които могат да бъдат изтеглени. Това ни дава, между другото, вероятността за печалба при един залог 1/13 983 816, което е 0,00000715112%.
Стефан, известен сваляч, е на селски събор, където има общо 13 красиви момичета, които биха му харесали. Стефан знае, че за една вечер може да ухажва 4 различни момичета. От колко различни четворки може да избира Стефан?

Това е отново прост пример за комбинации, редът няма значение, Стефан ще е също толкова добър с първото момиче, колкото и с последното. Така получаваме множество от 13 момичета, от което всеки път избираме 4 момичета. Това води до биномния коефициент

$(\binom{13}{4}) = 715.$
Имаш група от петдесет души – половината мъже и половината жени. Колко са различните тройки от хора, ако не бива да се състоят само от един пол (т.е. в тройката не бива да има трима мъже или три жени)?

Това вече е малко по-сложна комбинация. Ако изключим тройките от един пол, остават само две възможности за състава на тройката – двама мъже и една жена или един мъж и две жени, като броят на комбинациите на първата група (двама мъже и една жена) ще бъде същият като броя на комбинациите на втората група. Достатъчно е да пресметнем броя на комбинациите на първата група и после да го умножим по две. Сега вече отново е лесно. Определяме броя на комбинациите на различните двойки мъже, което е двайсет и пет над две, и го умножаваме по броя на комбинациите на една жена (това прави двайсет и пет, вж. основните зависимости по-горе, по-точно втория ред). Този резултат вече само умножаваме по две и имаме крайния резултат.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
В кутия има 15 изделия, от които 4 са дефектни. По колко начина могат да се изберат 6 изделия така, че
- нито едно да не е дефектно? В този момент избираме 6 изделия от 15 − 4 = 11 изделия, които не са дефектни. Така получаваме биномния коефициент
  
  $(\binom{11}{6}) = 462.$
- точно едно изделие да е дефектно? Избираме множество, което съдържа 5 годни изделия и 1 дефектно. Годните изделия са общо 11, дефектните са 4. Използваме комбинаторното правило за умножение и получаваме резултата:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- най-много едно да е дефектно? За решението ще използваме предишните резултати. Знаем, че имаме 462 възможности да изберем точно 6 годни изделия и 1848 възможности да изберем пет годни и едно дефектно изделие. Използваме комбинаторното правило за събиране, събираме тези резултати и получаваме търсения резултат, т.е. най-много едно дефектно изделие (= или нито едно дефектно изделие, или точно едно). Резултатът е: 462 + 1848 = 2310.

Глави: Комбинаторика, Вариации, Пермутации, Комбинации, Вариации с повторение, Комбинации с повторение, Колко различни ПИН кода има?

« Предишна: Пермутации

Следваща: Вариации с повторение »