1. Kombinatorika

Question 1

ismétlés nélküli permutáció

Answer 1

Tetszőleges $n \epsilon \natnums$ természetes szám esetén n különböző elem összes lehetséges sorbarendezéseinek számát n elem ismétlés nélküli permutációjának hívjuk és $P_n$-el jelöljük.
n!

Question 2

ismétléses permutációjának

Answer 2

Ha az elemek között azonosak is lehetnek, méghozzá összesen s féle és az egyes típusokból rendre $k_1,… k_s$ van ($k_1+…+k_s =n$), akkor az összes lehetséges sorbarendezésnek számát n elem s-edrendű ismétléses permutációjának hívjuk, és $P_n^ {k_1…k_s(ism)}$-el jelöljük (generalised perm.)
(n!)/(k_1!…k_s!)

Question 3

ismétléses variáció

Answer 3

Ha a kihúzás visszatevéses, akkor ismétléses variációról beszélünk, $V_n ^{k(ism)}$ -el jelöljük és ismét a kihúzott elemek kihúzásának sorrendje számít.
n^k

Question 4

ismétlés nélküli variáció

Answer 4

Tetszőleges $n, k \epsilon \N$ esetén n különböző elem halmazából k elem visszatevés nélküli mintavételeinek összes lehetséges számát n elem k-adrendű (ismétlés/visszatevés nélküli) vagy egyszerűen csak variációjának nevezzük, ha a kihúzott elemek kihúzásának sorrendje lényeges és $V_n ^{k}$-el jelöljük.
n(n-1)…(n-k+1)

Question 5

ismétléses kombináció

Answer 5

(n+k-1 alatt a k)

Question 6

ismétlés nélküli kombináció

Answer 6

Ha a fenti definícióban az elemek kihúzásának sorrendje lényegtelen, akkor az n elem k-adrendű (ismétlés/visszatevés nélküli) vagy egyszerűen csak kombinációjáról beszélünk és $C_n ^{k(ism)}$-val jelüljük. A másik esetben ismétléses komcinációról van szó, amit $C_n ^{k(ism)}$-el jelölünk.
n alatt a k

Question 7

Stirling formula

Answer 7

Megadja az n! nagyságrendjét elég pontosan. Elsősorban a binomiális együtthatók ($(_k^{n})$és $_ \frac{n}{k} ^{n}$) értékének, valamint az $O(2^{n}) $ és $O(n!)$ futásidejű algoritmusok összehasonlytására használjuk

Question 8

Binomiális együtthatók tulajdonságai

Question 9

Binomiális együttható

Answer 9

Tetszőleges $n, k \epsilon \N$ eseten bevezetjük a következő jelölést:
$(_ {k}^{n}) := C_n^{k} = \frac{n(n-1)…*(n-k+1)}{k!}$
amit binomiális együtthatónak nevezünk és “n alatt a k”-nak olvassuk (n elem k-tagú ismétlés nélküli kombinációja)

Question 10

Polinomiális együttható

Answer 10

Tetszőleges $n, k_1,…k_s, s \epsilon \natnums$ $k_1+…+k_s$ esetén a

$( _ {k_1,…,k_s}^{n} ) := \frac{n!}{k_1,…,k_s}$

kifejezést polinomiális együtthatónak nevezzük.

Question 11

Zárt formula $Σi^k
$ -ra

Answer 11

Bármely k eleme N-re létezik P_k(x)(k+1)-ed fokú polinom, amelyre 1^k + 2^k + … + n^k = \sum ^n_{i=0} i^k = P_k(n)

Question 12

Pascal háromszög

Answer 12

A Pascal-háromszög segítségével egyszerűen felirható az $(a+b)^n$ bármilyen n hatványon.

Question 13

Binomiális tétel

Answer 13

Binomiális tétel: Tetszőleges $a, b \epsilon \cnums$ és $n \epsilon \N$ esetén

$(a+b)^{n} = \sum_{i=0}^{n} (_i^{n}) * a^{i} * b^{n-i}$

Question 14

Polinomiális tétel

Answer 14

Polinomiális tétel: Tetszőleges $a_1,…,a_s \epsilon \cnums$ és $s,n \epsilon \N$ esetén fennál az:

$(a_1+…+a_s)^n=\sum_{(0\leq k_1,…,k_s \leq n) (k_1+…+k_s=n)}(^n_{k_1,…,k_s})a_1^{k_1}…*a_s^{k_s}$ összefüggés