Powtórka

Podstawowe zasady kombinatoryki:

• Reguła mnożenia.
  Jeżeli dane są dwa zbiory skończone $A$ i $B$, z których zbiór $A$ ma $m$ elementów, a zbiór $B$ ma $n$ elementów, to liczba różnych par $(a,b)$, takich że $a\in A$ i $b\in B$, jest równa iloczynowi mocy tych zbiorów: $\boldsymbol{m\cdot n}$.
• Reguła dodawania.
  Jeżeli dane są dwa zbiory rozłączne $A$ i $B$, z których zbiór $A$ ma $m$ elementów, a zbiór $B$ ma $n$ elementów, to moc zbioru $A\cup B$ jest równa sumie mocy tych zbiorów: $\boldsymbol{m+n}$.

Liczba wszystkie możliwych odwzorowań określonego typu:

1. Wszystkich możliwych permutacji zbioru $n$-elementowego, czyli $n$-wyrazowych ciągów utworzonych ze wszystkich elementów tego zbioru, jest $$P_n=n!$$
2. Wszystkich możliwych $k$-elementowych wariacji bez powtórzeń zbioru $n$-elementowego, czyli $k$-wyrazowych ciągów różnych elementów tego zbioru, jest $$\eqalign{V_n^k&=\frac{n!}{\left(n-k\right)!}\cr }$$
3. Wszystkich możliwych $k$-elementowych wariacji z powtórzeniami zbioru $n$-elementowego, czyli $k$-wyrazowych ciągów niekoniecznie różnych elementów tego zbioru, jest $$W_n^k=n^k$$
4. Wszystkich możliwych $k$-elementowych kombinacji zbioru $n$-elementowego, czyli $k$-elementowych podzbiorów tego zbioru, jest $$\eqalign{C_n^k&={n \choose k}=\frac{n!}{k!\cdot\left(n-k\right)!}\cr }$$

Schemat ułatwiający dobór odpowiedniego modelu kombinatorycznego odpowiadającego sytuacji opisanej zadaniu.