Wojciech Kordecki - Matematyka dyskretna (Materiały pomocnicze).pdf.pdf

(169 KB) Pobierz
C:\Users\Wojtek\Tex\md\md2003.DVI
Wojciech Kordecki
Matematyka
Materiaªy pomocnicze
Wrocªaw 2003
dyskretna
Spis tre±ci
Wst¦p
1
1. Relacje, funkcje i rozmieszczenia
2
1.1. Zbiory cz¦±ciowo uporz¡dkowane
2
1.2. Funkcje i rozmieszczenia
2
1.3. Zadania
4
2. Permutacje
6
2.1. Rozkªad permutacji na cykle
6
2.2. Liczby Stirlinga pierwszego rodzaju
8
2.3. Zadania
9
3. Kombinacje
11
3.1. Wspóªczynnik dwumienny
11
3.2. Generowanie podzbiorów
12
3.3. Zbiory z powtórzeniami
13
3.4. Zadania
14
4. Podziaªy
16
4.1. Zasada wª¡czania { wyª¡czania
16
4.2. Liczby Stirlinga drugiego rodzaju
17
4.3. Zadania
19
5. Funkcje tworz¡ce
20
5.1. Szeregi formalne
20
5.2. Zastosowania funkcji tworz¡cych
21
5.3. Zadania
22
Literatura
23
i
1
Wst¦p Matematyka dyskretna, nazywana jest te» kombinatoryk¡, analiz¡ kombinato-
ryczn¡ lub matematyk¡ zbiorów sko«czonych. Ta ostatnia nazwa najrzadziej
u»ywana (bo najdªu»sza), najdokªadniej okre±la zakres tego dziaªu matematy-
ki. W caªym wykªadzie mówi¡c zbiór, b¦dziemy mieli na my±li zbiór sko«czony,
chyba »e wyra¹nie powiemy, »e jest inaczej.
Wykªad z Matematyki Dyskretnej, który prowadziªem w latach 1997-2000,
byª przeznaczony dla I roku studiów in»ynierskich na Wydziale Podstawowych
Problemów Techniki, Politechniki Wrocªawskiej. Program wykªadu obejmowaª
mi¦dzy innymi nast¦puj¡ce zagadnienia:
1. Funkcje i rozmieszczenia.
2. Permutacje, rozkªad permutacji na cykle, liczby Stirlinga pierwszego ro-
dzaju.
3. Kombinacje, wspóªczynniki dwumianowe, zbiory z powtórzeniami.
4. Zasada wª¡czania { wyª¡czania, podziaªy zbioru, liczby Stirlinga drugie-
go rodzaju.
5. Funkcje tworz¡ce.
Zadania pochodz¡ z list ukªadanych do wykªadu w latach 1997/98 i 1999/00.
Znaczna ich cz¦±¢ byªa uªo»ona przez dra Marka Zakrzewskiego i dra Bogdana
Pawlika.
2
1. Relacje, funkcje i rozmieszczenia
1.1. Zbiory cz¦±ciowo uporz¡dkowane
na X
nazywa si¦ cz¦±ciowym porz¡dkiem , je±li jest zwrotna, przechodnia i antysy-
metryczna, tzn. je±li
4
x 4 x;
x
4
y
^
y
4
z =
)
x
4
z;
x
4
y
^
y
4
x =
)
x = y
Posety
Par¦ ( X;
4
)nazywasi¦ zbiorem cz¦±ciowo uporz¡dkowanym , (partially ordered
set = poset). Je»eli wiadomo o jaki porz¡dek chodzi, to zbiorem cz¦±ciowo
uporz¡dkowanym nazywa si¦ te» sam zbiór X . Je»eli dla pewnych elementów
x; y
x , to elementy te s¡ porównywalne . Je»eli
dowolne dwa elementy s¡ porównywalne, to porz¡dek nazywa si¦ liniowym .
Je»eli x
X zachodzi x
4
y lub y
4
4
y i x
= y to pisze si¦ x
y .Element x
2
X jest
minimalny , je±li nie istnieje y
2
X taki, »e y
x ,
maksymalny , je±li nie istnieje y
2
X taki, »e x
y ,
najmniejszy ,je±li x
4
y dla ka»dego y
2
X ,
X .
Element najmniejszy nazywa si¦ zerem ,anajwi¦kszy jedynk¡ zbioru cz¦±ciowo
najwi¦kszy ,je±li y
4
x dla ka»dego y
2
Zero i jeden
uporz¡dkowanego, oznaczane s¡ one cz¦sto przez 0 i 1.
Przykªad. Rodzina
R
=2 Z wszystkich podzbiorów dowolnego zbioru Z z
relacj¡ zawierania
jest zbiorem cz¦±ciowo uporz¡dkowanym (
R
;
). Elemen-
tem najwi¦kszym jest Z , a najmniejszym
;
. Równie» dowolna rodzina
S
2 Z
jest zbiorem cz¦±ciowo uporz¡d-
kowanym, cho¢ 0 i 1 mog¡ by¢ inne lub nie istnie¢.
Niech ( X; 4 ) b¦dzie zbiorem cz¦±ciowo uporz¡dkowanym oraz Y X .Je±li
ka»de dwa elementy zbioru Y s¡ porównywalne, to Y jest ªa«cuchem ,je±li
a«cuchy
za± »adne dwa ró»ne nie s¡ porównywalne, to Y jest antyªa«cuchem. Ka»dy
ªa«cuch ma element najmniejszy i najwi¦kszy, czyli pocz¡tek i koniec ªa«cucha.
1.2. Funkcje i rozmieszczenia
Zbiory
w pudeªkach
Niech jXj oznacza moc (liczb¦ elementów) zbioru sko«czonego X . Klasycznym
zadaniem kombinatoryki jest nast¦puj¡cy problem: dla danych zbiorów X i
Y ,gdzie
j
X
j
= m ,
j
Y
j
= n znale¹¢ liczb¦ wszytkich funkcji f : X
!
Y
speªniaj¡cych dane ograniczenia.
Twierdzenie 1.2.1. Je±li
j
X
j
= m i
j
Y
j
= n , to liczba wszystkich funkcji
f : X
!
Y jest równa n m .
Niech X b¦dzie dowolnym zbiorem (sko«czonym). Relacja binarna
2
podzbiorów zbioru Z z tak¡ sam¡ relacj¡
1.2. Funkcje i rozmieszczenia
3
Y s¡ ci¡gami dªugo-
±ci m o wyrazach ze zbioru Y . Ka»dy wyraz mo»na wybra¢ na n sposobów,
wszystkich wi¦c ci¡gów jest n m .
f
1 ; 2 ;:::;m
g
. Funkcje f : X
!
Elementy
w pudeªkach
Zadanie powy»sze formuªuje si¦ cz¦sto jako zadanie znalezienia liczby rozmiesz-
cze« m elementów w n pudeªkach.
Ograniczaj¡c si¦ do funkcji ró»nowarto±ciowych (wzajemnie jednoznacznych),
otrzymujemy nast¦puj¡ce wynik.
Twierdzenie 1.2.2. Je±li
j
X
j
= m i
j
Y
j
= n , to liczba funkcji ró»nowarto-
±ciowych f : X
!
Y jest dla m
¬
n równa
( n ) m = n ( n
−
1) ::: ( n
−
m +1) ;
(1.2.1)
gdzie dodatkowo przyjmuje si¦ ( n ) 0 =1.Dla m>n liczba ta jest równa zeru.
n . Pierwszy wyraz ci¡gu mo»na
wybra¢ na n sposobów, drugi na n − 1, a ogólnie i -ty wyraz mo»na wybra¢ na
m
f
1 ; 2 ;:::;m
g
oraz m
¬
−
( i
−
1) = m
−
i + 1 sposobów, co daje wzór (1.2.1). Dla m>n nie ma
funkcji f : X
! Y ró»nowarto±ciowych.
Permutacje
isilnie
Jest to zadanie znalezienia liczby rozmieszcze« m elementów w n pudeªkach,
gdy w ka»dym pudeªku mo»na umie±ci¢ co najwy»ej jeden element.
Je±li m = n ,to( n ) m jest oznaczane przez n ! i nazywane silni¡ liczby n .Je±li
X = Y , to ró»nowarto±ciow¡ funkcj¦ f : X
!
X nazywa si¦ permutacj¡ zbioru
X .St¡d
Twierdzenie 1.2.3. Je±li
j
X
j
=
j
Y
j
= n , to liczba funkcji ró»nowarto±ciowych
f : X
!
Y jest równa
n != n ( n − 1) ::: 1 :
Ci¡gi
w pudeªkach
W szczególno±ci istnieje n ! permutacji zbioru n -elementowego.
Zagadnieniem podobnym do zagadnienia rozwi¡zanego w twierdzeniu 1.2.2
jest zagadnienie rozmieszczenia m elementów w n pudeªkach, przy czym ka»-
de pudeªko zawiera ci¡g elementów, (pudeªka mog¡ by¢ te» puste). Dwa roz-
mieszczenia s¡ identyczne, gdy te same pudeªka maj¡ te same ci¡gi elementów.
Rozmieszczenia tego typu nazywa si¦ rozmieszczeniami uporz¡dkowanymi m
elementów w n pudeªkach .
Twierdzenie 1.2.4. Liczba rozmieszcze« uporz¡dkowanych m elementów w
n pudeªkach jest równa
( n ) m = n ( n +1) ::: ( n + m
−
1) ;;
(1.2.2)
gdzie dodatkowo przyjmuje si¦ ( n ) 0 =1.
Dowód. Niech X =
f
x 1 ;x 2 ;:::;x m g
.Element x 1
mo»na rozmie±ci¢ na n spo-
sobów, tyle ile jest pudeªek. Element x 2
mo»na umie±ci¢ na n
−
1 sposobów
Dowód. Oznaczmy X =
Dowód. Niech X =
14024453.001.png 14024453.002.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin