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[1]. 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 = ( n k ) = n ! k ! ( n − k ) ! = n ⋅ ( n − 1 ) ⋯ ( n − k + 1 ) k ⋅ ( k − 1 ) ⋯ 1 , n ≥ k ≥ 0 , ( n , k ) ∈ N {\displaystyle C_{k}^{n}={n \choose k}={\frac {n!}{k!(n-k)!}}={\frac {n\cdot (n-1)\cdots (n-k+1)}{k\cdot (k-1)\cdots 1}},\quad n\geq k\geq 0,\quad (n,k)\in N} ,
( n k ) = P ( n , k ) P ( k , k ) , {\displaystyle {n \choose k}={\frac {P(n,k)}{P(k,k)}},}
P ( n , k ) = n ! ( n − k ) ! {\displaystyle P(n,k)={\frac {n!}{(n-k)!}}} ,
(vidi faktorijel)

sledi:

( n k ) = n ! k ! ⋅ ( n − k ) ! . {\displaystyle {n \choose k}={\frac {n!}{k!\cdot (n-k)!}}.}

Takođe, broj ( n k ) {\displaystyle \quad {n \choose k}\quad } naziva se binomni koeficijent. Treba uočiti da se C k n {\displaystyle 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 = ( 39 7 ) = 39 ⋅ ( 39 − 1 ) ⋯ ( 39 − 7 + 1 ) 7 ⋅ ( 7 − 1 ) ⋯ 1 = {\displaystyle C_{7}^{39}={39 \choose 7}={\frac {39\cdot (39-1)\cdots (39-7+1)}{7\cdot (7-1)\cdots 1}}=}
= 39 ⋅ 38 ⋅ 37 ⋅ 36 ⋅ 35 ⋅ 34 ⋅ 33 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 77.519.922.480 5.040 = 15.380.937 {\displaystyle ={\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.[1] Broj kombinacija s ponavljanjem je:

C ¯ k n = C ¯ k n + k − 1 = ( n + k − 1 k ) {\displaystyle {\bar {C}}_{k}^{n}={\bar {C}}_{k}^{n+k-1}={n+k-1 \choose k}\quad } ,[1]
uz uslov: n ≥ k ≥ 0 ,   ( n , k ) ∈ N {\displaystyle n\geq k\geq 0,\ (n,k)\in N} .

Vidi još

  • Kombinatorika
  • Faktorijel

Reference

  1. ↑ 1,0 1,1 1,2 Mr Vene T. Bogoslavov, Zbirka rešenih zadataka iz matematike IV, XXI izdanje, 1986. godina, Zavod za udžbenike i nastavna sredstva, Beograd

Reference

  • Benjamin, Arthur T.; Quinn, Jennifer J. (2003), Proofs that Really Count: The Art of Combinatorial Proof, The Dolciani Mathematical Expositions 27, The Mathematical Association of America, ISBN 978-0-88385-333-7 
  • Brualdi, Richard A. (2010), Introductory Combinatorics (5th izd.), Pearson Prentice Hall, ISBN 978-0-13-602040-0 
  • Erwin Kreyszig, Advanced Engineering Mathematics, John Wiley & Sons, INC, 1999.
  • Mazur, David R. (2010), Combinatorics: A Guided Tour, Mathematical Association of America, ISBN 978-0-88385-762-5 
  • Ryser, Herbert John (1963), Combinatorial Mathematics, The Carus Mathematical Monographs 14, Mathematical Association of America 

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)[mrtav link]
  • The dice roll with a given sum problem An application of the combinations with repetition to rolling multiple dice