Lista Nr 4           								26.04.05

Wstęp do programowania

Matematyka Dyskretna

WSKiZ

Matematyka Dyskretna

1.	Podaj wzór jawny na sn, gdzie s0=3 oraz sn= -2sn-1 dla n1.
2.	Podaj wzór jawny na sn,=4sn-2,  gdzie s0=s1=-1.
3.	Powtórz ćwiczenie 2 dla s0=1 i s1=2.
4.	Podaj wzór jawny na sn= -3 sn-1 + 6 sn-2, gdzie s0=1 i s1=2.
5.	Podaj wzór jawny na sn= 5sn-1 – 6,25sn-2, gdzie s0=2 i s1=1.
6.	Podaj wzór jawny na sn= -3sn-1 + 6sn-2, gdzie s0=1 i s1=2.
7.	Podaj wzór jawny na sn= 3sn-1 - 4sn-2, gdzie s0=1 i s1=1.
8.	Podaj wzór jawny na sn= 2sn-1 - 2sn-2, gdzie s0=3 i s1=2.
9.	Ułóż rekurencyjny wzór na:
a.	liczbę permutacji n elementów;
b.	liczbę spójnych obszarów, które płaszczyzna jest podzielona przez n prostych takich, że żadne dwie nie są równoległe i żadne trzy nie przecinają się w jednym punkcie;
c.	na liczbę przekątnych w n-kącie wypukłym.
Następnie, w zadaniach (b) i (c), podaj wzory jawne.
10.	(Wieże Hanoi). Rozważ następującą zabawę: Dane są trzy paliki. Na pierwszy z nich nanizano n krążków różnej średnicy od krążka o największej średnicy na spodzie do najmniejszego na wierzchu. Zadanie polega na przemieszczeniu wszystkich krążków na trzeci palik. W pojedynczym ruchu można przenieść (tylko!) jeden krążek i z jednego palika na drugi. W trakcie przemieszczania nie wolno większego krążka położyć na mniejszym. Ułóż wzór rekurencyjny określających liczbę koniecznych ruchów, a następnie podaj wzór jawny.
11.	Rozważ rodzinę Pn wszystkich podzbiorów zbioru [n]={1,2,...,n}. 
a.	Ile elementów liczy rodzina Pn? 
b.	Rozważ teraz rodzinę Bn tych podzbiorów zbioru [n], które nie zawierają żadnej pary kolejnych liczb. Ułóż wzór rekurencyjny na liczbę elementów rodziny Bn., a następnie podaj wzór jawny.
12.	Rozważmy następującą rodzinę {Ci   :   i= 1,...,n} podzbiorów liczb naturalnych:
C1= {1,2}
Ci={i-1, i, i+1} dla    2  i  n.
Systemem reprezentantów dla rodziny {Ci   :   i= 1,...,n} nazywamy n- elementowy zbiór S={s1,...,sn } taki, że i=1,...,n  {si} = S  Ci.
Ułóż wzór rekurencyjny (a następnie podaj wzór jawny) na liczbę różnych systemów reprezentantów dla rodziny {Ci   :   i= 1,...,n}.