Kombinatorika

szerkesztés
Isten hozott a Mátrixban!

A kombinatorika a matematika egyik tudományága. Röviden úgy foglalhatjuk össze, mint a véges halmazok tartalmazkodási és számossági viszonyainak vizsgálatát; noha e meghatározás nem egészen pontos (a kombinatorika számára a végtelen halmazok is érdekese).

A kombinatorika, dacára annak, hogy a matematika látszólag legegyszerűbb struktúráit, a véges struktúrákat vizsgálja, mint tudományág, nagyon fiatal. Első komolyabb eredményei (a kombinációk vizsgálata) a valószínűségszámítással kapcsolatban már a tizenhetedik században megszülettek, de aztán csak a tizenkilencedik-huszadik században történt jelentősebb előrelépés.

E munkában elég elemi, általános iskolás szintről kiindulva kezdünk a tárgyalásába (noha a tárgyalásmódban, elsősorban a felépítés részletességében, precizitásában e szintet már a kezdet kezdetén jóval meghaladjuk).

Elemi kombinbatorika

szerkesztés
    1. Sorbarendezések
    2. Permutációk, variációk
    3. Kombinációk
    4. Ismétléses kombináció
    5. Fák
    6. Gráfok
    7. Halmazrendszerek alapjai

Hivatkozások

szerkesztés
  • Vilenkin: Kombinatorika
  • Lovász-satöbbi: Kombinatorika
  • Lovász: Kombinatorika Példatár
  • meg ilyesmik

Hivatkozások

szerkesztés

Bevezető feladatok

szerkesztés

Feladat: Kockafej Úr diplomatatáskája számzáras. A zár négy forgatható tárcsából áll, minden tárcsa egymástól függetlenül tízféle helyzetbe forgatható (0,1,2,3,4,5,6,7,8,9). A táska nyitása csak akkor lehetséges, ha a tárcsákat egy megfelelő, a táskéára jellemző helyzetbe forgatják (pl. az első tárcsa 4-es jegye a második 5-öse, a harmadik 6-osa és a negyedik 0-a mellé kerüljön; azaz a kód mondjuk 4560). Kockafej Úr elfelejtette a kódot.

  1. A) Hányféle kódot kell kipróbálnia, ha biztosan ki akarja nyitni a táskát?
  2. B) Hányadrészére csökken a szükséges próbálkozások száma, ha az utolsó sz ámjegyre emlékszik (mondjuk 0).
  3. C) Hányadrászére csökken a próbálkozások száma, ha minden tárcsán csak négy jegy van (0,1,2,3)?
  • (Mekkora az esélye, hogy a k-adik próbálkozásra nyíljon?)

Megj. A)B) 10-edrendű 4 ill 3 osztályú variációk. C negyedrendű permutációk.

Bonyolultabb feladat: lottó- és totószelvény.