5032124830

Rozdział 2

Elementy kombinatoryki oraz techniki zliczania

2.1 Wprowadzenie teoretyczne i przykłady

Niech dane będą. zbiory:

Ai = {ai,a₂,...,a_ni}, |Ai| = ni A2 = {bi,b₂, ...,b_n2j, \A₂\ = n₂

Ak = 0>i,P2, -,Pn_k}, \A_k\ = n_k

Ilość ciągów (cij_l, bj₂, ...,Pj_k) takich, że wyraz pierwszy należy do Aj, drugi do A₂, k-ty do A_k da się wyznaczyć, korzystając z twierdzenia:

Twierdzenie 2.1.1 (Zasada wielokrotnego wyboru)

Liczba k-elementowy eh ciągów, takich że a^ € A\, bj₂ G A₂,..., Xj_k € A_k, jest równa \Ai\ ■ \A₂\ ■ ...|>bc| = n\ ■ n₂ ■ ... ■ n_k.

Definicja 2.1.1 Niech dany będzie zbiór A = {ai, a₂,..., a_n}. Każdą funkcję, która liczbie naturalnej ze zbioru {1,2, przyporządkowuje dokładnie jeden element a_m ze zbioru A nazywamy k-elementową wariacją z powtórzeniami zbioru A.

K-elementowa wariacja z powtórzeniami zbioru A to k-krotny wybór po jednym elemencie ze zwracaniem ze zbioru A.

Twierdzenie 2.1.2 Liczba k-elementowych wariacji z powtórzeniami zbioru n-elementowego jest równa |V^j =n^k.