Matematyka Dyskretna
Andrzej Szepietowski
25 marca 2004 roku
Rozdział 1
Kombinatoryka
1.1 Zasada podwójnego zliczania
Zasada podwójnego zliczania jest bardzo prosta. Oto ona:
Jeżeli elementy jakiegoś zbioru są zliczane na dwa sposoby, to wynik obu zliczeń jest taki
sam.
Zastosujemy tę zasadę do udowodniena następującego lematu:
Lemat 1.1 (O uściskach dłoni) Przypuśćmy, że na przyjęciu część osób wita się przez
uścisk dłoni. Wtedy liczba osób, które uścisnęły nieparzystą liczbę dłoni jest parzysta.
Bardziej formalnie lemat ten można formułować za pomocą grafów. Rozważmy graf,
którego wierzchołkami są osoby na przyjęciu, a krawędzie łączą te osoby, które uścisnęły
sobie dłonie. Mamy.
Lemat 1.2 Niech G = (V, E), będzie dowolnym grafem z m = |E| krawędziami. Wtedy
d(v) = 2m,
v"V
gdzie d(v) oznacza stopień wierzchołka v, czyli liczbę krawędzi wychodzących z v.
Dowód: Zliczmy końce wszystkich krawędzi na dwa sposoby. Najpierw sumujemy po
wszystkich wierzchołkach v ile krawędzi ma koniec w wierzchołku v. Otrzymamy sumę
d(v). Następnie dla każdej krawędzi zliczamy jej dwa końce. Otrzymamy wynik
v"V
2m. Teza wynika z zasady podwojnego zliczania.
Ponieważ suma d(v) jest parzysta, więc liczba nieparzystych składników jest
v"V
parzysta. Mamy więc:
Lemat 1.3 (O uściskach dłoni, druga wersja) W każdym grafie liczba wierzchołków nie-
parzystego stopnia jest parzysta.
3
4 Rozdział 1. Kombinatoryka
1.2 CiÄ…gi
Zastanówmy się, ile ciągów długości k można utworzyć z elementów zbioru zawierają-
cego n symboli. Jeżeli zbiór symboli zawiera dwa elementy:
a, b,
to można utworzyć dwa ciągi długości jeden:
(a), (b),
cztery ciągi długości dwa:
(a, a), (a, b), (b, a), (b, b).
Aby uzyskać ciągi długości trzy, postępujemy w następujący sposób: bierzemy cztery
ciągi długości dwa i najpierw do każdego z nich dopisujemy na początku a. Otrzymujemy
w ten sposób komplet:
(a, a, a), (a, a, b), (a, b, a), (a, b, b).
Zauważmy, że są to wszystkie ciągi długości trzy z pierwszą literą a. Potem do tych
samych czterech ciągów długości dwa dopisujemy na początku symbol b i otrzymujemy
komplet:
(b, a, a), (b, a, b), (b, b, a), (b, b, b).
Komplety te są rozłączne i oba zawierają różne ciągi. Razem tworzą zbiór wszystkich
ciągów długości trzy:
(a, a, a), (a, a, b), (a, b, a), (a, b, b), (b, a, a), (b, a, b), (b, b, a), (b, b, b).
Postępując podobnie, możemy otrzymać szesnaście ciągów długości cztery.
Twierdzenie 1.4 Liczba ciągów długości k o elementach ze zbioru {a, b} wynosi 2k.
Dowód przez indukcję. Jak już pokazano, są dwa ciągi długości jeden.
Załóżmy teraz, że liczba ciągów długości k wynosi 2k i zauważmy, że wszystkich
ciągów długości k + 1 jest dwa razy więcej. Jest 2k ciągów z pierwszym elementem a i
2k ciÄ…gów z pierwszym elementem b. Razem mamy 2 · 2k = 2k+1 ciÄ…gów dÅ‚ugoÅ›ci k + 1.
Jeżeli zbiór symboli zawiera n elementów, to powtarzając powyższe rozumowanie,
możemy się przekonać, że istnieje n ciągów długości jeden, n2 ciągów długości dwa i
ogólnie ciągów długości k + 1 jest n razy więcej niż ciągów długości k. Zachodzi zatem
twierdzenie.
Twierdzenie 1.5 Liczba ciągów długości k o elementach ze zbioru n-elementowego wy-
nosi nk.
1.3. Funkcje 5
1.3 Funkcje
Policzmy teraz, ile jest funkcji ze zbioru A w zbiór B. Przypuśćmy, że zbiór A zawiera k
elementów:
1, . . . , k.
Każdą funkcję f z A w B można przedstawić jako ciąg
(f(1), f(2), . . . , f(k)).
Ciąg ten jest długości k, a jego elementy są wzięte ze zbioru B. Zauważmy, że każdej
funkcji odpowiada jeden ciąg, i na odwrót, każdy ciąg
(b1, b2, . . . , bk)
opisuje jedną funkcję. Mianowicie funkcję, która dla każdego i przypisuje wartość
f(i) = bi.
Przykład 1.6 Jeżeli A składa się z czterech elementów:
A = {1, 2, 3, 4},
a B składa się z trzech elementów:
B = {1, 2, 3},
to ciÄ…g
(2, 2, 2, 2)
opisuje funkcję stałą, która w całej swojej dziedzinie przyjmuje wartość 2, a ciąg
(1, 2, 3, 3)
opisuje funkcję f, która przyjmuje następujące wartości:
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 3.
Z powyższego wynika, że funkcji ze zbioru A w zbiór B jest tyle samo co ciągów długości
k = |A| z elementami ze zbioru B. Udowodniliśmy więc poniższe twierdzenie.
Twierdzenie 1.7 Jeżeli zbiór A zawiera k elementów, a zbiór B zawiera n elementów, to
liczba funkcji ze zbioru A w zbiór B wynosi nk.
1.4 Ciągi bez powtórzeń
Policzmy teraz, ile jest ciągów bez powtórzeń, czyli ciągów różnowartościowych. Jeżeli
elementy bierzemy ze zbioru trzyelementowego
{1, 2, 3},
6 Rozdział 1. Kombinatoryka
to możemy utworzyć trzy ciągi jednoelementowe:
(1), (2), (3),
sześć różnowartościowych ciągów dwuelementowych:
(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)
oraz sześć ciągów trójelementowych:
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).
Nie ma, oczywiście, dłuższych ciągów różnowartościowych utworzonych z elementów
zbioru {1, 2, 3}.
Twierdzenie 1.8 Jeżeli elementy wybieramy ze zbioru n-elementowego A, to liczba cią-
gów k-elementowych bez powtórzeń, które można wybrać z tego zbioru, wynosi:
n(n - 1) · · · (n - k + 1).
W tym wyrażeniu mamy iloczyn k kolejnych liczb, poczynając od (n - k + 1), a kończąc
na n.
Dowód. Jeżeli budujemy ciąg bez powtórzeń, to na pierwszy element ciągu możemy wy-
brać każdy z n elementów zbioru A, na drugą pozycję w ciągu możemy wybrać już tylko
jeden z n - 1 elementów (wszystkie poza tym, który został wybrany na pierwszy element
ciągu) i tak dalej, na każdą kolejną pozycję mamy o jeden element do wyboru mniej.
Zauważmy, że jeżeli k > n, to n(n - 1) . . . (n - k + 1) = 0, co jest zgodne z tym, że
w takim przypadku nie można utworzyć żadnego k-elementowego ciągu bez powtórzeń
z elementami ze zbioru A.
1.5 Permutacje
Permutacje to ciągi bez powtórzeń długości n, wybierane ze zbioru n-elementowego. Na
przykład, mamy dwie permutacje dwuelementowe:
(1, 2), (2, 1),
oraz sześć permutacji trzyelementowych:
(1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), (3, 2, 1).
Zgodnie z twierdzeniem 1.8 liczba permutacji w zbiorze n-elementowym wynosi:
n(n - 1)(n - 2) . . . 1,
czyli jest równa n!.
1.5. Permutacje 7
Funkcja silnia n! określona jest dla n > 0 w następujący sposób:
n
n! = i
i=1
Dodatkowo przyjmujemy 0! = 1. Mamy
1! = 1, 2! = 1 · 2 = 2, 3! = 1 · 2 · 3 = 6, 4! = 1 · 2 · 3 · 4 = 24.
Wartości funkcji silnia szybko rosną, na przykład:
5! = 120, 10! = 3 628 800, 20! H" 2433 · 1015.
Dla przybliżonego obliczania silni korzysta się ze wzoru Stirlinga:
"
n! H" e-nnn 2Ä„n. (1.1)
Dla każdego n zachodzą również następujące oszacowania:
"
n n " n n n
12
2Ä„n d" n! d" 2Ä„n e . (1.2)
e e
Dowody wzoru Stirlinga oraz powyższych oszacowań wychodzą poza zakres tego pod-
ręcznika.
Czasami używa się innej definicji permutacji. Mianowicie permutacja n-elementowa
to dowolna funkcja różnowartościowa ze zbioru {1, 2, . . . , n} na ten sam zbiór. Na ozna-
czenie permutacji Ą używa się zapisu:
1 2 . . . n
.
Ä„(1) Ä„(2) . . . Ä„(n)
Przykład 1.9 Permutacja:
1 2 3 4
Ä„ =
2 1 4 3
jest funkcją, która przyjmuje następujące wartości:
Ä„(1) = 2, Ä„(2) = 1, Ä„(3) = 4, Ä„(4) = 3.
Dwie permutacje n-elementowe można składać tak, jak składa się funkcje. Złożenie Ą1 ć%
Ą2 permutacji Ą1 i Ą2 określone jest wzorem:
Ą1 ć% Ą2(x) = Ą1(Ą2(x)).
Na przykład:
1 2 3 4 1 2 3 4 1 2 3 4
ć% = .
2 1 4 3 3 2 1 4 4 1 2 3
Zbiór wszystkich permutacji na zbiorze {1, . . . , n} z działaniem złożenia ma następujące
własności:
8 Rozdział 1. Kombinatoryka
" ZÅ‚ożenie permutacji jest Å‚Ä…czne. To znaczy, dla każdych trzech permutacji Ä„, Á, Ã:
Ä„ ć% (Á ć% Ã) = (Ä„ ć% Á) ć% Ã.
" Wśród permutacji istnieje identyczność id, czyli permutacja, która każdemu x z
dziedziny przypisuje wartość id(x) = x. Identyczność jest elementem neutralnym
składania permutacji, ponieważ dla każdej permutacji Ą:
id ć% Ą = Ą ć% id = Ą.
" Dla każdej permutacji Ą istnieje permutacja odwrotna (funkcja odwrotna) Ą-1,
spełniająca warunek:
Ą ć% Ą-1 = Ą-1 ć% Ą = id.
Powyższe zależności oznaczają, że zbiór wszystkich permutacji na zbiorze {1, . . . , n} z
działaniem składania permutacji stanowi grupę.
1.6 Podzbiory
Policzmy teraz, ile podzbiorów ma skończony zbiór n-elementowy. Jeżeli zbiór składa
się z trzech elementów:
{a, b, c},
to możemy łatwo wypisać wszystkie jego podzbiory:
", {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.
Tych podzbiorów jest osiem. Każdy zbiór trzyelementowy posiada osiem podzbiorów,
ponieważ nie ma znaczenia, jak nazywają się elementy zbioru. Zbiór pusty ma tylko jeden
podzbiór: zbiór pusty. Jeżeli zbiór zawiera jeden element {a}, to ma dwa podzbiory:
", {a},
a jeżeli zbiór zawiera dwa elementy {a, b}, to ma cztery podzbiory:
", {a}, {b}, {a, b}.
Rozważmy teraz ogólnie podzbiory zbioru
{1, 2, 3, . . . , n}.
Z każdym podzbiorem
A ‚" {1, 2, 3, . . . , n}
jest związana jego funkcja charakterystyczna, określona następującym wzorem:
1, gdy i " A,
ÇA(i) =
0, gdy i " A.
/
1.7. Podzbiory k-elementowe 9
DziedzinÄ… funkcji ÇA jest zbiór {1, . . . , n}, a przeciwdziedzinÄ… zbiór {0, 1}. Zauważmy,
że każdemu podzbiorowi odpowiada jedna funkcja charakterystyczna, i na odwrót, jeżeli
wez
miemy dowolnÄ… funkcjÄ™:
Ç : {1, . . . , n} {0, 1},
to wyznacza ona zbiór:
A = {i | Ç(i) = 1}.
PrzykÅ‚ad 1.10 Dla n = 5 funkcja charakterystyczna ÇA zbioru A = {2, 3, 5} jest opisa-
na przez ciÄ…g (0, 1, 1, 0, 1), a ciÄ…g (1, 0, 1, 1, 0) opisuje funkcjÄ™ charakterystycznÄ… zbioru:
{1, 3, 4}.
Z powyższych rozważań wynika, że liczba podzbiorów zbioru n-elementowego jest rów-
na liczbie funkcji ze zbioru {1, . . . , n} w zbiór {0, 1}. Czyli na podstawie twierdzenia 1.7
mamy.
Twierdzenie 1.11 Każdy n-elementowy zbiór ma 2n podzbiorów.
1.7 Podzbiory k-elementowe
Zastanówmy się teraz nad podzbiorami określonej mocy. Mówimy, że zbiór jest mocy n,
jeżeli zawiera n elementów. Dla zbioru czteroelementowego
{1, 2, 3, 4},
mamy jeden podzbiór pusty (zeroelementowy), cztery podzbiory jednoelementowe:
{1}, {2}, {3}, {4},
sześć podzbiorów dwuelementowych:
{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4},
cztery podzbiory trzyelementowe:
{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4},
i jeden podzbiór czteroelementowy:
{1, 2, 3, 4}.
Liczbę podzbiorów k-elementowych zbioru n-elementowego oznacza się przez
n
.
k
10 Rozdział 1. Kombinatoryka
n
Jest to tak zwany symbol Newtona. Inaczej, jest równe liczbie sposobów na jakie
k
można wybrać k elementów ze zbioru n elementowego. Właśnie pokazaliśmy, że:
4 4 4 4 4
= 1, = 4, = 6, = 4, = 1.
0 1 2 3 4
n
Z definicji wynika, że jeżeli k > n, to = 0. Zachodzą dwa wzory:
k
n n
= , (1.3)
k n - k
n + 1 n n
= + . (1.4)
k k k - 1
Wzór (1.3) bierze się z prostej obserwacji, że wybranie k elementów, które należą do
podzbioru A, jest równoważne wybraniu n - k elementów, które do A nie należą.
Aby uzasadnić równość (1.4), rozważmy k-elementowe podzbiory zbioru
{1, . . . , n, n + 1}.
Policzmy osobno te podzbiory, które zawierają element n + 1, i osobno te, które go nie
n
zawierają. Podzbiorów nie zawierających n + 1 jest , bo wszystkie k elementów trze-
k
n
ba wybrać ze zbioru {1, . . . , n}. Podzbiorów zawierających n + 1 jest , bo k - 1
k-1
elementów trzeba wybrać ze zbioru {1, . . . , n}. Razem wszystkich k-elementowych pod-
n n
zbiorów zbioru {1, . . . , n, n + 1} jest + .
k k-1
Korzystaj ąc z równości (1.4), możemy obliczać symbole Newtona rekurencyjnie. Naj-
0
pierw mamy = 1, ponieważ jest jeden zeroelementowy (pusty) podzbiór zbioru zero-
0
elementowego (pustego). Jeżeli mamy już policzone symbole Newtona dla n, to możemy
n+1
liczyć, ile jest podzbiorów zbioru (n + 1)-elementowego. Zaczynamy od = 1
n+1
n+1
oraz = 1, a następnie korzystamy z równania (1.4). Metodę tę ilustruje tak zwany
0
trójkąt Pascala:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
W n-tym wierszu (wiersze numerowane sÄ… od n = 0) znajdujÄ… siÄ™ symbole Newtona:
n n n n
. . . .
0 1 2 n
n n
Na skraju znajdują się jedynki, ponieważ = = 1. k-ty element w n-tym wierszu
0 n
dla 1 d" k d" n - 1 jest sumą dwóch elementów stojących bezpośrednio nad nim:
n n - 1 n - 1
= + .
k k k - 1
1.8. Dwumian Newtona 11
Jeżeli 0 d" k d" n, to symbol Newtona można też obliczyć ze wzoru:
n n(n - 1) · · · (n - k + 1)
= (1.5)
k k!
lub
n n!
= (1.6)
k k!(n - k)!
Oto uzasadnienie wzoru (1.5): Aby wybrać podzbiór k-elementowy ze zbioru {1, . . . , n},
wybieramy k-elementowy ciąg bez powtórzeń i bierzemy do podzbioru elementy tego
ciągu ignorując ich kolejność. Ponieważ każdemu k-elementowemu podzbiorowi odpo-
wiada k! ciągów o tych samych elementach, więc podzbiorów jest k! razy mniej niż
k-elementowych ciągów bez powtórzeń. Wzór (1.5) wynika teraz z twierdzenia 1.8, a
wzór (1.6) bezpośrednio ze wzoru (1.5).
Wzór (1.5) pozwala wyprowadzić oszacowania na wartość symbolu Newtona, dla 1 d"
k d" n:
k
n n(n - 1) · · · (n - k + 1) n n - 1 n - k + 1 n
= = · · · e" .
k k(k - 1) · · · 1 k k - 1 1 k
n-i n
Ponieważ, jak łatwo sprawdzić e" dla każdego 1 d" i d" k - 1. Korzystając z
k-i k
k
nierówności k! e" ( )k wyprowadzonej ze wzoru Stirlinga (1.2), otrzymujemy górne
e
ograniczenie:
n n(n - 1) · · · (n - k + 1) nk en k
= d" d" .
k k! k! k
1.8 Dwumian Newtona
Symbole Newtona występują w znanym twierdzeniu Newtona.
Twierdzenie 1.12 (dwumian Newtona) Dla każdej liczby rzeczywistej t oraz liczby cał-
kowitej n e" 0 zachodzi:
n
n
(1 + t)n = tk.
k
k=0
Dowód, przez indukcję. Wzór jest oczywisty dla n = 0. Załóżmy teraz, że jest prawdzi-
wy dla n. Mamy:
n
n
(1 + t)n+1 = (1 + t)n(1 + t) = tk (1 + t).
k
k=0
Współczynnik przy tk po prawej stronie wynosi:
n n
+ .
k - 1 k
12 Rozdział 1. Kombinatoryka
n n
Pierwszy skÅ‚adnik pochodzi od iloczynu: tk-1 · t, a drugi od iloczynu: tk · 1. Ze
k-1 k
n+1
wzoru (1.4) wynika, że współczynnik przy tk wynosi .
k
b
Jeżeli do wzoru Newtona podstawimy t = , a potem pomnożymy obie strony przez an,
a
to otrzymamy innÄ… znanÄ… wersjÄ™ wzoru Newtona.
Wniosek 1.13 Dla dowolnych liczb rzeczywistych a i b i dowolnej liczby całkowitej n e"
0:
n
n
(a + b)n = an-kbk.
k
k=0
Jeżeli podstawimy t = 1 do wzoru z twierdzenia 1.12, to otrzymamy:
n
n
2n = ,
k
k=0
co potwierdza jeszcze raz, że wszystkich podzbiorów zbioru n-elementowego jest 2n.
Zobaczymy teraz, że wśród wszystkich podzbiorów zbioru {1, . . . , n} jest tyle samo
podzbiorów mocy parzystej (o parzystej liczbie elementów) i podzbiorów mocy niepa-
rzystej (o nieparzystej liczbie elementów).
Twierdzenie 1.14 Dla każdego zbioru zawierającego n > 0 elementów, liczba podzbio-
rów parzystej mocy jest równa liczbie podzbiorów nieparzystej mocy.
Pierwszy dowód. Jeżeli podstawimy t = -1 do wzoru Newtona, to otrzymamy:
n
n
0 = (-1)k .
k
k=0
n
Zauważmy, że w sumie po prawej stronie z plusem występują symbole Newtona
k
dla parzystych k, a z minusem  dla nieparzystych k. Tak więc z plusem mamy liczbę
podzbiorów parzystej mocy, a z minusem liczbę podzbiorów nieparzystej mocy. Z powyż-
szego wzoru wynika, że podzbiorów parzystej mocy jest tyle samo co podzbiorów mocy
nieparzystej.
Drugi dowód. Rozważmy funkcję f, która każdemu podzbiorowi
A ‚" {1, 2, . . . , n}
przyporządkuje podzbiór
f(A) = A •" {n} = (A - {n}) *" ({n} - A),
czyli różnicę symetryczną zbioru A i zbioru jednoelementowego {n}. Zauważmy, że
funkcja f łączy podzbiory w pary, ponieważ jeżeli f(A) = B, to f(B) = A. Rzeczywi-
Å›cie, jeżeli A zawiera n, to B = A - {n} i B •" {n} = A. Jeżeli natomiast A nie zawiera
n, to B = A *" {n} i również B •" {n} = A.
Pozostaje zauważyć, że z pary zbiorów A i f(A) jeden jest mocy parzystej i jeden
nieparzystej.
1.9. Zasada szufladkowa Dirichleta 13
1.9 Zasada szufladkowa Dirichleta
Zasada szyfladkowa Dirichleta w najprostszej postaci mówi, że jeżeli mamy k kul i chce-
my je rozmieścić w m < k szufladach, to w przynajmniej jednej szufladzie musi znalez
ć
się więcej niż jedna kula. W nieco ogólniejszej postaci brzmi ona następująco:
Twierdzenie 1.15 (Zasada szufladkowa Dirichleta) Jeżeli zbiór A podzielimy na k pod-
|A|
zbiorów, to przynajmniej jeden z tych podzbiorów ma lub więcej elementów.
k
|A|
Dowód Nie wprost. Przypuśćmy, że każdy z k podzbiorów ma mniej niż elementów.
k
|A|
Wtedy cały zbiór A ma mniej niż k = |A| elementów; sprzeczność.
k
Przykład 1.16 Wyobraz
my sobie urnę z białymi i czarnymi kulami, po 10. Jeżeli wylosu-
jemy trzy kule, to będą wśród nich dwie kule w tym samym kolorze, a jeżeli wylosujemy 9
kul, to będziemy mieli 5 kul w jednym kolorze.
Przykład 1.17 Przypuśćmy, że na przyjęciu jest n osób i niektorzy witają się przez poda-
nie dłoni. Pokażemy, że wśród nich znajdą się dwie osoby, które uścisnęły tyle samo dłoni.
Najpierw załóżmy, że każda osoba uścisnęła komuś dłoń. Mamy wtedy n osób, z których
każda uścisnęła dłoń od 1 do n - 1 razy. Muszą być więc dwie osoby z tą samą liczbą
uścisków. Jeżeli natomiast jest osoba, która nie uścisnęła dłoni nikomu, to wtedy nie może
być osoby, która uścisnęła n-1 dłoni. Czyli mamy n osób, z których każda uścisnęła dłoń
od 0 do n - 2 razy.
1.10 Zasada sumy
W najprostszej postaci zasada sumy, mówi że moc sumy dwóch zbiorów A i B jest równa
|A *" B| = |A| + |B| - |A )" B|.
Wyobraz
my sobie, że obliczając prawą stronę tej równości liczymy po kolei elementy
zbioru A i dla każdego elementu dodajemy +1 do ogólnej sumy, następnie liczymy ele-
menty zbiorów B i dla każdego dodajemy +1, a na końcu liczymy elementy przekroju
A )" B i dla każdego dodajemy -1. Zastanówmy się teraz jaki jest udział poszczególnych
elementów w tak powstałej sumie. Jeżeli jakiś element występuje tylko w A lub tylko w
B, to jego udział wynosi 1. Ale także, jeżeli należy do obu zbiorów A i B to jego udział
wynosi 1 = 1 + 1 - 1. Dlatego na końcu wynik będzie równy liczbie elementów, które
należą do jednego lub drugiego zbioru.
Przykład 1.18 Policzmy ile liczb naturalnych z przedziału od 1 do 30 jest podzielnych
przez 2 lub 3. Niech A2 oznacza zbiór liczb podzielnych przez 2, a A3 zbiór liczb podziel-
nych przez 3. Liczby podzielne przez 2 lub 3 tworzą zbiór A2 *" A3. Mamy
|A2| = 15, |A3| = 10 oraz |A2 )" A3| = 5.
A2 )" A3 zawiera liczby podzielne przez 2 i 3, czyli podzielne przez 6. Ze wzoru na sumÄ™
otrzymujemy:
|A2 *" A3| = 15 + 10 - 5 = 20.
14 Rozdział 1. Kombinatoryka
Podobnie możemy uzasadnić wzór na sumę trzech zbiorów:
|A *" B *" C| = |A| + |B| + |C| - |A )" B| - |A )" C| - |B )" C| + |A )" B )" C|.
Jeżeli zastosujemy podobne liczenie, to udział elementów, które należą tylko do jednego
zbioru, wynosi 1, tych, które należą do dwóch (ale nie do trzech naraz), wynosi 1+1-1 =
1, a tych, które należą do wszystkich trzech zbiorów, 1 + 1 + 1 - 1 - 1 - 1 + 1 = 1.
Przykład 1.19 Policzmy ile liczb z przedziału od 1 do 30 jest podzielnych przez 2, 3, lub
5. Niech A2 oznacza zbiór liczb podzielnych przez 2, A3 zbiór liczb podzielnych przez
3, a A5 podzielnych przez 5. Mamy |A2| = 15, |A3| = 10, |A5| = 6, |A2 )" A3| = 5,
|A2 )" A5| = 3, |A3 )" A5| = 2, |A2 )" A3 )" A5| = 1. Ze wzoru na sumÄ™ otrzymujemy:
|A2 *" A3 *" A5| = 15 + 10 + 6 - 5 - 3 - 2 + 1 = 22.
Jak widać, tylko osiem liczb mniejszych od 30 nie jest podzielnych przez 2, 3 lub 5; są to:
1, 7, 11, 13, 17, 19, 23, 29.
W następnym podrozdziale pokażemy jak można obliczyć sumy dowolnej skończonej
klasy zbiorów.
1.11 Zasada włączania i wyłączania
Zacznijmy od przykładu.
Przykład 1.20 W grupie 100 studentów 45 uprawia koszykówkę, 53 pływanie i 55 szachy.
Takich, którzy grają w koszykówkę i pływają, jest 28; takich, którzy grają w koszykówkę i
szachy, jest 32, takich, którzy grają w szachy i pływają, jest 35, a takich, którzy uprawia-
ją wszystkie trzy sporty, jest 20. Pytanie: ilu studentów nie uprawia ani koszykówki, ani
pływania? To zadanie można rozwiązać za pomocą tak zwanego diagramu Venna (rysu-
nek ??). Posługując sie diagramem łatwo policzyć, że:
8 studentów uprawia koszykówkę i pływanie, ale nie gra w szachy,
15 pływa i gra w szachy, ale nie gra w koszykówkę;
10 pływa, ale nie gra w ani w koszykówkę, ani w szachy,
i tak dalej.
Widać też, że 22 studentów nie uprawia żadnego sportu.
Zasada włączania i wyłączania pozwala rozwiązywać tego typu zadania bez diagra-
mów Venna. Niech X będzie naszym uniwersum, A1, . . . , An jego podzbiorami. Dla
każdego podzbioru I zbioru indeksów I ‚" {1, . . . , n} definiujemy zbiór:
AI = Ai,
i"I
przyjmujemy przy tym A" = X.
1.11. Zasada włączania i wyłączania 15
Rysunek 1.1: Diagram Venna
pływacy
22
10
15
8 20
5 12 8
szachiści
koszykarze
Przykład 1.21 W przykładzie 1.20 X to zbiór wszystkich studentów, A1 to uprawiający
koszykówkę, A2  pływanie, a A3  szachy:
" A{1,2} = A1 )" A2 to uprawiający koszykówkę i pływanie,
" A{1,3} = A1 )" A3 to uprawiający koszykówkę i szachy,
" A{2,3} = A2 )" A3 to uprawiający pływanie i szachy,
" A{1,2,3} = A1 )" A2 )" A3 to uprawiajÄ…cy wszystkie trzy sporty.
Twierdzenie 1.22 (zasada włączania i wyłączania) Niech X, będzie dowolnym skończo-
nym zbiorem (uniwersum), a A1, . . . , An dowolnymi jego podzbiorami. Wtedy liczba ele-
mentów uniwersum X, które nie należą do żadnego podzbioru Ai, wynosi:
(-1)|I||AI|. (1.7)
I‚"{1,...,n}
16 Rozdział 1. Kombinatoryka
Sumujemy tutaj po wszystkich podzbiorach I zbioru {1, . . . , n}, a AI oznacza przekrój
AI = Ai.
i"I
Przykład 1.23 Stosując zasadę włączania i wyłączania do przykładu ze studentami mo-
żemy teraz policzyć studentów, którzy nie uprawiają żadnego sportu:
|A"| - |A1| - |A2| - |A3| + |A{1,2}| + |A{1,3}| + |A{2,3}| - |A{1,2,3}|=
|X| - |A1| - |A2| - |A3| + |A1 )" A2| + |A1 )" A3| + |A2 )" A3|
-|A1 )" A2 )" A3|=
100 - 45 - 53 - 55 + 28 + 32 + 35 - 20=22.
Dowód Twierdzenia 1.22. Podobnie jak w poprzednim podrozdziale, żeby obliczyć su-
mę (1.7), liczymy elementy poszczególnych zbiorów AI, i dla każdego elementu dodaje-
my (-1)|I| do sumy (+1, gdy |I| jest parzyste, lub -1, gdy |I| jest nieparzyste). Udział
pojedynczego elementu x w tak utworzonej sumie wynosi
(-1)|I|,
x"AI
czyli jest równy sumie współczynników (-1)|I| dla tych podzbiorów I ‚" {1, . . . , n}, dla
których x " AI .
Jeżeli x nie należy do żadnego z podzbiorów Ai, to x jest liczony tylko raz, w zbio-
rze A", i jego udział w sumie (1.7) wynosi 1. Przypuśćmy teraz, że x należy do jakiś
podzbiorów i niech
J = {i " {1, . . . , n} : x " Ai},
czyli J to indeksy tych podzbiorów, które zawierają x, niech |J| = j. Zauważmy teraz,
że x " AI wtedy i tylko wtedy, gdy I ‚" J. RzeczywiÅ›cie x " AI = Ai wtedy i
i"I
tylko wtedy, gdy x " Ai, dla każdego i " I, czyli gdy I ‚" J. Tak wiÄ™c udziaÅ‚ elementu
x w sumie (1.7) wynosi:
(-1)|I|.
I‚"J
Jest to suma po wszystkich podzbiorach I zbioru J. Uporządkujmy teraz składniki tej
j
sumy według mocy podzbiorów I. Mamy podzbiorów mocy i, więc:
i
j
j
(-1)|I| = (-1)i = (1 - 1)j = 0.
i
I‚"J i=0
Przedostatnia równość wynika ze wzoru Newtona. Tak więc wkłady elementów, które nie
należą do żadnego Ai, wynoszą po 1, a wkłady tych elementów, które należą do jakiegoś
Ai, wynoszą po 0. A zatem suma (1.7) zlicza elementy nie należące do żadnego Ai.
Aby policzyć moc sumy zbiorów
n
Ai
i=1
n
możemy wykorzystać wzór (1.7), przy założeniu, że X = Ai. Mamy wtedy
i=1
1.12. Przestawienia 17
Twierdzenie 1.24
n
Ai = - (-1)|I||AI |.
I‚"{1,...,n}
i=1
I="

1.12 Przestawienia
Przestawieniem będziemy nazywać permutację bez punktu stałego, czyli taką permutację,
w której żaden element nie stoi na swoim miejscu. Wykorzystamy teraz zasadę włączania
i wyłączania, do policzenia liczby przestawień w zbiorze n-elementowym.
Twierdzenie 1.25 Liczba przestawień (permutacji bez punktów stałych) w zbiorze n-
elementowym wynosi:
n
(-1)i
n! .
i!
i=0
Dowód. Niech X = Sn będzie zbiorem wszystkich permutacji na zbiorze {1, . . . , n},
a Ai zbiorem permutacji, w których i jest punktem stałym, to znaczy Ai = {Ą " Sn |
Ä„(i) = i}. Moc zbioru Ai wynosi:
|Ai| = (n - 1)!,
ponieważ w zbiorze Ai są te permutacje, które permutują wszystkie n - 1 elementów
oprócz i-tego. Podobnie moc zbioru AI wynosi:
|AI | = Ai = (n - |I|)!,
i"I
bo teraz w AI permutujemy n - |I| elementów, wszystkie oprócz tych, które należą do I.
Permutacje bez punktów stałych to te permutacje, które nie należą do żadnego ze zbiorów
Ai. Z zasady włączania i wyłączania ich liczba wynosi
(-1)|I|(n - |I|)!.
I‚"{1,...,n}
n
Pogrupujmy teraz składniki sumy według mocy zbiorów I. Mamy podzbiorów mocy
i
i. Dla każdego z nich składnik sumy wynosi (-1)i(n - i)!, tak więc liczba przestawień
wynosi:
n
n
(-1)i (n - i)!.
i
i=0
n n!
Twierdzenie wynika teraz z równości (n - i)! = .
i i!
18 Rozdział 1. Kombinatoryka
1.13 Generowanie obiektów kombinatorycznych
W tym rozdziale zajmiemy siÄ™ algorytmami generujÄ…cymi (wypisujÄ…cymi) obiekty kom-
binatoryczne. Przedstawione algorytmy będą działaly według następującego schematu:
" Wypisujemy pierwszy obiekt.
" Powtarzamy, aż do napotkania ostatniego obiektu:
Przetwarzamy bieżący obiekt tak, aby otrzymać następny obiekt.
Takie algorytmy mają tą zaletę, że nie wymagają dużo pamięci. Należy tylko pamię-
tać jeden obiekt. Algorytmy generujące obiekty są używane w przypadku, gdy chcemy
sprawdzić wszystkie obiekty danej klasy lub wtedy, gdy chcemy wylosować obiekt da-
nej klasy. Przypuśćmy, na przykład, że chcemy wylosować jakiś 3 elementowy podzbiór
7
zbioru {1, . . . , 7}. W tym celu losujemy liczbę naturalną k od 1 do = 35, a następnie
3
generujujemy podzbiory, aż do elementu k.
1.13.1 Generowanie podzbiorów
Algorytm wypisujÄ…cy wszystkie podzbiory zbioru {1, . . . , n}:
Pierwszy podzbiór: A = ".
By uzyskać następny po A podzbiór:
Wybieramy największy element a " {1, . . . , n} nie należący do A,
czyli a = max{1 d" i d" n | i " A}
/
Jeżeli takiego a nie ma, to
koniec algorytmu, zbiór A = {1, . . . , n} jest ostatnim podzbiorem.
W przeciwnym przypadku
dodajemy a do A i usuwamy z A wszystkie elementy większe od a.
Przykład 1.26 Dla n = 3 powyższy algorytm wypisze po kolei następujące zbiory: ",
{3}, {2}, {2, 3}, {1}, {1, 3}, {1, 2}, {1, 2, 3}.
Funkcje charakterystyczne wypisywanych podzbiorów, traktowane jako binarny za-
pis liczb, tworzą ciąg kolejnych liczb od 0 do 2n - 1. Szukając następnego elemenetu
algorytm postępuje podobnie jak algorytm zwiększania o jeden liczby w systemie dwój-
kowym.
1.13.2 Generowanie k-elementowych podzbiorów
Algorytm generujÄ…cy k elementowe podzbiory zbioru {1, . . . , n}:
Pierwszy k-podzbiór to {1, . . . , k};
Przypuśćmy, że ostatnio wygenerowany podzbiór to A = {a1, . . . , ak},
gdzie a1 < . . . < ak.
Aby wygenerować następny podzbiór:
znajdujemy najmniejsze takie i, że ai + 1 " A;
/
1.13. Generowanie obiektów kombinatorycznych 19
jeżeli ai = n, to
A = {n - k + 1, . . . , n} jest ostatnim podzbiórem.
jeżeli ai < n, to
zwiększamy ai o jeden,
elementymniejsze od ai zamieniamy na i - 1 najmniejszych liczb,
to znaczy aj := j dla j < i.
Przykład 1.27 Dla n = 6 i k = 4 algorytm wypisze po kolei następujące podzbiory
(podajemy je bez nawiasów i przecinków)
1234, 1235, 1245, 1345, 2345, 1236, 1246, 1346, 2346, 1256, 1356, 2356, 1456, 2456, 3456.
Zauważmy, że w przykładzie najpierw wypisywane są 4-podzbiory niezawierające 6:
1234, 1235, 1245, 1345, 2345
a póz
niej 4-podzbiory zawierajÄ…ce 6
1236, 1246, 1346, 2346, 1256, 1356, 2356, 1456, 2456, 3456,
które otrzymywane są w ten sposób, że do kolejnych 3-podzbiorów zbioru {1, . . . , 5} do-
pisywana jest 6. Jest to ogólna zasada działania tego algorytmu: aby wypisać j-podzbiory
zbioru {1, . . . , i} algorytm najpierw wypisuje j podzbiory zbioru {1, . . . , i - 1}, a na-
stępnie podzbiory zawierające element i (są one otrzymywane przez dodawanie i do j -1
podzbiorów zbioru {1, . . . , i - 1}). W powyższym przykładzie wśrod podzbiorów zawie-
rających 6 najpierw mamy te, które są utworzone z 3-podzbiorów {1, 2, 3, 4} z dopisaną
6:
1236, 1246, 1346, 2346,
a po nich następują te, które są utworzone z 2-podzbiorów {1, 2, 3, 4}, z dopisaną 5 i 6:
1256, 1356, 2356, 1456, 2456, 3456.
Dlatego, kiedy w bieżącym zbiorze A = {a1, . . . , ak} algorytm znalazł takie i, że ai+1 "
/
A, to znaczy, że algorytm jest w trakcie wypisywania tych podzbiorów, które zawierają
ai+1, . . . , ak (wszystkie większe od ai + 1), plus jakiś i-podzbiór zbioru {1, . . . , ai +
1}. Zbiór A jest ostatnim podzbiorem, w którym występują ai+1, . . . , ak, oraz jakiś i-
podzbiór zbioru {1, . . . , ai}, a nie występuje ai + 1. Według opisanej wyżej zasady teraz
powinny nastąpić podzbiory, które zawierają ai + 1 plus jakiś (i - 1)-podzbiór zbioru
{1, . . . , ai}, plus elementy ai+1, . . . , ak. Pierwszy z nich to podzbiór
{1, . . . , i - 1, ai + 1, ai+1 . . . , ak}.
I taki element jest wypisywany po zbiorze A.
20 Rozdział 1. Kombinatoryka
1.13.3 Generowanie permutacji
Algorytm generowania permutacji zbioru {1, . . . , n}:
Pierwsza permutacja to identyczność, czyli ai = i, dla 1 d" i d" n.
Aby wypisać następną po (a1, . . . , an) permutację:
Znajdujemy największe j, 1 d" j d" n - 1 spełniające warunek aj < aj+1,
jeżeli takiego j nie ma, to
bieżąca permutacja jest ostatnia,
jeżeli takie j istnieje, to
zamieniamy aj z najmniejszym ak takim, że ak > aj oraz k > j,
następnie odwracamy porządek elementów aj+1, . . . , an.
Przykład 1.28 Oto 10 pierwszych permutacji czteroelementowych
1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431,
Alorytm wypisuje permutacje w porządku rosnącym, jeżeli potraktujemy permutacje jako
liczby zapisane z bazą n + 1, a liczby 1, . . . , n jako cyfry w tym systemie. Na przykład,
przypuśćmy, że bieżącą permutacją jest (436521). Algorytm znajduje j = 2 i aj = 3.
Wtedy ta permutacja jest ostatnią (największą) permutacją spośród permutacji zaczynają-
cych się od (43...), bo od pozycji trzeciej mamy ciąg malejący (..6521) i jest to najwięk-
szy ciąg jaki można utworzyć z elementów 1,2,5,6. Teraz powinny nastąpić permutacje
zaczynające się od (45...) (czwórki na pierwszym miejscu nie zmieniamy, a trójka na
drugim miejscu powinna być zamieniona przez następną spośrod liczb stojących za nią,
czyli przez 5). Pierwszą taką permutacją jest ta, w której pozostałe elementy rosną, czyli
(451236).
1.14 Zadania
1. Ile numerów rejestracyjnych samochodów można utworzyć, jeżeli każdy numer
składa się z trzech liter i czterech cyfr?
Ile numerów rejestracyjnych można utworzyć, jeżeli będziemy dodatkowo wyma-
gać, aby każdy numer zaczynał się od spółgłoski?
2. Ile jest ciągów zero-jedynkowych długości 4, w których pierwszy i trzeci bit są
jednakowe? Wypisz je wszystkie.
3. Jaka część wszystkich ciągów zero-jedynkowych długości n > 3, posiada iden-
tyczne bity na pierwszej i trzeciej pozycji?
4. Ile jest liczb trzycyfrowych w systemie: a) dziesiętnym, b) dwójkowym, c) trójko-
wym? Ile jest liczb trzycyfrowych z różnymi cyframi.
5. Ile liczb trzycyfrowych zawiera cyfrÄ™ 2 lub 3?
6. Na ile sposobów można posadzić n osób przy okrągłym stole. Nie robi różnicy,
gdzie kto siedzi, ale jakich ma sąsiadów po lewej i prawej.
1.14. Zadania 21
7. Wypisz wszystkie funkcje ze zbioru {a, b} w zbiór {x, y, z}. Które z nich są róż-
nowartościowe?
8. Wypisz wszystkie funkcje ze zbioru {1, 2, 3} w zbiór {1, 2}. Które z nich są mo-
notoniczne?
9. Ile jest funkcji f ze zbioru {1, . . . , n} w zbiór {a, b, c}? ILe spośród nich spełnia
warunek f(1) = a, a ile spełnia warunek f(1) = f(2)?

10. Mamy dowolny graf G = (V, E). Na ile sposobów można pokolorować dwoma
kolorami jego wierzchołki? Na ile sposobów można pokolorować dwoma kolorami
wierzchołki tak, aby zgóry wybrana krawędz
e = {u, v} miała końce w różnych
kolorach?
11. Ile jest monotonicznych ciągów zerojedynkowych długości n?
12. Mamy dwie permutacje:
1 2 3 4 5
Ä„1 =
2 5 4 3 1
1 2 3 4 5
Ä„2 =
1 5 4 3 2
-1 -1
Oblicz Ą1 ć% Ą2, Ą2 ć% Ą1, Ą1 , Ą2 .
13. Ile słów można utworzyć z liter słowa ULICA (litery nie mogą się powtarzać)?
14. Mamy trójkąt równoboczny o wierzchołkach a, b, c. Jakim przekształceniom odpo-
wiadają permutacje jego wierzchołków?
15. Mamy czworościan o wierzchołkach a, b, c, d. Jakim przekształceniom odpowia-
dają permutacje jego wierzchołków?
16. Wypisz wszystkie 4-elementowe permutacje spełniające warunek Ą(2) = 3.
17. Ile jest 6-elementowych permutacji spełniających warunek: a) Ą(2) = 3; b) a)
Ä„(2) = 3 oraz pi(3) = 2.
18. W ilu permutacjach zbioru {1, . . . , n} jedynka stoi przed dwójką (niekoniecznie
bezpośrednio).
19. Wypisz wszystkie podzbiory zbioru {x, y, z}.
20. Na ile sposobów można wybrać dwuosobową delegację z grupy pięcioosobowej?
21. Wypisz funkcje charakterystyczne wszystkich trzyelementowych podzbiorów zbio-
ru {1, 2, 3, 4, 5}.
22. W grupie jest pięć dziewcząt i pięciu chłopców; a) na ile sposobów można wy-
brać podgrupę składającą się: a) z trzech dziewcząt i dwóch chłopców? b) Na ile
sposobów można utworzyć pięć par z chłopcem i dziewczyną w każdej parze?
22 Rozdział 1. Kombinatoryka
23. Znana jest zabawka dla dzieci składająca się z dwunastu sześciennych klocków z
naklejonymi na ściankach fragmentami obrazków. Na ile sposobów można ułożyć
te klocki w prostokąt (trzy rzędy po cztery klocki w rzędzie)?
n n-1
24. Udowodnij wzór k = n
k k-1
Wskazówka. Policz na dwa różne sposoby, ile k-elementowych drużyn z kapitanem
można utworzyć ze zbioru n sportowców.
2
n
n 2n
25. Udowodnij wzór = .
k=0 k n
Wskazówka. Policz na dwa różne sposoby, ile n-elementowych grup można utwo-
rzyć w klasie złożonej z n chłopców i n dziewcząt.
26. Na ile sposobów można wybraż trzy liczby spośród liczb od 1 do 60, tak aby ich
suma była: a) nieparzysta; b) parzysta; c) podzielna przez 3.
n
n n
27. Udowodnij, że jest największe dla k = i k = .
k 2 2
2n 22n
28. Udowodnij, że e" .
n 2n+1
29. Rozwiń wielomian (1 + t)8.
n
n
30. Udowodnij, że 2i = 3n.
i=0 i
31. Udowodnij wzory:
n n - 1 n - 2 3 2
= + + · · · + +
3 2 2 2 2
n n - 1 n - 2 k k - 1
= + + · · · + + .
k k - 1 k - 1 k - 1 k - 1
Wskazówka. Należy osobno policzyć podzbiory, w których 1 jest najmniejszym
elemnetem, osobno te, w których 2 jest najmniejszym elementem i tak dalej.
32. Ile jest ściśle rosnących funkcji ze zbioru {1, . . . , n} w zbiór {1, . . . , m}.
33. Ile maksymalnie krawędzi może mieć graf o n wierzchołkach? Ile maksymalnie
krawędzi może mieć graf skierowany o n wierzchołkach?
34. Na ile sposobów można pokolorować dwoma kolorami krawędzie pełnego grafu z
n wierzchołkami?
35. Mamy zbiór wierzchołków V = {1, . . . , n}. a) Ile jest grafów ze zbiorem wierz-
chołków V ? b) W ilu grafach {1, 2} jest krawędzią? c) Ile jest grafów skierowanych
z zbiorem wierzchołków V ?
36. W urnie są kule białe i czarne. Ile kul trzeba wyciągnąć z urny, żeby mieć pewność,
że wśród wyciągniętych będą: a) dwie w tym samym kolorze, b) siedem w tym
samym kolorze. Jakie będą odpowiedzi w przypadku, gdy w urnie będą kule w
trzech kolorach.
1.15. Problemy 23
m
37. Ułamek przedstawiamy w postaci dziesiętnej. Udowodnij, że okres tego ułamka
k
jest nie większy niż k.
38. Wylosowano n + 1 liczb ze zbioru {1, 2, . . . , 2n}. Pokaż, że któraś z nich jest
wielokrotnością innej.
Wskazówka: Mamy n szuflad, ponumerowanych kolejnymi liczbami nieparzystymi
1, 3, 5, ... , 2n - 1. Każdą z wylosowanych liczb k " {1, . . . , 2n} wkładamy do
szuflady z numerem m, jeżeli k = 2rm dla jakiegoś r e" 0.
39. Ze zbioru liczb od 1 do 107 wybrano 10 liczb. Pokaż, że w wylosowanym zbiorze
istnieją dwa rozłączne podzbiory z tą samą sumą.
40. Przedstaw wzór na sumę czterech zbiorów A, B, C i D.
41. Ile elementów zawiera różnica symetryczna A •" B?
42. Ile ciągów długości n o elementach ze zbioru {A, B, C, D} nie zawiera A lub nie
zawiera B, lub nie zawiera C.
43. Wyznacz liczbę elementów |A )" B )" C| oraz |C|, wiedząc, że |A| = 10, |B| = 9,
|A )" B| = 3, |A )" C| = 1, |B )" C| = 1 oraz |A *" B *" C| = 18.
44. Oblicz ile liczb mniejszych od 100 jest podzielnych przez 2, 3 lub 5.
45. Oblicz ile liczb mniejszych od 100 nie jest podzielnych przez żadną z liczb 2, 3,
5 lub 7. Udowodnij, że wszystkie te liczby oprócz 1 są pierwsze. Ile jest liczb
pierwszych mniejszych od 100?
46. Za pomocą algorytmów opisanych w podrozdziale o generowaniu obiektów kom-
binatorycznych wypisz wszystkie:
a) podzbiory zbioru {1, 2, 3, 4},
b) 2 elementowe podzbiory zbioru {1, 2, 3, 4, 5},
c) 3 elementowe podzbiory zbioru {a, b, c, d, e, f}.
d) 14 kolejnych permutacji zbioru {1, 2, 3, 4, 5, 6} poczynajÄ…c od permutacji
456321 (lub od permutacji 246531).
47. Napisz programy realizujÄ…ce opisane w tym rozdziale algorytmy generowania obiek-
tów kombinatorycznych.
1.15 Problemy
1.15.1 Najkrótsze drogi
Wyobraz
my sobie siatkÄ™ prostokÄ…tnych ulic z m + 1 ulicami biegnÄ…cymi pionowo (w
kierunku północ południe) i k + 1 ulicami biegnącymi poziomo (w kierunku wschód
zachód). Rysunek 1.2 przedstawia taką siatkę dla m = 6 i k = 4.
24 Rozdział 1. Kombinatoryka
Rysunek 1.2: Siatka ulic dla m = 6 i k = 4 z zaznaczoną jedną z najkrótszych dróg z A
do B.
B
A
k+m
1. Udowodnij, że liczba najkrótszych dróg z punktu A do punktu B wynosi .
k
2. Udowodnij, że liczba funkcji niemalejących ze zbioru {1, . . . , n} w zbiór {1, . . . , k}
k+n-1
wynosi .
k-1
3. Ile jest funkcji monotonicznych ze zbioru {1, . . . , n} w zbiór {1, . . . , k}?
Wskazówki. Najkrótsze drogi z A do B składają się z ciągu k + m odcinków, z których
m jest poziomych i k pionowych.
Funkcje niemalejące ze zbioru {1, . . . , n} w zbiór {1, . . . , k} można skojarzyć z naj-
krótszymi drogami w sieci ulic w prostokÄ…cie n × (k - 1).
1.15.2 Rozmieszczanie przedmiotów w pudełkach.
Przypuśćmy, że mamy n nierozróżnialnych kul. Rozważ na ile sposobów można rożłożyć
te kule do k rozróżnialnych pudełek.
n+k-1
1. Udowodnij, że istnieje sposobów rożłożenia n kul do k pudełek.
k-1
2. Na ile sposobów można rozmieścić: a) 2 kule w trzech szufladach, b) 3 kule w
dwóch szufladach. Wypisz wszystkie takie rozmieszczenia.
Wskazówka. Każde rozmieszczenia n kul w k pudełkach może być przedstawione jako
ciąg zer i jedynek długosci n + k - 1, w którym występuje dokładnie k - 1 jedynek. Zera
symbolizują kule a jedynki przegrody pomiędzy pudełkami. Na przykład ciąg 00110100
przedstawia rozłożenie pięciu kul do czterech pudełek, w których pierwsze pudełko za-
wiera dwie kule, drugie jest puste, trzecie zawiera jednÄ… kule, a czwarte dwie kule.
1.15. Problemy 25
1.15.3 Wybór n przedmiotów k rozróżnialnych typów
Wyobraz
my sobie, że mamy przedmioty w k różnych typach, że liczba przedmiotów każ-
dego typu jest nieograniczona i że przedmioty jednego typu są nierozróżnialne. Zasta-
nówmy się na ile sposobów można wybrać n przedmiotów spośród tych k typów, przy
założeniu, że dopuszczalne są powtórzenia typów i że kolejność wybranych przedmiotów
nie jest istotna.
n+k-1
1. Pokaż, że można to zrobić na sposobów.
k-1
2. Ile jest rozwiÄ…zaÅ„ równania x1 + x2 + · · · + xk = n wÅ›ród nieujemnych liczb
całkowitych? Liczba n jest stałą, a x1, ... ,xk to zmienne.
3. Na ile sposobów można wybrać 5 monet jeżeli mamy nieograniczone zapasy zło-
tówek i dwuzłotówek? Wypisz wszystkie takie sposoby.
4. Na ile sposobów można wybrać 5 monet jeżeli mamy nieograniczone zapasy zło-
tówek, dwuzłotówek i pięciozłotówek?
Wskazówka. Wybory przedmiotów k typów są równoważne rozkładaniu nierozróżnial-
nych kul do k szuflad. Włożenie kuli do i-tej szuflady oznacza, że jest ona i tego typu.
1.15.4 Kombinacje z powtórzeniami
k-elementowe kombinacje z powtórzeniami ze zbioru n-elementowego są to k-elementowe
wybory elementów zbioru n-elementowego, w których elementy mogą się powtarzać i
w których nie jest istotna kolejność wybieranych elementów. Na przykład, mamy czte-
ry trzyelementowe kombinacje z powtórzeniami ze zbioru dwuelementowego {1, 2}; oto
one: (1, 1, 1), (1, 1, 2), (1, 2, 2), (2, 2, 2).
Udowodnij, że liczba k-elementowych kombinacji z powtórzeniami ze zbioru n-
n+k-1
elementowego wynosi .
k
Wskazówka. Takie kombinacje odpowiadają wyborowi k elementów n typów.
1.15.5 Permutacje z powtórzeniami
Przypuśćmy, że mamy n przedmiotów k różnych typów oraz, że przedmiotów typu i jest
ni. Rozważmy ustawienia wszystkich tych przedmiotów w ciąg. Przy tym dwa ustawienia
są rozróżnialne tylko, jeżeli na jakiejś pozycji mają przedmioty różnych typów.
n!
1. Pokaż, że takich rozróżnialnych ustawień jest
n1!n2!···nk!
2. Ile słów można utworzyć z liter słowa MAMA (litery M i A mogą wystąpić po dwa
razy)? Wypisz wszystkie te słowa.
3. Ile słów można utworzyć z liter słowa MATEMATYKA?
26 Rozdział 1. Kombinatoryka
1.15.6 Podziały uporządkowane
Niech A będzie dowolnym zbiorem n elementówy i niech n1 . . . nk będą dowolnymi
liczbami naturalnymi takimi, że n1 + . . . + nk = n. Rozważmy rozbicia zbioru A na k
podzbiorów A1, . . . , Ak, takich, że |Ai| = ni dla każdego 1 d" i d" k. Zakładamy przy
tym, że kolejność podzbiorów jest istotna.
n!
1. Pokaż, że takich rozbić jest .
n1!n2!···nk!
2. Na ile sposobów można rozdać 52 kartry na cztery osoby?
3. Na ile sposobów można utworzyć 5 par z 10 osób?
4. Uogólnij wzór na dwumian Newtona na przypadek (a+b+c)n lub (a1+· · ·+ak)n.
1.15.7 Permutacje bez punktów stałych
Udowodnij, że liczba przestawień (permutacji bez punktów stałych) w zbiorze n-elementowym
n!
jest równa zaokrągleniu liczby do najbliższej liczby naturalnej; e jest podstawą loga-
e
rytmu naturalnego.
" (-1)i
Wskazówka. Skorzystaj z twierdzenia 1.25, z rozwinięcia: e-1 = oraz z
i=0 i!
" (-1)i 1
oszacowania: d" .
i=n+1 i! (n+1)!
1.15.8 Liczba surjekcji
Udowodnij, że liczba surjekcji (funkcji na całą przeciwdziedzinę) ze zbioru n-elementowego
na zbiór k-elementowy wynosi:
k
k
(-1)i (k - i)n.
i
i=0
Wskazówka. Skorzystaj z zasady włączania i wyłączania dla zbioru wszystkich funkcji ze
zbioru {1, . . . , n} w zbiór {1, . . . , k}. Zbiór Ai to funkcje, które nie mają elementu i w
obrazie.
1.15.9 Twierdzenie Ramseya
W tym podrozdziale będziemy rozważać grafy pełne, których krawędzie są pokolorowane
dwoma kolorami: białym lub czarnym. Dokładniej, mamy graf pełny G = (VG, EG) z
n = |VG| wierzchołkami i ze zbiorem krawędzi EG = {{u, v} | u, v " VG}, oraz funkcję
c : VG {b, c} kolorującą krawędzie tego grafu. Interesuje nas problem, kiedy w grafie
G istnieje klika H = (VH , EH) (podgraf pełny) z k wierzchołkami, której wszystkie
krawędzie mają ten sam kolor.
1.15. Problemy 27
1. Pokaż, że w każdym grafie z sześcioma wierzchołkami istnieje jednobarwny trójkąt
(trzy wierzchołki połączone krawędziami w tym samym kolorze).
Wniosek. W każdej grupie 6 osobowej albo są trzy osoby, które się wzajemnie
znają, albo trzy, które się nie znają.
2. Pokaż, że istnieje graf z pięcioma wierzchołkami, w którym nie ma jednobarwnego
trójkąta.
3. Pokaż, że w każdym grafie z 20 wierzchołkami istnieją cztery wierzchołki połączo-
ne krawędziami w tym samym kolorze.
Wskazówka. Pokaż, że istnieje 10 wierzchołków, które z pierwszym są połączone
tym samym kolorem, na przykład białym. Pokaż, że wśród każdych 10 wierzchoł-
ków albo są trzy wierzchołki połączone tylko białymi krawędziami, albo cztery
połączone tylko czarnymi (z dowolnego wierzchołka albo wychodzą cztery białe,
albo sześć czarnych krawędzi).
4. Pokaż, że w każdym grafie z 18 wierzchołkami istnieją cztery wierzchołki połączo-
ne krawędziami w tym samym kolorze.
Wniosek. W każdej grupie conajmniej 18 brydżystów albo są cztery osoby, które
już ze sobą grały (każda z każdą w parze), albo cztery, które ze sobą nigdy nie grały
(żadna z żadną).
Wskazówka. Podobnie jak w punkcie 3. Udowodnij, że wśród każdych 9 wierz-
chołków albo są trzy wierzchołki połączone tylko białymi krawędziami, albo cztery
połączone tylko czarnymi. Pokaż, że nie jest możliwe, aby z każdego wierzchołka
wychodziły trzy białe i pięć czarnych krawędzi.
Udowodnij następujące
Twierdzenie 1.29 (Twierdzenie Ramseya) . Dla każdego k istnieje Rk, takie, że każ-
dy graf z n > Rk wierzchołkami i dowolną funkcją kolorującą jego krawędzie posiada
podgraf z k wierzchołkami i wszystkimi krawędziami w jednym kolorze.
Szkic dowodu. Niech N0 będzie dużą liczbą. Pod koniec dowodu okaże się jak dużą.
Niech graf posiada N0 wierzchołków i niech te wierzchołki będą ustawione w ciąg. We-
żmy pierwszy wierzchołek x1. Na podstawie zasady szufladkowej istnieje kolor c1 "
{b, c} oraz podciąg N1 = N0/2 wierzchołków, które są z x1 połączone kolorem c1. Po-
zostałe wierzchołki usuwamy. Niech x2 będzie pierwszym który został. Znowu istnieje
kolor c2 oraz podciąg N2 = (N1 - 1)/2 wierzchołków stojących za x2, które wszystkie
są z x2 połączone kolorem c2 (kolory c1 i c2 mogą być takie same albo różne). Pozostałe
wierzchołki usuwamy. Powtarzamy to 2k - 1 razy i otrzymamy ciąg wierzchołków x1,
x2, ... , x2k, takich, że każdy wierzchołek xi, 1 d" i d" 2k - 1 jest połączony kolorem
ci ze wszystkimi wierzchołkami stojącymi za nim. Kolory c1, ... , c2k-1 nie muszą być
jednakowe, ale wszystkie należą do zbioru dwóch kolorów: biały i czarny. Dlatego na
podstawie zasady szufladkowej istnieje podciąg k wierzckołków, z których każde dwa
są połączone tym samym kolorem. Liczba N0 powinna być tak duża, aby możliwe były
wszystkie opisane wyżej wybory. Na liczbę Rk należy wybrać najmniejszą taką liczbę.
28 Rozdział 1. Kombinatoryka
Udowodnij Twierdzenie Ramseya dla przypadku, gdy kolorujemy nie pary wierzchoł-
ków, ale trójki wierzchołków. Dokładniej funkcja kolorująca przypisuje kolory trójkom
różnych wierzchołków c : {{u, v, w} | u, v, w " VG u = v, v = w, u = w} {b, c}.

Szkic dowodu. Dowód prowadzimy podobnie jak w twierdzeniu Ramsey a. Bierzemy
wierzchołek x1. Wśród pozostałych wierzchołków kolorujemy pary: para {u, v} ma ko-
lor biały, jeżeli trójka {x1, u, v} ma kolor biały. Z twierdzenia Ramsey a 1.29 wynika,
że jeżeli liczba wierzchołków N0 jest dostatecznie duża, to istnieje podciąg z N1 wierz-
chołkami i parami w jednym kolorze. Pozostałe wierzchołki usuwamy. Teraz każda trójka
zawierająca x1 ma taki sam kolor. Bierzemy następny wierzchołek x2 itd..
Udowodnij Twierdzenie Ramseya dla 3 (lub m) kolorów.
1.15.10 Twierdzenie Halla o różnych reprezentantach
Wyobraz
my sobie n podzbiorów A1, ... ,An zbioru {1, . . . , n}. Interesuje nas, kiedy dla
tych podzbiorów istnieje zestaw różnych reprezentantów, czyli ciąg n różnych liczb a1,
... ,an takich, że ai " Ai.
A
atwo zauważyć, że aby istniał zestaw różnych reprezentantów musi być spełniony
następujący:
Warunek Halla:
Dla każdego podzbioru J ‚" {1, ..., n}
Aj e" |J|.
j"J
Pokaż, że jest to także warunek wystarczający.
Wskazówka. Szkic dowodu (przez indukcję). Powiemy, że zbiór J jest krytyczny, jeżeli
Aj = |J|. Załóżmy najpierw, że istnieje podzbiór krytyczny J różny od całego
j"J
zbioru {1, . . . , n}. Niech C = Aj.
j"J
Na podstawie indukcji można w nim znalez
ć reprezentatów. Reszta spełnia warunek
Halla. Istotnie, niech I ‚" {1, . . . , n} - J oraz K = I *" J. Z tego, że K speÅ‚niaÅ‚ warunek
Halla na początku wynika, że podzbiór I spełnia warunek Halla dla zbiorów Bi = Ai-C.
Bi = (Ai - C) = (Ai) - |C| e" |K| - |J| = |I|.
i"I k"K k"K
Jeżeli nie ma właściwego podzbioru krytycznego, to na a1 wybieramy dowolny elem-
net z A1, a reszta spełnia warunek Halla.