kombinatoryka 2 id 242495

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 ˛

a 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 ˛

a 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 X d(v) = 2m,

v∈V

gdzie d(v) oznacza stopień wierzchołka v , czyli liczbę krawędzi wychodz ˛

acych 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 P

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.

Rozdział 1. Kombinatoryka

1.2

Ci ˛

agi

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 ˛

agó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 ˛

agów długości k o elementach ze zbioru n -elementowego wy-

nosi nk .

1.3. Funkcje

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 ˛

(2, 2, 2, 2)

opisuje funkcję stał ˛

a, która w całej swojej dziedzinie przyjmuje wartość 2 , a ci ˛

(1, 2, 3, 3)

opisuje funkcję f , która przyjmuje następuj ˛

ace 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 ˛

agi 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},

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 ˛

ac od (n − k + 1) , a kończ ˛

na n .

Dowód. Jeżeli budujemy ciąg bez powtórze ń, to na pierwszy element ciągu możemy wybrać 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. 2

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

Funkcja silnia n! określona jest dla n > 0 w następujący sposób:

n! =

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! ≈ 2433 · 1015.

Dla przybliżonego obliczania silni korzysta się ze wzoru Stirlinga:

√

n! ≈ e−nnn 2πn.

(1.1)

Dla każdego n zachodzą również następujące oszacowania:

√

n n

√

n n

2πn

≤ n! ≤ 2πn

e 12 .

(1.2)

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)

Przykład 1.9 Permutacja:

1 2 3 4

π =

2 1 4 3

jest funkcj ˛

a, która przyjmuje następuj ˛

ace 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:

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

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

weź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 ˛

ag (0, 1, 1, 0, 1) , a ci ˛

ag (1, 0, 1, 1, 0) opisuje funkcję charakterystyczn ˛

a 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

Rozdział 1. Kombinatoryka

Jest to tak zwany symbol Newtona. Inaczej, n 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:

= 1,

= 4,

= 6,

= 4,

= 1.

Z definicji wynika, że jeżeli k > n, to n = 0. Zachodzą dwa wzory:

(1.3)

n − k

n + 1

(1.4)

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

zawierają. Podzbiorów nie zawierających n + 1 jest n, bo wszystkie k elementów trze-

ba wybrać ze zbioru {1, . . . , n}. Podzbiorów zawierających n + 1 jest

n , bo k − 1

k−1

elementów trzeba wybrać ze zbioru {1, . . . , n}. Razem wszystkich k-elementowych pod-

zbiorów zbioru {1, . . . , n, n + 1} jest n +

n .

k−1

Korzystając z równości (1.4), możemy obliczać symbole Newtona rekurencyjnie. Naj-

pierw mamy 0 = 1, ponieważ jest jeden zeroelementowy (pusty) podzbiór zbioru zero-

elementowego (pustego). Jeżeli mamy już policzone symbole Newtona dla n, to możemy

liczyć, ile jest podzbiorów zbioru (n + 1)-elementowego. Zaczynamy od n+1 = 1

n+1

oraz n+1 = 1, a następnie korzystamy z równania (1.4). Metodę tę ilustruje tak zwany

trójk ˛

at Pascala:

W n-tym wierszu (wiersze numerowane są od n = 0) znajdują się symbole Newtona:

n n n

. . .

Na skraju znajdują się jedynki, ponieważ n = n = 1. k-ty element w n-tym wierszu

dla 1 ≤ k ≤ n − 1 jest sumą dwóch elementów stojących bezpośrednio nad nim:

n − 1

k − 1

1.8. Dwumian Newtona

Jeżeli 0 ≤ k ≤ n, to symbol Newtona można też obliczyć ze wzoru:

n(n − 1) · · · (n − k + 1)

(1.5)

lub

(1.6)

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 ≤

k ≤ n:

n(n − 1) · · · (n − k + 1)

n − 1

n − k + 1

n k

· · ·

≥

k(k − 1) · · · 1

k − 1

Ponieważ, jak łatwo sprawdzić n−i ≥ n dla każdego 1 ≤ i ≤ k − 1. Korzystając z

k−i

nierówności k! ≥ ( k )k wyprowadzonej ze wzoru Stirlinga (1.2), otrzymujemy górne

ograniczenie:

n(n − 1) · · · (n − k + 1)

en 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 ≥ 0 zachodzi:

(1 + t)n =

tk.

k=0

Dowód, przez indukcję. Wzór jest oczywisty dla n = 0. Załóżmy teraz, że jest prawdzi-wy dla n. Mamy:

(1 + t)n+1 = (1 + t)n(1 + t) =

(1 + t).

k=0

Współczynnik przy tk po prawej stronie wynosi:

k − 1

Rozdział 1. Kombinatoryka

Pierwszy składnik pochodzi od iloczynu:

n tk−1 · t, a drugi od iloczynu: ntk · 1. Ze

k−1

wzoru (1.4) wynika, że współczynnik przy tk wynosi n+1.

Jeżeli do wzoru Newtona podstawimy t = b , a potem pomnożymy obie strony przez an,

to otrzymamy inną znaną wersję wzoru Newtona.

Wniosek 1.13 Dla dowolnych liczb rzeczywistych a i b i dowolnej liczby całkowitej n ≥

0 :

(a + b)n =

an−kbk.

k=0

Jeżeli podstawimy t = 1 do wzoru z twierdzenia 1.12, to otrzymamy:

2n =

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 ˛

acego 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:

0 =

(−1)k

k=0

Zauważmy, że w sumie po prawej stronie z plusem występują symbole Newtona n

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

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 znaleź ć 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 podzbiorów, to przynajmniej jeden z tych podzbiorów ma |A| lub więcej elementów.

Dowód Nie wprost. Przypuśćmy, że każdy z k podzbiorów ma mniej niż |A| elementów.

Wtedy cały zbiór A ma mniej niż k |A| = |A| elementów; sprzeczność.

Przykład 1.16 Wyobraźmy sobie urnę z białymi i czarnymi kulami, po 10. Jeżeli wylosujemy trzy kule, to będ ˛

a 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 ˛

a się przez poda-

nie dłoni. Pokażemy, że wśród nich znajd ˛

a 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 ˛

a być więc dwie osoby z t ˛

a sam ˛

a 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|.

Wyobraź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 podzielnych przez 3. Liczby podzielne przez 2 lub 3 tworz ˛

a 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.

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 ˛

a 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ł ˛

aczania i wył ˛

aczania

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 ˛

a w koszykówkę i pływaj ˛

a, jest 28; takich, którzy graj ˛

a w koszykówkę i

szachy, jest 32, takich, którzy graj ˛

a w szachy i pływaj ˛

a, jest 35, a takich, którzy uprawia-

j ˛

a wszystkie trzy sporty, jest 20. Pytanie: ilu studentów nie uprawia ani koszykówki, ani pływania? To zadanie można rozwi ˛

azać za pomoc ˛

a tak zwanego diagramu Venna (rysu-

nek ?? ). Posługuj ˛

ac 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

Rysunek 1.1: Diagram Venna

pływacy

szachiści

koszykarze

Przykład 1.21 W przykładzie 1.20 X to zbiór wszystkich studentów, A1 to uprawiaj ˛

acy

koszykówkę, A2 — pływanie, a A3 — szachy:

• A{1,2} = A1 ∩ A2

to uprawiaj ˛

acy koszykówkę i pływanie,

• A{1,3} = A1 ∩ A3

to uprawiaj ˛

acy koszykówkę i szachy,

• A{2,3} = A2 ∩ A3

to uprawiaj ˛

acy pływanie i szachy,

• A{1,2,3} = A1 ∩ A2 ∩ A3

to uprawiaj ˛

acy wszystkie trzy sporty.

Twierdzenie 1.22 (zasada wł ˛

aczania i wył ˛

aczania) Niech X , będzie dowolnym skończo-

nym zbiorem (uniwersum), a A1, . . . , An dowolnymi jego podzbiorami. Wtedy liczba elementów uniwersum X , które nie należ ˛

a do żadnego podzbioru Ai , wynosi:

(−1)|I||AI|.

(1.7)

I⊂{1,...,n}

Rozdział 1. Kombinatoryka

Sumujemy tutaj po wszystkich podzbiorach I zbioru {1, . . . , n} , a AI oznacza przekrój AI = T

i∈I

i .

Przykład 1.23 Stosuj ˛

ac zasadę wł ˛

aczania i wył ˛

aczania do przykładu ze studentami mo-

żemy teraz policzyć studentów, którzy nie uprawiaj ˛

a ż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

X (−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 = T

i∈I

i wtedy 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:

X (−1)|I|.

I⊂J

Jest to suma po wszystkich podzbiorach I zbioru J . Uporządkujmy teraz składniki tej

sumy według mocy podzbiorów I. Mamy j podzbiorów mocy i, więc:

(−1)|I| =

(−1)i = (1 − 1)j = 0.

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

[ Ai

i=1

możemy wykorzystać wzór (1.7), przy założeniu, że X = Sn

i=1

i. Mamy wtedy

1.12. Przestawienia

Twierdzenie 1.24

n

[

= −

(−1)|I||AI |.

i=1

I⊂{1,...,n}

I6=∅

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:

X (−1)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:

I | =

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}

Pogrupujmy teraz składniki sumy według mocy zbiorów I. Mamy n podzbiorów mocy

i. Dla każdego z nich składnik sumy wynosi (−1)i(n − i)!, tak więc liczba przestawień

wynosi:

(−1)i

(n − i)!.

i=0

Twierdzenie wynika teraz z równości n(n − i)! = n! .

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

zbioru {1, . . . , 7}. W tym celu losujemy liczbę naturalną k od 1 do 7 = 35, a następnie 3

generujujemy podzbiory, aż do elementu k.

1.13.1

Generowanie podzbiorów

Algorytm wypisuj ˛

acy 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 ≤ i ≤ 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 ˛

ace 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 ˛

acy 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

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 ˛

ace 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óź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ą

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.

Rozdział 1. Kombinatoryka

1.13.3

Generowanie permutacji

Algorytm generowania permutacji zbioru {1, . . . , n}:

Pierwsza permutacja to identyczność, czyli ai = i, dla 1 ≤ i ≤ n.

Aby wypisać następną po (a1, . . . , an) permutację:

Znajdujemy największe j, 1 ≤ j ≤ 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ększy 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

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) 6= 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ędź 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

Oblicz π1 ◦ π2, π2 ◦ π1, π−1

π−1

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?

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)?

24. Udowodnij wzór k n = n n−1

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.

25. Udowodnij wzór Pn

n2 = 2n.

k=0

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.

27. Udowodnij, że n jest największe dla k = d n e i k = b n c.

28. Udowodnij, że 2n ≥ 22n .

2n+1

29. Rozwiń wielomian (1 + t)8.

30. Udowodnij, że Pn

n2i = 3n.

i=0

31. Udowodnij wzory:

n − 1

n − 2

+ · · · +

n − 1

n − 2

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

37. Ułamek m przedstawiamy w postaci dziesiętnej. Udowodnij, że okres tego ułamka

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 ≥ 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

Wyobraź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.

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.

1. Udowodnij, że liczba najkrótszych dróg z punktu A do punktu B wynosi k+m.

2. Udowodnij, że liczba funkcji niemalejących ze zbioru {1, . . . , n} w zbiór {1, . . . , k}

wynosi k+n−1.

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 najkró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.

1. Udowodnij, że istnieje n+k−1 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

1.15.3

Wybór n przedmiotów k rozróżnialnych typów

Wyobraź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.

1. Pokaż, że można to zrobić na n+k−1 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-

elementowego wynosi n+k−1.

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.

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?

Rozdział 1. Kombinatoryka

1.15.6

Podziały uporz ˛

adkowane

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 ≤ i ≤ k. Zakładamy przy

tym, że kolejność podzbiorów jest istotna.

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 jest równa zaokrągleniu liczby n! do najbliższej liczby naturalnej; e jest podstawą loga-e

rytmu naturalnego.

Wskazówka. Skorzystaj z twierdzenia 1.25, z rozwinięcia: e−1 = P∞ (−1)i oraz z i=0

oszacowania:

(−1)i

P∞

≤

i=n+1

(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:

(−1)i

(k − i)n.

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

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 ˛

a funkcj ˛

a koloruj ˛

ac ˛

a 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 ≤ i ≤ 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ę.

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 6= v, v 6= w, u 6= 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 wierzchoł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

Wyobraź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.

Ł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 ≥ |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 S

= |J|. Załóżmy najpierw, że istnieje podzbiór krytyczny J różny od całego

j∈J

zbioru {1, . . . , n}. Niech C = S

j∈J

j .

Na podstawie indukcji można w nim znaleźć 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.

[

(Ai − C) =

(Ai) − |C| ≥ |K| − |J| = |I|.

i∈I

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.