Online matek érettségi és felvételi felkészítő

Kombinatorika

Az emelt szintű matematika kombinatorika témakörében a következő alapfogalmak, tételek és elméletek szerepelnek:

1. Permutáció
A permutáció adott elemek sorrendjének megváltoztatása. Ha egy ( n ) elemű halmaz összes elemét rendezzük, a lehetséges sorrendek száma ( n! ) (n faktoriális). Ha ( k ) elemet azonos a halmazban, akkor az ismétlés nélküli permutációk száma:
[
P_n^{k,i} = frac{n!}{k!}notag
]

2. Variáció
A variációk rendezett részhalmazokat képeznek. Ismétlés nélküli variáció esetén ( n ) elemből ( k )-t választunk, és a sorrend számít. A képlet:
[
V_n^{k,i} = frac{n!}{(n-k)!}notag
]
Ismétléses variációnál minden elem többször is szerepelhet, ekkor a variációk száma ( n^k ).

3. Kombináció
A kombinációk rendezetlen részhalmazokat képeznek. Ismétlés nélküli kombinációk esetén ( n ) elemből ( k )-t választunk ki, ahol a sorrend nem számít. A számítás alapképlete:
[
C_n^k = binom{n}{k} = frac{n!}{k!(n-k)!}notag
]
Ismétléses kombináció esetén a képlet:
[
C_n^{k,i} = binom{n+k-1}{k}notag
]

4. Szita-formula (Inklúzió-exklúzió elv)
A szita-formula lehetővé teszi, hogy különböző halmazok metszetei alapján meghatározzuk az egyesített halmaz elemeinek számát. A két halmazra alkalmazott formula:
[
|A cup B| = |A| + |B| – |A cap B|notag
]
Több halmaz esetén a formula kiterjeszthető, hogy figyelembe vegye a különböző metszeteket.

5. Kombinatorikus geometria
Ez a terület a geometriai objektumok diszkrét tulajdonságaival foglalkozik, például pontok, egyenesek és sokszögek elhelyezkedésével és viszonyaival. Ilyen probléma lehet például a síkban lévő pontok összekötéséből kialakuló egyenesek száma.

6. Stirling-számok
A Stirling-számok két típusra oszlanak:
– Az elsőfajú Stirling-számok a ciklusokba rendezett elemek számát adják meg.
– A másodfajú Stirling-számok azt adják meg, hogy ( n ) elemet hányféleképpen lehet ( k ) nem üres halmazra osztani.

7. Bell-számok
A Bell-számok azt jelölik, hogy egy ( n ) elemű halmaz hányféleképpen osztható fel nem üres részhalmazokra. A Bell-számok rekurzív formulával számíthatók.

8. Binomiális együtthatók és binomiális tétel
A binomiális együtthatók a ( binom{n}{k} ) kifejezésben szerepelnek, és a kombinációk számát adják meg. A binomiális tétel:
[
(a + b)^n = sum_{k=0}^{n} binom{n}{k} a^{n-k} b^knotag
]

9. Pascal-háromszög
A Pascal-háromszög egy táblázat, amelyben a binomiális együtthatók szerepelnek. Minden sor az előző sor értékeinek összege alapján épül fel és egy nevezetes összefüggést szemléltet:
[
binom{n}{k} = binom{n-1}{k-1} + binom{n-1}{k}notag
]

10. Catalan-számok
A Catalan-számok fontosak a kombinatorikus problémákban, például korrekt zárójelezések, konvex sokszögek és bináris fák számolásában. A ( n )-edik Catalan-szám képlete:
[
C_n = frac{1}{n+1} binom{2n}{n}notag
]
Ez a szám számos különféle kombinatorikus objektum számát adja meg, mint például a konvex sokszög átlóinak számát vagy a korrekt zárójelek párosítási lehetőségét.