[ Pobierz całość w formacie PDF ]
MatematykadyskretnaII
Zbiórzada«
GrzegorzBobi«ski
Wst¦p
Niniejszyzbiórzada«jestowocemprowadzonychprzezemniewlatach1999–
2002¢wicze«zprzedmiotu„MatematykaDyskretnaII”naIIrokuinforma-
tykinaWydzialeMatematykiiInformatykiUniwersytetuMikołajaKoper-
nikawToruniu.Stanowionuzupełnienieprzygotowanychprzezdr.Witolda
Kra±kiewiczanotatekzwykładuztegoprzedmiotu.Zadaniazamieszczonew
zbiorzepochodz¡znast¦puj¡cychpozycjipo±wi¦conychkombinatoryce:
1.VictorBryant,Aspectsofcombinatorics,Awide-rangingintroduction,
CambridgeUniversityPress,Cambridge,1993;
2.PeterCameron,Combinatorics:topis,techniques,algorithms,Cam-
bridgeUniversityPress,Cambridge,1994;
3.ZbigniewPalka,AndrzejRuci«ski,Wykładyzkombinatoryki,cz¦±¢1,
WydawnictwaNaukowo-Techniczne,Warszawa1998;
4.K.A.Pybnikob(red),Kombinatorny
analiz,Zadaqiiupra
ne-
ni
,Nauka,Glavna
redakci
fiziko-matematiqesko
literatu-
ry,Moskva,1982.
Zbiórzawieratak»ezadaniazaproponowaneprzezdr.AndrzejaDaszkiewicza,
dr.WitoldaKra±kiewiczaorazmojegowłasnegoautorstwa.
1
Rozdział1
Zadania
1.1Podstawowepoj¦cia
1.
Nailesposobówztalii52kartmo»nawybra¢10karttak,abybył
w±ródnichdokładniejedenas?
2.
Nailesposobówztalii52kartmo»nawybra¢10karttak,abybył
w±ródnichconajmniejjedenas?
3.
Nailesposobówztalii52kartmo»nawybra¢6karttak,abybyły
w±ródnichkartywszystkichkolorów?
4.
Nailesposobówspo±ródnmał»e«stwmo»nawybra¢jedn¡kobiet¦i
jednegom¦»czyzn¦,którzynies¡mał»e«stwem?
5.
Sadzamynosóbprzyokr¡głymstole.Dwarozsadzeniauwa»amyza
identyczne,je±liwobuprzypadkachka»dyczłowiekmatychsamychs¡sia-
dów.Ilejestmo»liwychsposobówrozsadzenia?
6.
Nailesposobówmo»naposadzi¢przyokr¡głymstolenkobietin
m¦»czyzntak,aby»adnedwieosobytejsamejpłciniesiedziałyoboksiebie?
Dwarozsadzeniauwa»amyzaidentyczne,je±liwobuprzypadkachka»dy
człowiekmatychsamychs¡siadów.
7.
Nailesposobówmo»narozmie±ci¢knierozró»nialnychkulwnponu-
merowanychszufladach,przyzało»eniu,»ewka»dejszufladziemo»eznale¹¢
si¦conajwy»ejjednakula?
8.
Nailesposobówmo»narozmie±ci¢krozró»nialnychkulwnponume-
rowanychszufladach,przyzało»eniu,»ewka»dejszufladziemo»eznale¹¢si¦
conajwy»ejjednakula?
9.
Ilejestpermutacjizbioru{1,...,n},wktórej»adnedwies¡siednie
liczbynies¡parzyste?
2
1.2Metodabijektywna
Konstruuj¡codpowiedniebijekcjeudowodni¢nast¦puj¡cerówno±ci.
(1)
k
n
k
=n
n−1
k−1
n
k
X
n
(2)
k
=n2
n−1
k=1
k
2
n
k
X
n
(3)
=n(n−1)2
n−2
+n2
n−1
k=1
k
2
n
k
n
n−k
=n
2
2n−2
n−1
X
(4)
k=1
n
l
n−l
k−l
n
k
X
k
(5)
=
2
k
l=0
m
l
n
k−l
m+n
k
X
k
(6)
=
l=0
n
2k
n
2k+1
X
=
X
k0
(7)
k0
k
m
n+1
m+1
X
n
(8)
=
k=m
n
k
X
(9)
(m−1)
n−k
=m
n
k=0
n+1
2
2
X
n
(10)
k
3
=
k=1
1.3Reguławł¡czaniaiwył¡czania
10.
Ilejestliczbcałkowitychdodatnichniewi¦kszychni»10000podziel-
nychprzynajmniejprzezjedn¡zliczb2,3,5?
11.
Ilejestcałkowitoliczbowychrozwi¡za«równania
x
1
+···+x
6
=30
spełniaj¡cychponi»szewarunki?
3
n
n
(a)0x
i
10,i=1,...,6.
(b)−10x
i
20,i=1,...,6.
(c)x
1
5,x
2
10,x
3
15,x
4
20,x
i
0,i=1,...,6.
12.
Nailesposobówztalii52kartmo»nawybra¢5karttak,abyotrzy-
ma¢conajmniejjednegoasa,conajmniejjednegokrólaiconajmniejjedn¡
dam¦?
13.
Ilejestpermutacjizbioru{1,2,3,4,5,6,7,8,9,10},wktórychpierw-
szaliczbajestwi¦kszaod2,aostatniajestmniejszaod9?
14.
Ilejestci¡gówdługo±cin,n3,zło»onychzcyfr0,1,...,9takich,
»eka»dazcyfr1,2,3wyst¦pujewka»dymzci¡gówconajmniejraz?
15.
Ilejestmacierzyzero-jedynkowychowymiarachnnan,wktórych
conajmniejjedenwierszjestzerowy?
16.
Jakiejestprawdopodobie«stwo,»eporozdaniukartdobryd»austa-
lonygraczw±ródotrzymanychkartb¦dziemiałczterykartytejsamejwyso-
ko±ci?
17.
Obliczprawdopodobie«stwo,»erzucaj¡cdziesi¦¢razydwomakost-
kamidogryuzyskamywszystkiepary{i,i},gdziei=1,...,6.
18.
Przyokr¡głymstolesadzamynmał»e«stw,naprzemiankobiet¦i
m¦»czyzn¦.Jakiejestprawdopodobie«stwo,»e»adnemał»e«stwonieb¦dzie
siedziałooboksiebie?
1.4Rekurencja
19.
Znale¹¢jawnewzorydlaci¡gówspełniaj¡cychponi»szewarunkire-
kurencyjne.
(a)a
n+2
=5a
n+1
−6a
n
,a
0
=2,a
1
=5.
(b)a
n+2
=a
n+1
−a
n
,a
0
=0,a
1
=1.
(c)a
n+3
=2a
n+2
+a
n+1
−2a
n
,a
0
=0,a
1
=1,a
2
=9.
20.
Znale¹¢jawnewzorydlaci¡gówspełniaj¡cychponi»szewarunkire-
kurencyjne.
(a)a
n+1
−2a
n
=n
2
+n+2,a
0
=0.
(b)a
n+2
+2a
n+1
−3a
n
=1,a
0
=0,a
1
=1.
4
[ Pobierz całość w formacie PDF ]