5600235764

8 Współczynniki dwumianowe 20

Twierdzenie 8.1. Dla dowolnych 0 < k < n

Dowód. Ustalmy pewien n-elementowy zbiór X, i wybierajmy po kolei k różnych jego elementów, tzn. utwórzmy iniekcję Zk —* X. Wiemy, że takich iniekcji jest

Tli

n(n - 1).....(n — k + 1) = -^L7TT.

(n — k)\

W wyniku takiego wyboru, dostajemy wszakże pewien uporządkowany ciąg k elementów zbioru X. Wiele takich ciągów wyznacza ten sam fc-elementowy podzbiór zbioru X. Ciągi takie różnią się jedynie kolejnością elementów, a zatem jest ich tyle ile permutacji zbioru /c-elemetowego, czyli A;!. Zatem jest dokładnie

n(n — 1) ■... • (n — k + 1) _ n!

k\    (n — k)\k\

podzbiorów fc-elementowych zbioru n-elementowego.    □

To samo twierdzenie można dowieść indukcyjnie.

Twierdzenie 8.2. Dla n, k 6 N zachodzi:

(U)

(iii)

0, dla k > n,

n, dla n > 0,

dla n > k > 0.

(iv)

Dowód, (i) Natychmiastowa konsekwencją faktu, że dowolny zbiór n-elementowy X ma tylko jeden 0-elementowy podzbiór, a mianowicie podzbiór pusty 0 i tylko jeden podzbiór n-elementowy, to znaczy cały zbiór X.

(ii)    Zbiór n-elementowy nie może mieć podzbiorów o k > n elementach.

(iii)    Podzbiorów jednoelementowych jest dokładnie tyle ile elementów w zbiorze.

(iv)    Załóżmy, że n > /c > 0. Wówczas fc-elementowych podzbiorów A w n-elementowym zbiorze X jest tyle samo co ich (n — A;)-elementowych dopełnień X\A. Innymi słowy funkcja

n(X)3A->X\A€V_n-_k(X)

□

jest bijekcją, a więc \Pt(X)\ = \V_n-_k(X)\,