Kombinatorika Pro I.
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^k\notag
\]
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.
Copyright © iMatek 2020-2025 – Minden jog fenntartva
