szukanie zaawansowane

Elementy kombinatoryki

Najpierw małe przypomnienie pojęć takich jak silnia i symbol Newtona.

Silnia

n! (n silnia) to iloczyn wszystkich liczb naturalnych nie większych od n.

n! = \begin{cases}1 \hspace{10}: n = 0  \vee n = 1 \\ n \cdot (n-1) \hspace{10}: n > 1 \end{cases} \\ \\  \vee \\ \\ n! = \begin{cases} 1 \hspace{10}: n = 0 \\ \prod_{k=1}^{n} k  \hspace{10}: n  \ge 1\end{cases}


5! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 = 120

Dla każdej dodatniej liczby naturalnej n, \hspace{5}n!! definiujemy jako:


n!! = \begin{cases} 2\cdot4\cdot6\cdot8\cdot \ldots \cdot (n-2) \cdot n \hspace{10} : n = 2k  \wedge k \in N^{+} \\ 1\cdot3\cdot5\cdot7\cdot \ldots \cdot (n-2) \cdot n \hspace{10} : n = 2k+1  \wedge k \in N^{+}\end{cases}


4!! = 2 \cdot 4 = 8 , \hspace{10} 5!! = 1\cdot3\cdot5 = 15

Ważne! (n!)!  \neq  n!!


Przykładowo:

4!! = 2\cdot4 = 8 \\ \\ (4!)! = (1\cdot2\cdot3\cdot4)! = (24)! = \\ 1\cdot2\cdot3\cdot4\cdot5\cdot6\cdot\ldots\cdot23\cdot24 = 620448401733239439360000



Symbol Newtona

dla dowolnych liczb naturalnych n, k, Symbol Newtona definiujemy jako:

{n\choose k} = \begin{cases}\frac{n!}{k!\cdot(n-k)!} \hspace{10}: 0  \le k \le n \\ 0 \hspace{10}: k>n\end{cases}


Symbol Newtona czytamy "n nad k" lub "n po k" (drugie sformułowanie jest popularniejsze)

Elementy Kombinatoryki

Twierdzenie o mnożeniu

Liczbę wszystkich różnych ciągów (a_{1}, a_{2}, a_{3}, \ldots , a_{j} ) takich, że (element) x_{i} \hspace{10}( i = 1,2,3, \ldots, j ) możemy wybrać na n_{i} sposobów jest równa n_{1}\cdot n_{2}\cdot n_{3}\cdot \ldots \cdot n{j}


Permutacje

Permutacja bez powtórzeń

Permutacją bez powtórzeń zbioru n-elementowego, nazywamy każdy n-wyrazowy ciąg utworzony z wszystkich elementów tego zbioru.

Permutację bez powtórzeń zapisujemy za pomocą:

P_{n} = n! \hspace{10} n \in N^{+}



Permutacja z powtórzeniami

Permutacją n-elementową z powtórzeniami zbioru X = \{x_{1}, x_{2}, x_{3}, \ldots, x_{k} \}, w której x_{1} występuje n_{1} razy, element x_{2} występuje n_{2} razy itd. i n_{1}+n_{2}+\ldots+n_{k} = n nazywamy każdy n-wyrazowy ciąg, w którym x_{i} występuje n_{i} razy. (i = 1,2,\ldots, k)

Permutację z powtórzeniami zapisujemy za pomocą wzoru:

P_{n}^{n_{1},n_{2}, \ldots, n_{k}} = \frac{n!}{n_{1}!\cdotn_{2}!\cdot \ldots\cdotn_{k}!}\hspace{10}: i = 1,2,3,\ldots,k \hspace{5}n_{1}+n_{2}+\ldots+n_{k} = n, \hspace{5} n_{i} \in N^{+}


Wariacje

Wariacje bez powtórzeń

Dla dowolnych n,k \in N^{+}  \wedge  k \le n k-wyrazowych wariacji bez powtórzeń zbioru n-elementowego jest:

V^{k}_{n} = n\cdot(n-1)\cdot(n-2)\cdot\ldots\cdot(n-k+1) = \frac{n!}{(n-k)!}



Wariacje z powtórzeniami

Dla dowolnych n,k \in N^{+}  \wedge k \le n k-wyrazowych wariacji z powtórzeniami zbioru n-elementowego jest:

\overline{V}^{k}_{n} = n^k



Kombinacje

Kombinacje bez powtórzeń

Dla dowolnych n,k \in N^{+} \wedge  k \le n liczba k-elementowych kombinacji bez powtórzeń zbioru n-elementowego ma postać:

C^{k}_{n} = {n\choose k} =\frac{n!}{k!\cdot(n-k)!}


Kombinacją k-elementową zbioru n-elementowego nazywamy każdy k-elementowy podzbiór tego zbioru (k \le n)
Kombinacje z powtórzeniami

Kombinację k-elementową z powtórzeniami zbioru n-elementowego X = \{x_{1}, x_{2}, x_{3}, \ldots, x_{n} \} nazywamy każdy ciąg (k_{1},k_{2},\ldots,k_{n}) taki że, k_{1}+k_{2}+\ldots+k_{n} = k \hspace{10} k_{i} \in N^{+}, \hspace{10} i = 1,2,3,\ldots, n

Oczywiście, w kombinacji z powtórzeniami, element x_{1} występuje k_1 razy, x_2 \hspace{10}k_2 razy itd.

Wszystkich k-elementowych kombinacji z powtórzeniami zbioru n-elementowego jest:

\overline{C}^k_{n} = {n+k-1 \choose n-1}

Arytmetyka:

Logika matematyczna:

Geometria:

Funkcje:

Analiza matematyczna:

Algebra:

Rachunek prawdopodobieństwa:

 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl