Комбинация (математика)

В комбинаториката, комбинацията е начин за избиране на елементи от множество. Избирането може да стане с повторение или без повторение, т.е. с връщане на избраните елементи в началното множесто или с изваждането им от него. При втория случай, а именно без повторение, комбинация на n елемента от k-ти клас, се нарича кое да е подмножество от k, т.е. k ≤ n различни елемента избрани измежду n дадени елемента, в което местата на избраните елементи е без значение.

Комбинации без повторение

Броят на комбинациите без повторение на n елемента от k-ти клас се означава с $\mathbf {C} _{n}^{k}$ или C(n,k) и е равен на биномния коефициент n над k:

$\mathbf {C} _{n}^{k}=\mathbf {C} (n,k)={n \choose k}={\frac {n!}{k!(n-k)!}}.$

Комбинациите на k елемента от множество с n елемента се отнасят до броя на всички възможни различни групи от по k елемента които могат да бъдат получени при произволно избиране без повторение.

Комбинации с повторение

Сега нека разгледаме какъв ще е броят на всички възможни различни групи от по к елемента, ако след всяко избиране ги връщаме обратно в началното множество n. В такъв случай броят на комбинациите с повторение на n елемента от k- ти клас се означава с Неуспех при разбора (синтактична грешка): {\displaystyle \mathbf{C}_n^k = \mathbf{C}_{n + k – 1}^k} и е равен на

Неуспех при разбора (синтактична грешка): {\displaystyle \mathbf{C}_n^k = \mathbf{C}_{n + k – 1}^k = {n + k – 1\choose k} = \frac{(n + k – 1)!}{k!(n – 1)!}}

където k е броят на повтарящите се елементи.

По-общо, комбинация от n неща, взети по групи от k всеки път, често биват наричани k комбинации от n неща, е начин да изберем подмножество от k от дадено множество с размер n. И както вече научихме съществуват точно ${n \choose k}$ начина това да бъде осъществено. Избирането на k посочени елемента от n елемента е еквивалентно на избирането на останалите n – k непосочени. Ако обозначим непосочените елементи с s, то тогава тази симетрия може да бъде изразена чрез изразът:

$n=s+t$

и тогава k комбинации от n елемента могат да бъдат записвани като "(s, k) комбинации". По този начин (s, k) – комбинация е начин за раздреляне на n елемента в две групи с размер s и k.

Когато питам колко комбинации от 21 елемента могат да бъдат взети от 25.
Аз всъщност питам колко комбинации от 4 могат да бъдат взети.
Защото броя на начините за взимане на 21 е равен не броя на начините на оставяне на 4 елемента.

“

”

An essay on Probabilities, 1838

Примери

Пример 1.

Да се пресметне колко различни групи от по трима човека могат да бъдат образувани от дадена група състояща се от седем човека. Броят на възможните групи представлява броят на комбинациите на 7 елемента от 3-ти клас и се пресмята както следва:

${7 \choose 3}={\frac {7!}{3!(7-3)!}}={\frac {7\cdot 6\cdot 5\cdot 4!}{3!\cdot 4!}}={\frac {7\cdot 6\cdot 5}{3!}}={\frac {7\cdot 6\cdot 5}{6}}=7\cdot 5=35.$

Пример 2.

В играта 6 от 49 за да спечелим джакпот трябва числата от попълнен фиш да отговарят на изтеглените числа. Да се пресметне колко фиша трябва да попълним за да сме сигурни, че ще спечелим джакпот. Броят на фишовете в които са изброени всички възможни комбинации от 6 числа от 1 до 49 можем да изчислим с помощта на:

${n \choose k}={n! \over k!(n-k)!}$.

където n = 49 и k = 6, от където следва:

${49 \choose 6}={49! \over 6!(49-6)!}=13,983,816$

в последното уравнение, 49! представлява броят на начините по които могат да бъдат наредени числата от 1 до 49, т.е пермутациите на числото 49, които се пресмятат с помощта на факториел или 49! = 1 × 2 × 3 ×...× 49. В знаменателят, първия член, 6!, представлява всички начини по които шест числа могат да бъдат наредени, но поради факта, че местата на избраните елементи или в нашия случай редът на изтеглянето е без значение, ние делим на това число. Вторият член, представлява броят на възможните начини по които могат да останат 49 числа след като изберем и извадим 6 от тях, т.е. 43!. И така, съществуват 13,983,816 начина по които 6 числа могат да бъдат изтеглени от 49, което е и търсеният брой на фишовете.

Източници

1. Брадистилов Г. Д. Висша математика, С. Техника, 1965 г. 36-38 с.

Вижте също

Пермутация

Комбинаторика