ZACHODNIOPOMORSKI UNIWERSYTET TECHNOLOGICZNY
W SZCZECINIE
MATEMATYKA DYSKRETNA
Wykład 6: Elementy kombinatoryki
Prowadzący Wykłady: dr inż. Larisa Dobryakova
2011
Podstawowe określenia (1)
Kombinatoryka rozdział matematyki dyskretnej, który zajmuje się zestawieniami,
czyli grupami utworzonymi z przedmiotów zwanych elementami.
Mówiąc dokładniej, kombinatoryka odpowiada na pytanie, ile da się zbudować
zestawień określonego rodzaju z dostępnych elementów.
Zasada dodawania
Dla dowolnych parami rozłącznych zbiorów skończonych A1,A2,...,An ,
(tj. Ai Aj = Ć, i ą j ) mamy:
A1 A2 ... An = A1 + A2 + ...+ An .
Dla dowolnych zbiorów skończonych AB mamy:
,
A B = A + B .
2
Podstawowe określenia (2)
Metoda włączania-wyłączania
1. Dla dwóch zbiorów: Dla dowolnych zbiorów skończonych AB mamy:
,
A B = A + B - A B .
2. Dla trzech zbiorów: Dla dowolnych zbiorów skończonych A,B,C mamy:
A B C = A + B + C - A B - B C - C A + A B C .
Przykład
W pewnym klubie trenuje 15 osób grających w tenisa, 14 osób grających w
siatkówkę i 12 osób grających w koszykówkę. Spośród nich 3 grają w tenisa i
siatkówkę, 5 osób gra w tenisa i koszykówkę, 7 grają w siatkówkę, a tylko 4 osoby
grają we wszystkie trzy gry. Ile osób trenuje w klubie?
3
Podstawowe określenia (3)
Zasada mnożenia
Dla dowolnych zbiorów skończonych A1,A2,...,An mamy:
A1 A2 ... An = A1 A2 ... An .
Przykład
W turnieju szachowym biorą udział dwie drużyny. Pierwsza drużyna liczy 6
zawodników, natomiast druga drużyna 8 zawodników. Ile różnych indywidualnych
pojedynków może być stoczonych, jeśli zawodnicy jednej drużyny nigdy ze sobą nie
walczą?
4
Kombinacje (1)
Niech A będzie zbiorem skończonym składającym się z n elementów.
Kombinacją z n elementów branych po k nazywamy każdy podzbiór zawierający k
k
elementów danego zbioru A zawierającego n elementów i oznacza się Cn albo
ćn
symbolem Newtona .
Łk ł
Czyli kombinacje to zbiory spełniające dwa następujące warunki:
obejmują jedynie określoną liczbę k spośród danych n elementów, przy czym
k < n
nie jest istotna kolejność elementów kombinacji
5
Kombinacje (2)
Przykład
Wyznaczyć trzyelementowe kombinacje utworzone z pięciu elementów 1,2,3,4,5.
Wyznaczyć dwuelementowe kombinacje utworzone z trzech elementów a,b,c .
Jeżeli liczba n > 1 jest liczbą naturalną, to symbol n ! (czyta się n silnia ) oznacza
iloczyn wszystkich liczb naturalnych, nie większych od n , czyli:
n ! = 1 2 3 ...n .
Ilość kombinacji z n elementów branych po k , gdzie 0 Ł k Ł n , wynosi:
n
ć
n !
k
Cn == .
k
k ! n - k !
( )
Ł ł
6
Permutacje (1)
1. W nauce o kombinacjach zbiór skończony jest uważany za zbiór różnych
elementów niczym między sobą nie związanych.
2. Dla zbioru skończonego uporządkowanego ustala sie pojęcie bezpośredniego
następstwa elementów:
Istnieje jedyny element pierwszy.
Istnieje jedyny element ostatni.
Po każdym elemencie z wyjątkiem ostatniego bezpośrednio następuje jedyny
element zbioru uporządkowanego (tzw. następnik).
Między zbiorem skończonym uporządkowanym, zawierającym n elementów, a
zbiorem n początkowych liczb ciągu naturalnego 1,2,...,n można ustalić
odpowiedniość wzajemnie jednoznaczną, tak że pierwszemu elementowi
zbioru zostaje przyporządkowana liczba 1, ostatniemu liczba n , i gdy
pewnemu elementowi zostaje podporządkowana liczba k , to bezpośrednio po
nim następującemu elementowi musi być przyporządkowana liczba k +1. Tę
odpowiedniość nazywamy numerowaniem elementów danego zbioru
skończonego.
7
Permutacje (2)
3. Każdy dany zbiór skończony, zawierający więcej, niż jeden element, można
uporządkować różnymi sposobami, to znaczy można różnymi sposobami
ponumerować jego elementy.
Każdy zbiór skończony uporządkowany nazywamy permutacją elementów tego
zbioru.
Czyli permutacje to zestawienia spełniające dwa następujące warunki:
każda permutacja obejmuje wszystkie dane elementy
istotna jest tylko kolejność elementów permutacji
Przykład 1
Wyznaczyć wszystkie możliwe permutację z trzech elementów 1,2,3.
Przykład 2
Wyznaczyć wszystkie możliwe permutację z dwóch elementów a,b
.
Ilość wszystkich permutacji, które mogą być utworzone z n elementów, wynosi:
n ! = 1 2 3 ...n
i oznacza się Pn .
8
Podstawienia (1)
Rozważmy zbiór uporządkowany zawierający n elementów.
A = 1,2,...,n
{ }
Jeśli elementy zbioru A ułożone są w kolejności od najmniejszego do największego,
to tworzą one permutację podstawową.
1-1
Wzajemnie jednoznaczne odwzorowanie s : A A na siebie nazywamy
na
podstawieniem.
Podstawienia zbioru A zapisują sie w postaci macierzy dwuwierszowej:
a1 a2 ... an
ć
s =
s a1 s a2 ... s an ,
( ) ( ) ( )
Łł
gdzie ai A.
Podstawienie, w którym wszystkie elementy przekształcają się na siebie, nazywamy
podstawieniem tożsamościowym:
1 2 ... n a1 a2 ... an
ć ć
s ==
1 2 ... n a a2 ... an .
Ł ł Ł 1 ł
9
Podstawienia (2)
Przykład 1
1 2 3 4 ć3 2 1 4
ć
Czy symbole i oznaczają jedno i to samo podstawienie?
4 1 3 2 Ł3 1 4 2
Łł ł
Przykład 2
Wyznaczyć wszystkie podstawienia zbioru .
A = 1,3,5
{ }
Przykład 3
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Ile różnych liczb można otrzymać z cyfr , przy czym:
każda cyfra w zapisie występuje tylko raz
cyfra 0 nie może występować na początku liczby.
10
Rozmieszczenia (1)
Rozmieszczeniem (lub wariacją) n elementów branych po k nazywa się
uporządkowany podzbiór danego zbioru n elementów zawierający k elementów i
k
oznacza się symbolem An .
Dwa różne rozmieszczenia n elementów branych po k różnią się bądz składem
występujących w nich elementów, bądz przy jednakowych składach porządkiem
ustawienia elementów.
Czyli wariacje to zestawienia spełniające dwa następujące warunki:
obejmują jedynie określoną liczbę k < n spośród danych n elementów
istotna jest kolejność elementów rozmieszczenia.
Ilość różnych rozmieszczeń utworzonych z n elementów branych po k , wynosi:
n !
k
An = .
n - k !
( )
11
Rozmieszczenia (2)
Przykład 1
Wyznaczyć wszystkie rozmieszczenia utworzone z czterech elementów 1,2,3,4
branych po trzy.
Przykład 2
Wyznaczyć wszystkie rozmieszczenia utworzone z trzech danych elementów a,b,c
branych po dwa.
Przykład 3
Ile różnych liczb naturalnych można utworzyć z cyfr 0, 1, 2, 3, 4
, jeśli w każdej liczbie
każda z tych cyfr występować będzie nie więcej, niż raz?
12
Powtórzenie elementów (1)
Zdefiniowane powyżej pojęcia można również rozszerzyć na przypadki, gdy brane są
pod uwagę powtórzenia elementów:
kombinacja z powtórzeniami: odpada warunek, że k < n , można również
tworzyć kombinacje k elementowe z n elementów, gdy k ł n
permutacja z powtórzeniami: ilość powtórzeń danego elementu jest ściśle
określona
rozmieszczenie z powtórzeniami: odpada warunek, że k < n , czyli można
również tworzyć rozmieszczenia k elementowe z n elementów, gdy k ł n
13
Powtórzenie elementów (2)
Ilość kombinacji n elementów po k z powtórzeniami wyraża się wzorem:
n + k -1 !
( ) ćn + k -1
( k
Cnk ) = = = Cn +k -1.
k
k ! n -1 !
( )
Łł
Ilość różnych permutacji elementów a1,a2,..,ak z powtórzeniami, w których
elementy a1,a2,..,ak występują odpowiednio n1,n2,..,nk razy, równa się:
n1 + n2 +...+ nk !
( )
P = .
n1,n2,...,nk
n1!n2 !...nk !
Ilość wszystkich rozmieszczeń n elementów po k z powtórzeniami równa się:
k
A = nk .
n
14
Algorytm ustalania rodzaju zestawień z elementów
zbioru
Przy rozwiązywaniu zadań kombinatorycznych można posługiwać się następującym
algorytmem:
1. Kolejność elementów nie jest istotna, zestawienia różnią się tylko składem:
kombinacja.
2. Kolejność elementów w zestawieniach jest istotna:
Zestawienia różnią się tylko kolejnością elementów permutacja.
Zestawienia różnią się kolejnością elementów oraz składem rozmieszczenie.
3. Jeżeli elementy powtarzają się, to kombinacja, permutacja lub rozmieszczenie
będzie z powtórzeniami.
15
Powtórzenie elementów (3)
Przykład
O jakich zestawieniach mowa w poniższych zadaniach:
a. Z 32 liter polskiego alfabetu układamy dowolne, 5 literowe wyrazy.
b. Spośród sześciu osób, tylko cztery mogą otrzymać zaproszenia.
c. 10 osób ustawiamy w szeregu na różne sposoby.
d. W urnie znajduje się 2 kule żółte i 5 zielonych. Wyciągamy 3 kule bez zwracania,
notujemy ilość wyciągniętych kul żółtych i zielonych.
e. W urnie znajdują się 2 kule żółte i 5 zielonych. Wyciągamy kolejno wszystkie kule
bez zwracania i notujemy ich kolory w kolejności ciągnienia.
f. W urnie znajduje się 7 kul, każda w innym kolorze. Wyciągamy kolejno wszystkie
kule bez zwracania i notujemy ich kolory w kolejności ciągnienia.
g. Losujemy 6 ponumerowanych kul z 49.
h. Z cyfr 1,2,3,4,5 układamy różne liczby pięciocyfrowe tak, aby żadna cyfra się nie
powtarzała.
i. Z cyfr 1,2,3,4,5 układamy różne liczby czterocyfrowe tak, aby żadna cyfra się nie
powtarzała.
j. Z cyfr 1,2,3,4,5 układamy różne liczby pięciocyfrowe. Cyfry mogą się powtarzać.
16
Dwumian Newtona (1)
Dla każdych liczb rzeczywistych a,b Ą oraz dla każdej liczby naturalnej n Ą
zachodzi:
n
n
0 0 1 n n 0 k n -k k
a + b = Cn an -0 b +Cn an -1 b1 + ... +Cn -1 a1 bn -1 +Cn a bn -0 =
( )
C a b
n
k =0
Wzór ten nazywamy wzorem lub dwumianem Newtona. Korzystając z tego wzoru
można wyprowadzić wzór na dowolną n tą potęgę sumy.
k
Współczynniki Cn nazywamy współczynnikami dwumianowymi Newtona
ćn
i czasami oznaczamy .
Łk ł
Przykład
n
Wyprowadzić wzór a + b dla n = 4.
( )
Własności dwumianu Newtona:
k n
Cn = Cn -k
k k k
Cn +1 =Cn +Cn -1
n
k
C = 2n
n
k =0
17
Dwumian Newtona (2)
Współczynniki rozwinięcia dwumianu Newtona można otrzymać w prosty sposób
tworząc trójkąt Pascala. Każda liczba w trójkącie Pascala jest równa sumie dwóch
liczb nad nią. Każdy n + 1 wiersz trójkąta zawiera współczynniki dwumianowe dla
( )
n
wyrażenia a + b .
( )
0
a + b 1
( )
1
a + b 11
( )
2
a + b 1 2 1
( )
3
a + b 1 3 3 1
( )
4
a + b 1 4 6 4 1
( )
5
a + b 1 5 10 10 5 1
( )
18
Współczynniki wielomianowe
Rozwinięcie n tej potęgi sumy x1 + x2 + ... + xk w wielomian ma następującą
postać:
n !
n1 n2 nk
x1 + x2 + ... + xk n = x1 x ... xk .
( )
2
n1!n2 !...nk !
n1+n2 !+..+nk =n
Przykład 1
3
Rozwinąć sumę w wielomian x + y + z .
( )
Przykład 2
3 2 4
Znalezć współczynnik przy x y z przy rozwinięciu 9 tej potęgi sumy
9
x + y + z w wielomian.
( )
19
Wyszukiwarka
Podobne podstrony:
Wykład VI minimalizacja zespołu funkcji, projektowanie układów kombinacyjnychNauka o materiałach 2 VIFiz pol VI 2014EKO VI Promocja jako proces komunikacjiStreszczenie Pieśni VI IliadyPrezentacja VI dziaCapítulo VIvi tutorial QWERTY GrayThe?vil s Lover The ResurrectThe Pacific Pt VI PROPER HDTV XviD NoTVParadies Sonata VIR4 VI(1)CHILLOUT rozdział VILP IV VI Prus Bolesław Antekwięcej podobnych podstron