22995

5 Zestaw 5 (tydzień 5)

1.    ( T) Kost ka n- wym iarowa H„ jest grafem u-spó/riyni.

Wskazówka: Skorzystać /. definicji rekurenr.yjr.ej kostki oraz z l.w. Mer^era.

2.    Ziiustować (w. Dilworrha na przykładzie zbioru 2‘ z relacją inkluzji gdzie A' - {a JA.

•’». (T) W grafie 6" - (V* E) zbiór C jest pokryciem wierzchołkowy ni wtedy i tylko wtedy, gdy zbiór \ ' - C jest zbiorem niezależnym.

I. Wyprowadzić twierdzenie Kóniga z twierdzenia Dilworr.ha.

Wskazówka: Potraktować graf dwudzielny jako diagram llassego porządku zdefiniowanego następująco: wierzchołki z lewej poprzedzają wierzchołki z prawej.

6 Zestaw 6 (tydzień 6)

(Tj Liczba sposobów w jakie można rozmieścić nawiasy w iloczynie 'xi.ro .. .x_n jest równa liczbie Catalana.

Aa ile spójnych obszarów dzieli płaszczyznę n- prostych a położeniu oyóhiym (żadne dwie r.ie są równoległe, żadne trzy nie przecinają się w jednym punkcie)

• >. (T) Ciąg Fibonacciego F_Tl ma następujące własności: l • • • ł- F_n = /V-2 - L

b) F_ri jest parzyste wtedy i tylko wtedy, gdy 2 dzieli /*.

\

1 \a ile sposobów można pokryć .-szachownico^ 2 x n dominami? ó Rozwiązać: .

- - >*rt

■ »•

-7 ■ "n

— J.i/n—I “K It Ął

— ')

. •    '-n . -    *'7* - I

■h;_n.. i - in: x, 1 iF: s_n

- 0.

v