kombinatoryka

Matematyka dyskretna

Kombinatoryka

Andrzej Szepietowski

Ci¸

agi

Zastanówmy si¸e, ile ci¸agów d lugości k można utworzyć z elementów zbioru zawieraj¸acego n symboli.

Jeżeli zbiór symboli zawiera dwa elementy:

a, b,

to można utworzyć dwa ci¸agi d lugości jeden:

(a), (b),

cztery ci¸agi d lugości dwa:

(a, a), (a, b), (b, a), (b, b).

Aby uzyskać ci¸agi d lugości trzy, post¸epujemy w nast¸epuj¸acy sposób: bierzemy cztery ci¸agi d lugości dwa i najpierw do każdego z nich dopisujemy na pocz¸atku a. Otrzymujemy w ten sposób komplet: (a, a, a), (a, a, b), (a, b, a), (a, b, b).

Zauważmy, że s¸a to wszystkie ci¸agi d lugości trzy z pierwsz¸a liter¸a a. Potem do tych samych czterech ci¸agów d lugości dwa dopisujemy na pocz¸atku symbol b i otrzymujemy komplet:

(b, a, a), (b, a, b), (b, b, a), (b, b, b).

Komplety te s¸a roz l¸aczne i oba zawieraj¸a różne ci¸agi. Razem tworz¸a zbiór wszystkich ci¸agów d lugoś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¸epuj¸ac podobnie, możemy otrzymać szesnaście ci¸agów d lugości cztery.

Twierdzenie 1 Liczba ci¸agów d lugości k o elementach ze zbioru {a, b} wynosi 2k.

Dowód przez indukcj¸

e. Jak już pokazano, s¸a dwa ci¸agi d lugości jeden.

Za lóżmy teraz, że liczba ci¸agów d lugości k wynosi 2k i zauważmy, że wszystkich ci¸agów d lugości k + 1 jest dwa razy wi¸ecej. Jest 2k ci¸agów z pierwszym elementem a i 2k ci¸agów z pierwszym elementem b. Razem mamy 2 · 2k = 2k+1 ci¸agów d lugości k + 1.

Jeżeli zbiór symboli zawiera n elementów, to powtarzaj¸ac powyższe rozumowanie, możemy si¸e przekonać, że istnieje n ci¸agów d lugości jeden, n2 ci¸agów d lugości dwa i ogólnie ci¸agów d lugości k + 1 jest n razy wi¸ecej niż ci¸agów d lugości k. Zachodzi zatem twierdzenie.

Twierdzenie 2 Liczba ci¸agów d lugości k o elementach ze zbioru n-elementowego wynosi nk.

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¸a funkcj¸e f z A w B można przedstawić jako ci¸ag

(f (1), f (2), . . . , f (k)).

Ci¸ag ten jest d lugości k, a jego elementy s¸a wzi¸ete ze zbioru B. Zauważmy, że każdej funkcji odpowiada jeden ci¸ag, i na odwrót, każdy ci¸ag

(b1, b2, . . . , bk)

opisuje jedn¸a funkcj¸e. Mianowicie funkcj¸e, która dla każdego i przypisuje wartość f (i) = bi.

Na przyk lad, jeżeli A sk lada si¸e z czterech elementów:

A = {1, 2, 3, 4},

a B sk lada si¸e z trzech elementów:

B = {1, 2, 3},

to ci¸ag

(2, 2, 2, 2)

opisuje funkcj¸e sta l¸a (która w ca lej swojej dziedzinie przyjmuje wartość 2), a ci¸ag (1, 2, 3, 3)

opisuje funkcj¸e f , która przyjmuje nast¸epuj¸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¸agów d lugości k = |A|

z elementami ze zbioru B. Udowodniliśmy wi¸ec poniższe twierdzenie.

Twierdzenie 3 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.

Ci¸

agi bez powtórzeń

Policzmy teraz, ile jest ci¸agów bez powtórzeń, czyli ci¸agów różnowartościowych. Jeżeli elementy bierzemy ze zbioru trzyelementowego

{1, 2, 3},

to możemy utworzyć trzy ci¸agi jednoelementowe:

(1),

(2),

(3),

sześć różnowartościowych ci¸agów dwuelementowych:

(1, 2),

(1, 3),

(2, 1),

(2, 3),

(3, 1),

(3, 2)

oraz sześć ci¸agó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 luższych ci¸agów różnowartościowych utworzonych z elementów zbioru {1, 2, 3}.

Twierdzenie 4 Jeżeli elementy wybieramy ze zbioru n-elementowego A, to liczba ci¸agó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¸ac na n.

Dowód. Jeżeli budujemy ci¸ag bez powtórzeń, to na pierwszy element ci¸agu możemy wybrać każdy z n elementów zbioru A, na drug¸a pozycj¸e w ci¸agu możemy wybrać już tylko jeden z n−1 elementów (wszystkie poza tym, który zosta l wybrany na pierwszy element ci¸agu) i tak dalej, na każd¸a kolejn¸a pozycj¸e 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¸agu bez powtórzeń z elementami ze zbioru A.

Permutacje

Permutacje to ci¸agi bez powtórzeń d lugości n, wybierane ze zbioru n-elementowego. Na przyk lad, 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 4 liczba permutacji w zbiorze n-elementowym wynosi:

n(n − 1)(n − 2) . . . 1,

czyli jest równa n!.

Funkcja silnia n! określona jest na zbiorze liczb naturalnych w nast¸epuj¸acy sposób: 0! = 1,

(n + 1)! = (n + 1)n!

Z określenia tego otrzymujemy:

1! = 1,

2! = 2 · 1 = 2,

3! = 3 · 2 = 6,

4! = 4 · 6 = 24.

Wartości funkcji silnia szybko rosn¸a, na przyk lad:

5! = 120,

10! = 3 628 800,

20! ≈ 2433 · 1015.

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

√

n! ≈ e−nnn 2πn.

(1)

Dla każdego n zachodz¸a również nast¸epuj¸ace oszacowania:

√

nn n

2πn

≤ n! ≤ 2πn

e 12 .

(2)

Dowody wzoru Stirlinga oraz powyższych oszacowań wychodz¸a poza zakres tego podr¸ecznika.

Czasami używa si¸e innej definicji permutacji. Mianowicie permutacja n-elementowa to dowolna funkcja różnowartościowa ze zbioru {1, 2, . . . , n} na ten sam zbiór. Na oznaczenie permutacji π

używa si¸e zapisu:

. . .

π(1) π(2) . . . π(n)

Na przyk lad, permutacja:

1 2 3 4

π =

2 1 4 3

jest funkcj¸a, która przyjmuje nast¸epuj¸ace wartości:

π(1) = 2,

π(2) = 1,

π(3) = 4,

π(4) = 3.

Dwie permutacje n-elementowe można sk ladać tak, jak sk lada si¸e funkcje. Z lożenie π1 ◦ π2 permutacji π1 i π2 określone jest wzorem:

π1 ◦ π2(x) = π1(π2(x)).

Na przyk lad:

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 laniem z lożenia ma nast¸epuj¸ace w lasności:

• Z lożenie permutacji jest l¸aczne. 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 ladania permutacji, ponieważ dla każdej permutacji π:

id ◦ π = π ◦ id = π.

• Dla każdej permutacji π istnieje permutacja odwrotna (funkcja odwrotna) π−1, spe lniaj¸aca warunek:

π ◦ π−1 = π−1 ◦ π = id.

Powyższe zależności oznaczaj¸a, że zbiór wszystkich permutacji na zbiorze {1, . . . , n} z dzia laniem sk ladania permutacji stanowi grup¸e.

Podzbiory

Policzmy teraz, ile podzbiorów ma skończony zbiór n-elementowy. Jeżeli zbiór sk lada si¸e z trzech elementów:

{a, b, c},

to możemy latwo 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¸a si¸e 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¸azana jego funkcja charakterystyczna, określona nast¸epuj¸acym wzorem: ( 1, gdy i ∈ A,

χA(i) =

0, gdy i /

∈ A.

Dziedzin¸a funkcji χA jest zbiór {1, . . . , n}, a przeciwdziedzin¸a zbiór {0, 1}. Zauważmy, że każdemu podzbiorowi odpowiada jedna funkcja charakterystyczna, i na odwrót, jeżeli weźmiemy dowoln¸a funkcj¸e:

χ : {1, . . . , n} → {0, 1},

to wyznacza ona zbiór:

A = {i | χ(i) = 1}.

Na przyk lad, dla n = 5 funkcja charakterystyczna χA zbioru

A = {2, 3, 5}

jest opisana przez nast¸epuj¸acy ci¸ag:

(0, 1, 1, 0, 1),

a ci¸ag:

(1, 0, 1, 1, 0)

opisuje funkcj¸e charakterystyczn¸a zbioru:

{1, 3, 4}.

Z powyższych rozważań wynika, że liczba podzbiorów zbioru n-elementowego jest równa liczbie funkcji ze zbioru {1, . . . , n} w zbiór {0, 1}. Czyli na podstawie twierdzenia 3 mamy twierdzenie poniższe.

Twierdzenie 5 Każdy zbiór n-elementowy ma 2n podzbiorów.

Podzbiory k-elementowe

Zastanówmy si¸e 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¸e podzbiorów k-elementowych zbioru n-elementowego oznacza si¸e przez

n .

Jest to tak zwany symbol Newtona. Inaczej, n jest równe liczbie sposobów na jakie można wybrać k

k elementów ze zbioru n elementowego. W laśnie pokazaliśmy, że:

= 1,

= 4,

= 6,

= 4,

= 1.

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

n − k

n + 1

(3)

k − 1

Pierwszy wzór bierze si¸e z prostej obserwacji, że wybranie k elementów, które należ¸a do podzbioru A, jest równoważne wybraniu n − k elementów, które do A nie należ¸a.

Aby uzasadnić równość 3, rozważmy k-elementowe podzbiory zbioru

{1, . . . , n, n + 1}.

Policzmy osobno te podzbiory, które zawieraj¸a element n + 1, i osobno te, które go nie zawieraj¸a.

Podzbiorów nie zawieraj¸acych n + 1 jest n, bo wszystkie k elementów trzeba wybrać ze zbioru k

{1, . . . , n}. Podzbiorów zawieraj¸acych n + 1 jest

n , bo k − 1 elementów trzeba wybrać ze zbioru

k−1

{1, . . . , n}. Razem wszystkich k-elementowych podzbiorów zbioru {1, . . . , n, n + 1} jest n + n .

k−1

Korzystaj¸ac z równości 3, możemy obliczać symbole Newtona rekurencyjnie. Najpierw mamy 0 = 1, ponieważ jest jeden zeroelementowy (pusty) podzbiór zbioru zeroelementowego (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 oraz n+1 = 1, a nast¸epnie korzystamy z równania n+1

3. Metod¸e t¸e ilustruje tak zwany trójk¸at Pascala:

W n-tym wierszu (wiersze numerowane s¸a od n = 0) znajduj¸a si¸e symbole Newtona:

. . .

Na skraju znajduj¸a si¸e jedynki, ponieważ n = n = 1. k-ty element w n-tym wierszu dla 0

1 ≤ k ≤ n − 1 jest sum¸a dwóch elementów stoj¸acych bezpośrednio nad nim:

n − 1

k − 1

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

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

(4)

lub

(5)

k!(n − k)!

Oto uzasadnienie wzoru 4: Aby wybrać podzbiór k-elementowy ze zbioru {1, . . . , n}, wybieramy k-elementowy ci¸ag bez powtórzeń i bierzemy do podzbioru elementy tego ci¸agu ignoruj¸ac ich kolejność.

Ponieważ każdemu k-elementowemu podzbiorowi odpowiada k! ci¸agów o tych samych elementach, wi¸ec podozbiorów jest k! razy mniej niż k-elementowych ci¸agów bez powtórzeń. Wzór 4 wynika teraz z twierdzenia 4, a wzór 5 bezpośrednio ze wzoru 4.

Wzór 4 pozwala wyprowadzić oszacowania na wartość symbolu Newtona, dla 1 ≤ k ≤ n:

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

n n − 1

n − k + 1 nk

· · ·

≥

k(k − 1) · · · 1

k − 1

Ponieważ, jak latwo sprawdzić n−i ≥ n dla każdego 1 ≤ i ≤ k − 1. Korzystaj¸ac z nierówności k−i

k! ≥ (k )k wyprowadzonej ze wzoru Stirlinga (2), otrzymujemy górne ograniczenie: e

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

enk

≤

Dwumian Newtona

Symbole Newtona wyst¸epuj¸a w znanym twierdzeniu Newtona.

Twierdzenie 6 (dwumian Newtona) Dla każdej liczby rzeczywistej t oraz liczby ca lkowitej n ≥

0 zachodzi:

n !

(1 + t)n =

tk.

k=0

Pierwszy dowód. (1 + t)n jest wielomianem stopnia n. Policzmy wspó lczynnik tego wielomianu stoj¸acy przy tk. Rozważmy iloczyn:

(1 + t)(1 + t) . . . (1 + t) .

}

razy

Przy rozwijaniu tego wyrażenia wybieramy z każdego czynnika 1 lub t, potem wymnażamy wybrane elementy i sumujemy tak utworzone iloczyny. W iloczynie otrzymamy tk wtedy, gdy t wybierzemy k razy oraz 1 wybierzemy n − k razy. Można to zrobić na n sposobów, tak wi¸ec wspó lczynnik k

przy tk wynosi n.

Drugi dowód przez indukcj¸

e. Wzór jest oczywisty dla n = 0. Za lóżmy teraz, że jest prawdziwy

dla n. Mamy:

n ! !

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

tk (1 + t).

k=0

Wspó lczynnik przy tk po prawej stronie wynosi:

k − 1

Pierwszy sk ladnik pochodzi od iloczynu:

tk−1 · t,

k − 1

a drugi od iloczynu:

n tk · 1.

Ze wzoru 3 mamy teraz:

n + 1

k − 1

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

mamy inn¸a znan¸a wersj¸e wzoru Newtona.

Wniosek 7 Dla dowolnych liczb rzeczywistych a i b i dowolnej liczby ca lkowitej n ≥ 0: n !

(a + b)n =

an−kbk.

k=0

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

n !

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 nieparzystej (o nieparzystej liczbie elementów).

Twierdzenie 8 Dla każdego zbioru zawieraj¸acego n elementów, liczba podzbioró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

0 =

(−1)k

k=0

Zauważmy, że w sumie po prawej stronie z plusem wyst¸epuj¸a symbole Newtona n dla parzystych k

k, a z minusem — dla nieparzystych k. Tak wi¸ec z plusem mamy liczb¸e podzbiorów parzystej mocy, a z minusem liczb¸e 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¸e f , która każdemu podzbiorowi

A ⊂ {1, 2, . . . , n}

przyporz¸adkuje podzbiór

f (A) = A ⊕ {n} = (A − {n}) ∪ ({n} − A),

czyli różnic¸e symetryczn¸a zbioru A i zbioru jednoelementowego {n}. Zauważmy, że funkcja f l¸aczy podzbiory w pary, ponieważ jeżeli

f (A) = B,

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.

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¸ac praw¸a stron¸e tej równości liczymy po kolei elementy zbioru A i dla każdego elementu dodajemy +1 do ogólnej sumy, nast¸epnie liczymy elementy 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¸e teraz jaki jest udzia l poszczególnych elementów w tak powsta lej sumie. Jeżeli jakiś element wyst¸epuje tylko w A lub tylko w B, to jego udzia l wynosi 1. Ale także, jeżeli należy do obu zbiorów A i B to jego udzia l wynosi 1 = 1 + 1 − 1. Dlatego na końcu wynik b¸edzie równy liczbie elementów, które należ¸a do jednego lub drugiego zbioru.

Przyk lad Policzmy ile spośród liczb od 1 do 30 jest podzielnych przez 2 lub 3. Niech A2 oznacza zbiór liczb z tego przedzia lu 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¸e otrzymujemy:

|A2 ∪ A3| = 15 + 10 − 5 = 20.

Podobnie możemy uzasadnić wzór na sum¸e 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 l elementów, które należ¸a tylko do jednego zbioru, wynosi 1, tych, które należ¸a do dwóch (ale nie do trzech naraz), wynosi 1 + 1 − 1 = 1, a tych, które należ¸a do wszystkich trzech zbiorów, 1 + 1 + 1 − 1 − 1 − 1 + 1 = 1.

Przyk lad Policzmy ile spośród liczb 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¸e otrzymujemy:

|A2 ∪ A3 ∪ A5| = 15 + 10 + 6 − 5 − 3 − 2 + 1 = 22.

Jak z tego 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¸epnym rozdziale pokażemy jak można obliczyć sumy dowolnej skończonej klasy zbiorów.

Zasada w l¸

aczania i wy l¸

aczania

Zacznijmy od przyk ladu. W grupie 100 studentów 45 uprawia koszykówk¸e, 53 p lywanie, a 28 jedno i drugie. Pytanie: ilu studentów nie uprawia ani koszykówki, ani p lywania?

Zadanie to można rozwi¸azać ,,na palcach”. 17 = 45 − 28 studentów uprawia tylko koszykówk¸e, a 25 = 53 − 28 studentów uprawia tylko p lywanie. Zatem 70 = 17 + 25 + 28 studentów uprawia jeden z dwóch sportów, a 30 = 100 − 70 nie uprawia ani koszykówki, ani p lywania. Na rysunku 1.1

zilustrowano ten przyk lad. Jest to tak zwany diagram Venna .

Przypuśćmy teraz, że s¸a także studenci graj¸acy w szachy. Graj¸acych w szachy jest 55. Takich, którzy graj¸a w koszykówk¸e i szachy, jest 32, takich, którzy graj¸a w szachy i p lywaj¸a, jest 35, a takich, którzy uprawiaj¸a wszystkie trzy sporty, jest 20. To zadanie też można rozwi¸azać za pomoc¸a diagramu Venna (rysunek 1.2). Na przyk lad, 8 studentów uprawia koszykówk¸e i p lywanie, ale nie gra w szachy, a 22 studentów nie uprawia żadnego sportu.

Zasada w l¸aczania i wy l¸aczania pozwala rozwi¸azywać tego typu zadania bez diagramów Venna.

Figure 1: Diagram Venna

pywanie

koszykwka

Niech X b¸edzie 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.

W naszym przyk ladzie X to zbiór wszystkich studentów, A1 to uprawiaj¸acy koszykówk¸e, A2 —

p lywanie, a A3 — szachy:

• A{1,2} = A1 ∩ A2

to uprawiaj¸acy koszykówk¸e i p lywanie,

• A{1,3} = A1 ∩ A3

to uprawiaj¸acy koszykówk¸e i szachy,

• A{2,3} = A2 ∩ A3

to uprawiaj¸acy p lywanie i szachy,

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

to uprawiaj¸acy wszystkie trzy sporty.

Figure 2: Diagram Venna

pywanie

szachy

koszykwka

Twierdzenie 9 (zasada w l¸

aczania i wy l¸

aczania) Liczba elementów uniwersum X,

które nie należ¸a do żadnego podzbioru Ai, wynosi:

(−1)|I||AI|.

(6)

I⊂{1,...,n}

Sumujemy tutaj po wszystkich podzbiorach I zbioru {1, . . . , n}.

Dowód. Podobnie jak w poprzednim rozdziale, żeby obliczyć sum¸e 6, liczymy elementy poszczególnych zbiorów AI, i dla każdego elementu dodajemy (−1)|I| do sumy (+1, gdy |I| jest parzyste, lub −1, gdy |I| jest nieparzyste). Każdy element x ∈ X może być liczony kilka razy. Udzia l pojedynczego elementu x jest równy sumie wspó lczynnikó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 zbiorze A∅, i jego udzia l w sumie 6 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¸a x. Zauważmy teraz, że x ∈ AI wtedy i tylko wtedy, gdy I ⊂ J. Rzeczywiście x ∈ AI = Ti∈I Ai wtedy i tylko wtedy, gdy x ∈ Ai, dla każdego 13

i ∈ I, czyli gdy I ⊂ J. Tak wi¸ec udzia l elementu x w sumie 6 wynosi:

X (−1)|J|.

I⊂J

Jest to suma po podzbiorach zbioru J. Uporz¸adkujmy teraz sk ladniki tej sumy wed lug mocy podzbiorów I. Mamy j podzbiorów mocy i, gdzie j = |J|, wi¸ec:

(−1)|J| =

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

I⊂J

i=0

Przedostatnia równość wynika ze wzoru Newtona.

Tak wi¸ec wk lady elementów, które nie należ¸a do żadnego Ai, wynosz¸a po 1, a wk lady tych elementów, które należ¸a do jakiegoś Ai, wynosz¸a po 0. A zatem suma 6 zlicza elementy nie należ¸ace do żadnego Ai.

Stosuj¸ac zasad¸e w l¸aczania i wy l¸aczania do przyk ladu 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.

Aby policzyć moc sumy zbiorów

[ Ai

i=1

możemy wykorzystać wzór 6, przy za lożeniu, że

[

X =

Ai.

i=1

Mamy wtedy

Twierdzenie 10

[

Ai| = −

(−1)|I||AI|.

i=1

I⊂{1,...,n}

I6=∅

Przestawienia

Przestawieniem b¸edziemy nazywać permutacj¸e bez punktu sta lego, czyli tak¸a permutacj¸e, w której żaden element nie stoi na swoim miejscu. Wykorzystamy teraz zasad¸e w l¸aczania i wy l¸aczania, do policzenia liczby przestawień w zbiorze n-elementowym.

Twierdzenie 11 Liczba przestawień (permutacji bez punktów sta lych) w zbiorze n-elementowym wynosi:

X (−1)i

i=0

Dowód. Niech X b¸edzie zbiorem wszystkich permutacji na zbiorze {1, . . . , n}, a Ai zbiorem permutacji, w których i jest punktem sta lym, to znaczy π(i) = i. Moc zbioru Ai wynosi:

|Ai| = (n − 1)!,

ponieważ w zbiorze Ai s¸a te permutacje, które permutuj¸a 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 oprócz tych, które należ¸a do I.

Permutacje bez punktów sta lych to te permutacje, które nie należ¸a do żadnego ze zbiorów Ai.

Z zasady w l¸aczania i wy l¸aczania ich liczba wynosi:

(−1)|I|(n − |I|)!.

I⊂{1,...,n}

Pogrupujmy teraz sk ladniki wed lug mocy zbiorów I. Mamy n podzbiorów mocy i. Dla każdego i

z nich sk ladnik sumy wynosi (−1)i(n − i)!, tak wi¸ec liczba przestawień wynosi: n

(−1)i

(n − i)!.

i=0

Twierdzenie wynika teraz z równości:

(n − i)! =

Zadania

1. Ile numerów rejestracyjnych samochodów można utworzyć, jeżeli każdy numer sk lada si¸e z trzech liter i czterech cyfr?

Ile numerów rejestracyjnych można utworzyć, jeżeli b¸edziemy dodatkowo wymagać, aby każdy numer zaczyna l si¸e od spó lg loski?

2. W grupie jest pi¸eć dziewcz¸at i pi¸eciu ch lopców. Na ile sposobów można wybrać podgrup¸e sk ladaj¸ac¸a si¸e z dwóch dziewcz¸at i dwóch ch lopców?

Na ile sposobów można utworzyć w tej grupie pi¸eć par, z jednym ch lopcem i jedn¸a dziewczyn¸a w każdej parze?

3. Znana jest zabawka dla dzieci sk ladaj¸aca si¸e z dwunastu sześciennych klocków z naklejonymi na ściankach fragmentami obrazków. Na ile sposobów można u lożyć te klocki w prostok¸at (trzy rz¸edy po cztery klocki w rz¸edzie)?

4. Ile s lów można utworzyć z liter s lowa ULICA (litery nie mog¸a si¸e powtarzać)?

Ile s lów można utworzyć z liter s lowa MATMA (litery M i A mog¸a wyst¸apić po dwa razy)?

5. Udowodnij wzór:

n − 1

= n

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.

6. Udowodnij wzór:

n !2

k=1

Wskazówka. Policz na dwa różne sposoby, ile n-elementowych grup można utworzyć w klasie z lożonej z n ch lopców i n dziewcz¸at.

7. Udowodnij, że n jest najwi¸eksze dla k = d ne i k = b n c.

8. Udowodnij, że:

22n

≥

n + 1

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

10. Przedstaw wzór na sum¸e czterech zbiorów A, B, C i D.

11. Wyznacz liczb¸e elementów |A ∩ B ∩ C| oraz |C|, wiedz¸ac, że |A| = 10, |B| = 9, |A ∩ B| = 3,

|A ∩ C| = 1, |B ∩ C| = 1 oraz |A ∪ B ∪ C| = 18.

12. Oblicz ile liczb mniejszych od 100 jest podzielnych przez 2, 3 lub 5.

13. Oblicz ile liczb mniejszych od 100 nie jest podzielnych przez 2, 3, 5 lub 7. Udowodnij, że wszystkie te liczby oprócz 1 s¸a pierwsze. Ile jest liczb pierwszych mniejszych od 100?

14. k-elementowe kombinacje z powtórzeniami ze zbioru n-elementowego s¸a to k-elementowe wybory elementów zbioru n-elementowego, w których elementy mog¸a si¸e powtarzać i w których nie jest istotna kolejność wybieranych elementów. Na przyk lad, mamy cztery 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.

15. Udowodnij, że liczba przestawień (permutacji bez punktów sta lych) w zbiorze n-elementowym jest równa zaokr¸agleniu liczby n! do najbliższej liczby naturalnej; e jest podstaw¸a logarytmu e

naturalnego.

Wskazówka. Skorzystaj z twierdzenia 11, z rozwini¸ecia:

∞

X (−1)i

e−1 =

i=0

oraz z oszacowania:

∞

(−1)i

≤

(n + 1)!

i=n+1

16. Udowodnij, że liczba surjekcji (funkcji na ca l¸a przeciwdziedzin¸e) ze zbioru n-elementowego na zbiór k-elementowy wynosi:

(−1)i

(k − i)n.

i=0

Wskazówka. Skorzystaj z zasady w l¸aczania i wy l¸aczania dla zbioru wszystkich funkcji ze zbioru {1, . . . , n} w zbiór {1, . . . , k}. Zbiór Ai to funkcje, które nie maj¸a elementu i w obrazie.