MatDys 2008 5

MatDys 2008 5, studia, matematyka dyskretna

[ Pobierz całość w formacie PDF ]
Cz.Bagi«ski–Materiałydydaktyczne
1
MatematykaDyskretna5/2008
1.
a)Wyznaczy¢najmniejszewarto±cinik;dlaktórychf
n
k
g >1000000000:
b)Wyprowadzi¢zwartywzórnaf
n
3
g:
2.
Udowodni¢,»eliczbarozmieszcze«nró»nychprzedmiotówwmró»nychkomórkachjestrówna
(n;m)=m!f
n
m
g:
3.
Wyznaczy¢wzórnaliczb¦podziałówzbioruA=f1;2;3;:::;ng,któreniezawieraj¡podziału
»adnego(n1)-elementowegopodzbioruzbioruA.
4.
Liczb¡Bella
B
n
nazywamyliczb¦wszystkichpodziałówzbiorun-elementowego:
B
n
=f
n
0
g+f
n
1
g++f
n
n
g:
Wyznaczy¢najmniejsz¡warto±¢n,dlaktórejB
n
>1000000000.Udowodni¢,»eliczbyBellaspeniaj¡
zale»no±¢:
X
n
n
i
B
i
:
B
n+1
=
i=0
n
2
g=
n+1
5.
Udowodni¢,»eliczbyStirlingadrugiegorodzajuspełniaj¡zale»no±ci:a)f
n
+2
n
4
;c)f
n
n
3
g=
n+2
+8
n+1
+6
n
6
:
n
1
g=
n
2
;b)
f
n
4
6
6
6.
Udowodni¢,»e
X
x
n
=
f
n
k
gx
k
;
k=0
gdziex
k
=x(x1)(xk+1)
7.
Wbudowieniemieckiejmaszynyszyfruj¡cej’Enigmy’zasadnicz¡rol¦odgrywaływirnikiib¦ben
odwracaj¡cy.Wszystkieonedokonywałypermutacjisymboli26-literowegoalfabetu.Pozaszyfrowaniu
kolejnejliterytekstunast¦powałobrótjednegolubwi¦cejwirnikówikolejnaliterabyłaszyfrowanaw
innymichustawieniu.Przepływpr¡duprzezwirnikipowodował,»eprzyzało»eniui»kolejnewirniki
wyznaczałypermutacje iab¦benodwracaj¡cy,szyfrowanieoznaczałozło»eniepermutacji
1
1
1
.
=
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EKMFLGDQVZNTOWYHXUSPAIBRCJ
=
ABCDEFGHIJKLMNOPQRSTUVWXYZ
AJDKSIRUXBLHWTMCQGZNPYFVOE
ABCDEFGHIJKLMNOPQRSTUVWXYZ
BDFHJLCPRTXVZNYEIWGAKMUSQO
=
ABCDEFGHIJKLMNOPQRSTUVWXYZ
EJMZALYXVBWFCRQUONTSPIKHGD
=
Przyzało»eniu,»ewirnikiniewykonuj¡»adnegoruchuposzyfrowaniukolejnychliter,zaszyfrowa¢
swojeimi¦inazwisko.Rozło»y¢nailoczyncyklirozł¡cznychwszystkiepowy»szepermutacje.Wy-
znaczy¢donichpermutacjeodwrotne.Pokaza¢,»ezaszyfrowanietekstuzaszyfrowanegodajetekst
jawny.Wyznaczy¢ilejestwszystkichpermutacji,któremaj¡identycznetypy(liczbycykliiichdłu-
go±ci),jakpodanepermutacje.
8.
Niechfb¦dziedowoln¡permutacj¡zpoprzedniegozadania.
a)Znale¹¢takienajmniejszeliczbynaturalnem,»ef
m
=e.
b)Wskaza¢tak¡permutacj¦hwS
26
,dlaktórejnajmniejszaliczbakspełniaj¡cawarunekh
k
=e
jestmo»liwienajwi¦ksza.
n
Cz.Bagi«ski–Materiałydydaktyczne
2
9.
Wyznaczy¢liczb¦wszystkichtranspozycjinale»¡cychdoS
n
:Pokaza¢,»eka»datranspozycja
t=[x y]spełniawarunekt
2
=e:Wyznaczy¢liczb¦wszystkichpermutacjifnale»¡cychdoS
6
,
którespełniaj¡warunekf
2
=e(takiepermutacjenazywamy
inwolucjami
).Poda¢wszystkietakie
permutacjezS
4
:
10.
Wyznaczy¢liczb¦wszystkichnieporz¡dkówwS
4
,S
5
iS
6
.
11.
Wyznaczy¢warto±ciliczbStirlinga[
n
k
]dlawszystkichn;ktakich,»e06n;k67.Poda¢
najmniejszewarto±cinik,dlaktórych[
n
k
]>1000000.
12.
Udowodni¢nast¦puj¡ceto»samo±ci:
a)
n
1
]=
n
2
; c)[
n
n
2
]=
n
4
+2
n+1
;d)[
n
n
3
]=
n
6
+8
n+1
+6
n+2
6
:
4
6
k=0
13.
Udowodni¢,»ewarto±¢bezwzgl¦dnawspółczynnikaprzyk-tejpot¦dzex-awielomianux
n
jest
równa[
n
k
]:
Przygotował:Cz.Bagi«ski
n
P
[
n
k
]=n!;b)[
n
[ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl