41108 skanuj0003

ELEMENTY KOMBINATORYKI

Definicja siini

Symbol n! (n silnia) zdefiniowany jest dla liczb całkowitych nieujemnych i oznacza iloczyn pierwszych n liczb naturalnych, gdy

n jest liczbą naturalną oraz 1, gdy n = 0.

n! =

l*2-3-...-n dian = 1,2,...

1    dla n = 0

Definicja symbolu Newtona

(n\

Symbol Newtona (czyt. „n po k” lub „n nad k”) zdefiniowany jest

w

dla liczb całkowitych nieujemnych i oznacza 0, gdy k > n i iloraz iloczynu pierwszych n liczb naturalnych oraz iloczynu: iloczynu k pierwszych liczb naturalnych i iloczynu pierwszych n-k liczb

naturalnych w przeciwnym przypadku.

fn)	II
, k,
V V

k! (n — k)!

0

gdy 0 < k < n

gdy k > n

n!

Własności symbolu Newtona: 1) dla 0 < k < n

v^ky

n-k

2) dla 1 < k < n

v^ky

+

V

n

k-1

fn + l) k

n

3) Ik-

k=l

n

4) I.

5) X

k=0 V^k/ ^ rf

k=0W

= n • 2

= 2

n—1

_an-k_bk _    •, .W

(a + b)¹

6) (x₁+x₂+x₃+... + x_n)ⁿ =n!

X

ki k-^X1 ’^x2'

_x^km

(k₁+k₂+...+k_m=n)    ^kl-'^k2-'''kjjj!