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

В комбинаториката, комбинацията е начин за избиране на елементи от множество. Избирането може да стане с повторение или без повторение, т.е. с връщане на избраните елементи в началното множесто или с изваждането им от него. При втория случай, а именно без повторение, комбинация на 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- ти клас се означава с $\mathbf {C} _{n}^{k}=\mathbf {C} _{n+k-1}^{k}$ и е равен на

$\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)!}=13983816$.

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

При обикновен запис и фишове с по 4 комбинации всеки, трябва да се попълнят 13983816:4 = 3 495 954 фиша. Ако се използват системи за пълно комбиниране и съкратено записване, броят на фишовете намалява. Например при система с 10 числа пълно комбиниране броят на комбинациите е

${49 \choose 10}={49! \over 10!(49-10)!}=8217822536.$

За тяхното попълване са необходими 8 217 822 536 : 4 = 2 054 455 634 фиша.

Източници

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

Вижте също

Пермутация

Вариация

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