Kombinatoryka
Andrzej Szepietowski
1
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.
2
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.
1
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.
3
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),
2
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.
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¸agu bez powtórzeń z elementami ze zbioru A.
4
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,
3
(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
√
nn n
2πn
≤ n! ≤ 2πn
e 12 .
(2)
e
e
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
.
π(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
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 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 π, ρ, σ: π ◦ (ρ ◦ σ) = (π ◦ ρ) ◦ σ.
4
• 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.
5
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},
5
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.
6
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 .
k
6
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:
!
!
!
!
!
4
4
4
4
4
= 1,
= 4,
= 6,
= 4,
= 1.
0
1
2
3
4
Z definicji wynika, że jeżeli k > n, to n = 0. Zachodz¸a dwa wzory:
k
!
!
n
n
=
,
k
n − k
!
!
!
n + 1
n
n
=
+
.
(3)
k
k
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
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).
0
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
0
3. Metod¸e t¸e ilustruje tak zwany trójk¸at 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¸a od n = 0) znajduj¸a si¸e symbole Newtona:
!
!
!
!
n
n
n
n
. . .
.
0
1
2
n
Na skraju znajduj¸a si¸e jedynki, ponieważ n = n = 1. k-ty element w n-tym wierszu dla 0
n
1 ≤ k ≤ n − 1 jest sum¸a dwóch elementów stoj¸acych bezpośrednio nad nim:
!
!
!
n
n − 1
n − 1
=
+
.
k
k
k − 1
7
Jeżeli 0 ≤ k ≤ n, to symbol Newtona można też obliczyć ze wzoru:
!
n
n(n − 1) · · · (n − k + 1)
=
(4)
k
k!
lub
!
n
n!
=
(5)
k
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(n − 1) · · · (n − k + 1)
n n − 1
n − k + 1 nk
=
=
· · ·
≥
.
k
k(k − 1) · · · 1
k
k − 1
1
k
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 )k wyprowadzonej ze wzoru Stirlinga (2), otrzymujemy górne ograniczenie: e
!
n
n(n − 1) · · · (n − k + 1)
nk
enk
=
≤
≤
.
k
k!
k!
k
7
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 !
X
n
(1 + t)n =
tk.
k
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) .
|
{z
}
n
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.
k
8
Drugi dowód przez indukcj¸
e. Wzór jest oczywisty dla n = 0. Za lóżmy teraz, że jest prawdziwy
dla n. Mamy:
n ! !
X
n
(1 + t)n+1 = (1 + t)n(1 + t) =
tk (1 + t).
k
k=0
Wspó lczynnik przy tk po prawej stronie wynosi:
!
!
n
n
+
.
k − 1
k
Pierwszy sk ladnik pochodzi od iloczynu:
!
n
tk−1 · t,
k − 1
a drugi od iloczynu:
!
n tk · 1.
k
Ze wzoru 3 mamy teraz:
!
!
!
n
n
n + 1
+
=
.
k
k − 1
k
2
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 !
X
n
(a + b)n =
an−kbk.
k
k=0
Jeżeli podstawimy t = 1 do wzoru z twierdzenia 6, to otrzymamy:
n !
X
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 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.
9
Pierwszy dowód. Jeżeli podstawimy t = −1 do wzoru Newtona, to otrzymamy: n
!
X
n
0 =
(−1)k
.
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,
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.
2
8
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.
10
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.
9
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.
11
pywanie
25
28
30
17
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.
12
pywanie
22
10
15
8
20
5
12
8
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:
X
(−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:
i
j
!
X
X
j
(−1)|J| =
(−1)i = (1 − 1)j = 0.
i
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.
2
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
n
[ Ai
i=1
możemy wykorzystać wzór 6, przy za lożeniu, że
n
[
X =
Ai.
i=1
Mamy wtedy
Twierdzenie 10
n
[
X
|
Ai| = −
(−1)|I||AI|.
i=1
I⊂{1,...,n}
I6=∅
10
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:
n
X (−1)i
n!
.
i!
i=0
14
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:
\
|A
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:
X
(−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
!
X
n
(−1)i
(n − i)!.
i
i=0
Twierdzenie wynika teraz z równości:
!
n
n!
(n − i)! =
.
i
i!
2
11
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)?
15
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
n − 1
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.
6. Udowodnij wzór:
n !2
!
X
n
2n
=
.
k
n
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.
k
2
2
8. Udowodnij, że:
!
2n
22n
≥
.
n
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.
k
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.
16
Wskazówka. Skorzystaj z twierdzenia 11, z rozwini¸ecia:
∞
X (−1)i
e−1 =
i!
i=0
oraz z oszacowania:
∞
X
(−1)i
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:
k
!
X
k
(−1)i
(k − i)n.
i
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.
17