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
.
De nicja. 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 De nicja. 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. De niujemy 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
de nicj¦.
De nicja. Niech n b¦dzie liczb¡ naturaln¡. Dla liczby caªkowitej k de niujemy
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 zde niowa¢ 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.
De nicja. 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