2 Podstawowe obiekty kombinatoryczne

Oznaczenia: N = {0, 1, 2, . . . } zbiór liczb naturalnych.

Dla n ∈ N przyjmujemy [n] = {1, 2, . . . , n}. W szczególno±ci [0] jest zbiorem

pustym.

Je±li A jest zbiorem sko«czonym, to ilo±¢ elementów w A oznaczamy symbolem
|A|

lub #A; tego drugiego symbolu u»ywamy zwªaszcza wtedy, gdy zbiór jest

zadany przez list¦ swoich elementów.
2.1 Niech A b¦dzie zbiorem sko«czonym. Ci¡g nelementowy o warto±ciach w
A

zapisywany w postaci (a

1

, a

2

, . . . , a

n

)

, gdzie a

i

∈ A

, jest funkcj¡ a : [n] −→ A

przy czym a(i) = a

i

dla i = 1, 2, . . . , n. St¡d w odniesieniu do ci¡gów mo»na

u»ywa¢ tych samych terminów, których u»ywamy w odniesieniu do funkcji. Pro-

ste rozumowanie indukcyjne pokazuje, »e wszystkich ci¡gów nelementowych o

warto±ciach w zbiorze kelementowym jest k

n

.

Denicja. Permutacj¡ zbioru nelementowego A nazywamy ka»dy ró»nowar-

to±ciowy ci¡g nelememntowy o warto±ciach w A. Zbiór wszystkich permutacji

zbioru A oznaczamy symbolem P

A

.

Stwierdzenie. Je±li A jest zbiorem nelementowym, to ilo±¢ wszystkich per-

mutacji A jest równa n!.

Dowód. Niech p

n

oznacza ilo±¢ permutacji zbioru n-elementowego. Stosujemy

indukcj¦ wzgl¦dem n. Oczywi±cie p

1

= 1 = 1!

. Niech teraz A b¦dzie zbiorem o

n > 1

elementach i zaªó»my prawdziwo±¢ twierdzenia dla wszystkich zbiorów o

n − 1

elementach. Niech (a

1

, a

2

, . . . , a

n

)

b¦dzie permutacj¡ zbioru A. Wówczas

(a

1

, a

2

, . . . , a

n−1

)

jest permutacj¡ zbioru A \ {a

n

}

. Odwrotnie, je±li b ∈ A i

(a

1

, a

2

, . . . , a

n−1

)

jest permutacj¡ zbioru A \ {b}, to (a

1

, a

2

, . . . , a

n−1

, b)

jest

permutacj¡ zbioru A. St¡d p

n

= n · p

n−1

i na mocy zaªo»enia indukcyjnego

p

n

= n · (n − 1)! = n!

.

2.2 Uwagi na temat silni. Zatrzymajmy si¦ na chwil¦ nad wyst¦puj¡c¡ w

poprzednim twierdzeniu funkcj¡ silni. Warto±ci tej funkcji dla maªych n podaje

nast¦pj¡ca tabela.

n

0

1

2

3

4

5

6

7

8

9

10

. . .

n!

1

1

2

6

24

120

720

5 040

40 320

362 880

3 628 800

. . .

Ze wzgl¦dów praktycznych warto zapami¦ta¢ ostatni¡ z podanych warto±ci, a

przynajmniej pami¦ta¢, »e 10! to troch¦ wi¦cej ni» 3 i póª miliona. Z tabeli

wida¢, »e funkcja silni ro±nie bardzo szybko (co zreszt¡ znalazªo odbicie w jej

polskiej nazwie). Jak szybko? Zazwyczaj zadawalaj¡c¡ odpowied¹ daje nast¦-

puj¡ce stwierdzenie.

Stwierdzenie. Dla wszystkich n naturalnych zachodzi

n

n

e

n−1

≤ n! ≤

n

n+1

e

n−1

.

1

Dowód. Punktem wyj±cia jest nast¦puj¡ca, ªatwa do udowodnienia nierówno±¢:

dla wszystkich x ∈ R zachodzi

1 + x ≤ e

x

.

Przyjmuj¡c x =

1
k

i podnosz¡c obie strony do k-tej pot¦gi, otrzymujemy

 k + 1

k



k

≤ e.

Mo»emy teraz oszacowa¢ iloraz

n

n

n!

w sposób nast¦puj¡cy

n

n

n!

=

n

n−1

(n − 1)!

=



n

n − 1



n−1

·

(n − 1)

n−2

(n − 2)!

=

=



n

n − 1



n−1

·

 n − 1

n − 2



n−2

·

(n − 2)

n−3

(n − 3)!

= · · · =

=



n

n − 1



n−1

·

 n − 1

n − 2



n−2

· · · · ·

 3

2



2

·

 2

1



≤ e

n−1

,

co daje lew¡ nierówno±¢ zapisan¡ w tezie stwierdzenia. Analogicznie dla x =
−

1

k+1

otrzymujemy



k

k + 1



k+1

≤ e

−1

i mo»emy oszacowa¢

n!

n

n+1

=

(n − 1)!

n

n

=

 n − 1

n



n

·

(n − 2)!

(n − 1)

n−1

=

=

 n − 1

n



n

·

 n − 2

n − 1



n−1

·

(n − 3)!

(n − 2)

n−2

= · · · =

=

 n − 1

n



n

·

 n − 2

n − 1



n−1

· · · · ·

 2

3



3

·

 1

2



2

≤ e

−(n−1)

,

co daje drug¡ nierówno±¢.

Z powy»szego stwierdzenia wynika, »e n! jest iloczynem (n/e)

n

przemono»o-

nym przez pewien czynnik zawarty pomi¦dzy e i en. Okazuje si¦, »e obserwacj¦

t¦ mo»na u±ci±li¢.

Twierdzenie. (Stirling) n! ∼

√

2πn

n

e

n

.

2.3 Denicja. Kombinacj¡ kelementow¡ zbioru A nazywamy kelementowy

podzbiór A. Symbolem C

n,k

b¦dziemy oznacza¢ zbiór wszystkich kombinacji k

elementowych zbioru [n].

Stwierdzenie. Zbiór C

n,k

jest niepusty wtedy i tylko wtedy, gdy 0 ≤ k ≤ n.

Je±li ta nierówno±¢ zachodzi, to |C

n,k

| =

n!

k!(n−k)!

.

2

Dowód. Deniujemy funcj¦ okre±lon¡ na P

[n]

o warto±ciach w C

n,k

w sposób

nast¦puj¡cy:

(a

1

, a

2

, . . . , a

n

) 7→ {a

1

, a

2

, . . . , a

k

}.

Przeciwobraz ka»dego zbioru A ∈ C

k,n

skªada si¦ z tych ci¡gów (b

1

, b

2

, . . . , b

n

) ∈

P

[n]

, dla których podci¡g (b

1

, b

2

, . . . , b

k

)

jest permutacj¡ zbioru A, a podci¡g

(b

k+1

, b

k+2

, . . . , b

n

)

jest permutacj¡ zbioru [n] \ A.

2.4 Wyra»enie

n!

k!(n−k)!

nazywa si¦ wspóªczynnikiem dwumianowyn Newtona

i oznacza symbolem

n
k

.

W dalszym ci¡gu b¦dzie wygodniej rozszerzy¢ nieco

denicj¦.

Denicja. Niech n b¦dzie liczb¡ naturaln¡. Dla liczby caªkowitej k deniujemy

symbol Newtona n nad k w sposób nast¦puj¡cy

n

k



=



n!

(n−k)!k!

,

gdy 0 ≤ k ≤ n;

0

w przeciwnym przypadku.

2.5 Wzór dwumianowy Newtona

Dla dowolnej liczby naturalnej n

(x + y)

n

=

n

X

k=0

n

k



x

k

y

n−k

.

Dowód. Rozwijaj¡c lew¡ stron¦, mamy

(x + y)

n

= (x + y)(x + y) · · · · · (x + y)

|

{z

}

n razy

.

Wymna»aj¡c powy»sze dwumiany, z ka»dego z n nawiasów wybieramy czynnik
x

lub y. Wspóªczynnik przy x

k

y

n−k

jest równy ilo±ci sposobów wybrania k

czynników x spo±ród n dwumianów.

Uwaga. Wzór dwumianowy obowi¡zuje nie tylko wtedy, gdy x i y s¡ liczbami

rzeczywistymi czy zespolonymi. Z dowodu wynika, »e obowi¡zuje w ka»dym

systemie z przemiennymi i ª¡cznymi dziaªaniami + i ×, w którym obowi¡zuje

rozdzielno±¢ dodawania wzgl¦dem mno»enia, a wi¦c na przykªad dla wielomia-

nów, w ciaªach sko«czonych, w pier±cieniach reszt itp.
2.6 Dokonuj¡c cz¦±ciowego skrócenia, mo»emy zapisa¢

x

k



=

(x − k + 1) · · · · · (x − 1)x

k!

,

co pozwala zdeniowa¢ symbol dwumianowy dla dowowolnej liczby naturalnej
k

i dowolnej liczby rzeczywistej x.

Zauwa»my, »e

3

(1) przy ustalonej liczbie k wyra»enie

x
k

jest wielomianem stopnia k od x;

(2) dla k > 0, liczby 0, 1, . . . , k − 1 s¡ pierwiastkami wielomianu

x
k

, s¡ to jego

jedyne pierwiastki.
2.7 Rekurencja dla symboli dwumianowych.

Twierdzenie. (a) Dla dowolnych liczb naturalnych n ≥ k > 0 zachodzi

n

k



=

n − 1

k



+

n − 1

k − 1



.

(b) Dla ka»dej liczby naturalnej k > 0 zachodzi

x

k



=

x − 1

k



+

x − 1

k − 1



.

Dowód.

(a) Niech A b¦dzie kelemnetowym pozbiorem [n]. Je±li n 6∈ A,

to A jest podzbiorem [n − 1]. W przeciwnym przypadku A \ {n} jest (k − 1)

elementowym podzbiorem [n−1]. Otrzymujemy w ten sposób wzajemnie jedno-

znaczn¡ odpowiednio±¢ pomi¦dzy C

n,k

oraz rozª¡czn¡ sum¡ C

n−1,k

i C

n−1,k−1

.

(b) Na mocy (2.6) obie strony równo±ci s¡ dla ustalonego k wielomianami stopnia
k

, a na mocy punktu (a) wielomiany te przyjmuj¡ równe warto±ci dla niesko«-

czenie wielu warto±ci x. St¡d s¡ równe.

2.8 Uwaga. Wªasno±¢ rekurencyjna wraz z warunkami pocz¡tkowymi

n

0

=

1

dla wszystkich n,

0
k

= 0

dla wszyskich k > 0 pozwala wyliczy¢

n
k

dla

wszystkich n, k ∈ N (trójk¡t Pascala).
2.9 Symbole wielomianowe Newtona

O kelemtowym podzbiorze B zbioru nelementowego A mo»emy my±le¢ jako o

podziale zbioru A na dwie cz¦±ci: kelementow¡ cz¦±¢ B i (n − k)elementow¡
A \ B

. Uogólnienie tego punkt widzenia prowadzi do uogólnienia symboli dwu-

mianowych.

Denicja. Niech (k

1

, k

2

, . . . , k

r

)

b¦dzie ci¡giem liczb naturalnych z sum¡ n.

Rozkªadem zbioru n elementowego A na bloki dªugo±ci (k

1

, k

2

, . . . , k

r

)

nazy-

wamy ciag (A

1

, A

2

, . . . , A

r

)

podzbiorów A taki, »e

(1) |A

i

| = k

i

dla i = 1, 2, . . . , r;

(2) A

i

∩ A

j

6= ∅

dla i 6= j;

(3) A

1

∪ A

2

∪ · · · ∪ A

r

= A

.

Twierdzenie. Niech k

1

+ k

2

+ · · · + k

r

= n

. Wszystkich rozkªadów zbioru

n

elementowego na bloki dªugo±ci (k

1

, k

2

, . . . , k

r

)

jest

n!

k

1

! · k

2

! · · · · · k

r

!

ozn.

=



n

k

1

, k

2

, . . . , k

r



.

Twierdzenie. Dla ka»dego ci¡gu (k

1

, k

2

, . . . , k

r

)

, gdzie k

1

+ k

2

+ · · · + k

r

= n

i k

i

> 0

, zachodzi wzór rekurencyjny



n

k

1

, k

2

, . . . , k

r



=

r

X

i=1



n − 1

k

1

, . . . , k

i

− 1, . . . , k

r



.

4

Twierdzenie. Wzór wielomianowy Newtona

(x

1

+ x

2

+ · · · + x

r

)

n

=

X

k

1

+k

2

+···+k

r

=n



n

k

1

, k

2

, . . . , k

r



x

k

1

1

x

k

2

2

. . . x

k

r

r

.

Dowody tych twierdze« s¡ analogiczne do dowodów w przypadku r = 2.

5