Egzamin z matematyki dyskretnej

14 czerwca 2007 r.

Cze

,

sc pierwsza; czas rozwia

,

zywania: 1 godzina i 10 minut.

1.

Udowodnij, _ze dla dowolnych liczb naturalnych

n;

k

takich, _ze

n

>

0 oraz

n



k



0,

liczba wszystkich par uporza

,

dkowanych

hA;

B

i

podzbiorow zbioru

f

1

;

2

;

:

:

:

;

2

ng

takich, _ze

jAj

=

jB

j

=

n

oraz

jA

\

B

j

=

k

, wynosi

(2n)!

(k

!)

2

((n?k

)!)

2

.

2.

Rozwa_zamy grafy

G

o ustalonym zbiorze szesciu wierzcho lkow

V

(

G

) =

f

1

;

2

;

:

:

:

;

6

g

oraz pie

,

ciu krawe

,

dziach. Ile jest wsrod nich takich grafow

G

, _ze _zaden wierzcho lek

z

V

(

G

) nie jest izolowany? Podaj dok ladna

,

wartosc liczbowa

,

.

Prosimy o napisanie rozwia

,

zania ka_zdego zadania na

oddzielnej

,

CZYTELNIE

podpisanej (najlepiej z numerem indeksu) kartce.

Powodzenia!

Egzamin z matematyki dyskretnej

14 czerwca 2007 r.

Cze

,

sc druga; czas rozwia

,

zywania: 1 godzina i 45 minut.

3.

Ile jest s low d lugosci

n



1 nad alfabetem

fa;

b;

c;

d;

e;

f

;

g

g

takich, _ze po

d

oraz

e

zawsze wyste

,

puje

a

, natomiast przed

f

oraz

g

zawsze wyste

,

puje

c

? (Napisz

odpowiednie rownanie lub uk lad rownan rekurencyjnych i podaj wzor ogolny).

4.

Na ile rozro_znialnych sposobow mo_zna z lo_zyc witra_z, maja

,

cy kszta lt siedmioka

,

ta

foremnego z przeka

,

tnymi poprowadzonymi tak jak na poni_zszym rysunku:

za pomoca

,

15 szklanych p lytek (1 siedmioka

,

tnej i 14 trojka

,

tnych), z ktorych ka_zda

jest zabarwiona jednym z dwoch kolorow?

5.

Wieloscian wypuk ly ma

n

wierzcho lkow. Oblicz sume

,

ka

,

tow wszystkich jego scian.

Prosimy o napisanie rozwia

,

zania ka_zdego zadania na

oddzielnej

,

CZYTELNIE

pod-

pisanej (najlepiej z numerem indeksu) kartce.

Powodzenia!