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
=
Plik z chomika:
TLOD
Inne pliki z tego folderu:
KOMEDIA ROMANTYCZNA DVDRIP PL.avi
(716934 KB)
Aplikacje na symbiana S60v5.rar
(3005 KB)
SymbianS60pack.rar
(13887 KB)
jak sformatować symbiana.txt
(2 KB)
rotateme_unsigned.rar
(18 KB)
Inne foldery tego chomika:
Dokumenty
Filmy
Gry
Programy
Prywatne
Zgłoś jeśli
naruszono regulamin