Kombinacija

U matematici, kombinacije je način izbora elemenata iz kolekcije, tako da (za razliku od varijacija) redosled izbora nije važan.

Kombinacije bez ponavljanja

U kombinatorici, svaki podskup od k (k ≤ n) različitih elemenata skupa S od n elemenata zove se kombinacija bez ponavljanja k-te klase od n elemenata. Poredak elemenata nije važan u kombinacijama: dva podskupa koja imaju iste elemente u drugačijem poretku čine istu kombinaciju. Broj od k kombinacija C(n, k) skupa koji ima n elemenata je:

$C_k^n=(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}=\frac{n\cdot (n-1)\cdots (n-k+1)}{k\cdot (k-1)\cdots 1},n\ge k\ge 0,(n,k)\in N$,

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{P(n,k)}{P(k,k)},$

$P(n,k)=\frac{n!}{(n-k)!}$,

(vidi faktorijel)

sledi:

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!\cdot (n-k)!}.$

Takođe, broj $(\genfrac{}{}{0ex}{}{n}{k})$ naziva se binomni koeficijent. Treba uočiti da se $C_k^n$ može rešiti korišćenjem Paskalovog trougla.

Primer

Jedan dobar primer za razumevanje izračunavanja broja kombinacija bez ponavljanja je igra na sreću loto. Na primer, da bismo izračunali ukupan broj kombinacija lotoa u kom se od 39 mogućih brojeva izvlači 7 brojeva, primenjujemo formulu:

$C_7^{39}=(\genfrac{}{}{0ex}{}{39}{7})=\frac{39\cdot (39-1)\cdots (39-7+1)}{7\cdot (7-1)\cdots 1}=$

$=\frac{39\cdot 38\cdot 37\cdot 36\cdot 35\cdot 34\cdot 33}{7\cdot 6\cdot 5\cdot 4\cdot 3\cdot 2\cdot 1}=\frac{77.519.922.480}{5.040}=15.380.937$

Dakle, verovatnoća dobitka na lotou na kom se pogađa 7 od 39 brojeva je nešto manja od 1 prema 15 miliona.

Kombinacije sa ponavljanjem

Kombinacije k-te klase od n elemenata kod kojih se jedan element može do k puta ponavljati zovu se kombinacije s ponavljanjem k-te klase od n elemenata. Broj kombinacija s ponavljanjem je:

${\overline{C}}_k^n={\overline{C}}_k^{n+k-1}=(\genfrac{}{}{0ex}{}{n+k-1}{k})$,

uz uslov: $n\ge k\ge 0,(n,k)\in N$.

Povezano

• Kombinatorika
• Faktorijel

Reference

• Šablon:Citation
• Šablon:Citation
• Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
• Šablon:Citation
• Šablon:Citation

Vanjske veze

• Topcoder tutorial on combinatorics
• C code to generate all combinations of n elements chosen as k
• Many Common types of permutation and combination math problems, with detailed solutions
• The Unknown Formula For combinations when choices can be repeated and order does NOT matter
• Combinations with repetitions (by: Akshatha AG and Smitha B)Šablon:Dead link
• The dice roll with a given sum problem An application of the combinations with repetition to rolling multiple dice