combinatorics

combinatorics (tsz. combinatoricses)

1. (informatika) kombinatorika

A kombinatorika a diszkrét matematika egyik ága, amely véges (vagy megszámlálható) halmazok elemeinek kiválasztási, rendezési, csoportosítási lehetőségeivel foglalkozik. Alkalmazzák algoritmusok, gráfelmélet, valószínűségszámítás, számítástudomány és kriptográfia területén is.

1. Hányféleképpen választhatunk ki elemeket adott feltételek mellett?
2. Hányféleképpen rendezhetők el az elemek?
3. Mi változik, ha számít a sorrend vagy ismétlődhetnek az elemek?

Hányféleképpen rendezhető el n különböző elem?

Képlet:

P(n) = n!

Példa: 3 elem (A, B, C) → 3! = 6 sorrend: ABC, ACB, BAC, BCA, CAB, CBA

Hányféleképpen választhatunk ki k elemet n-ből, ha sorrend számít?

Képlet:

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

Példa: Hányféleképp választhatunk ki 2 betűt 4-ből (A, B, C, D) sorrendesen? V(4, 2) = 4×3 = 12

Hányféleképpen választhatunk ki k elemet n-ből, ha nem számít a sorrend?

Képlet:

C(n, k) = \binom{n}{k} = \frac{n!}{k!(n - k)!}

Példa: 4 diák közül válasszunk ki 2-t egy projektcsoportra → C(4, 2) = 6

Hányféleképpen választhatunk ki k elemet n típusból, ismétléssel, sorrend nem számít?

Képlet:

\binom{n + k - 1}{k}

Példa: Válasszunk 3 fagyit 2 ízből (pl. csoki és vanília, lehet 3 csoki is): ${\textstyle {\binom {2+3-1}{3}}={\binom {4}{3}}=4}$

n elem, de vannak benne azonosak – hány különböző sorrend létezik?

Képlet:

\frac{n!}{k_1! \cdot k_2! \cdot \ldots \cdot k_m!}

Példa: Hány különböző sorrendje van az „ANA” szónak?

3 betű, 2 A → ${\textstyle {\frac {3!}{2!1!}}=3}$

Ha egy feladat több lépésből áll, és az első lépésnek n₁, a másodiknak n₂ lehetősége van:

\text{Összes lehetőség} = n_1 \times n_2 \times \ldots \times n_k

Ha az egyik vagy a másik lehetőség történhet meg:

\text{Összes lehetőség} = n_1 + n_2 + \ldots + n_k

A kombinatorika adja az alapot a klasszikus valószínűségszámításhoz:

P = \frac{\text{kívánt esetek száma}}{\text{összes esetek száma}}

1. Hányféleképp ülhet le 5 ember 5 székre?
   • 5! = 120
2. Hányféleképp választhatunk 3 könyvet 10-ből, ha nem számít a sorrend?
   • ${\textstyle {\binom {10}{3}}=120}$
3. Hány háromjegyű szám alkotható 1–9 számjegyekből, ha nem ismétlődhetnek?
   • V(9, 3) = 9×8×7 = 504

• Kriptográfia – kulcsok száma
• Játéktervezés – lehetséges játékállások
• Adattömörítés – kódlehetőségek
• Bioinformatika – génkombinációk
• Valószínűségi modellek – kártyajátékok, dobókockák, szerencsejátékok

• combinatorics - Szótár.net (en-hu)
• combinatorics - Sztaki (en-hu)
• combinatorics - Merriam–Webster
• combinatorics - Cambridge
• combinatorics - WordNet
• combinatorics - Яндекс (en-ru)
• combinatorics - Google (en-hu)
• combinatorics - Wikidata
• combinatorics - Wikipédia (angol)