115717

Część II. W zadaniach 13-15 proszę podać sposób ich rozwiązania oraz odpowiedź, które należy umieścić bezpośrednio pod zadaniem.

13. (3 pkt.) Ile co najwyżej krawędzi można dodać do poniższego drzewa, aby otrzymać graf planarny?

Odp: 27 — 10 = 17. Rozwiązanie jest analogiczne jak w grupie A.

14. (2 pkt.) Ile drzew spinających ma poniższy graf?

Odp: (i²)⁴. Rozw iązanie jest analogiczne jak w^r grupie A.

15. (3 pkt.) Znajdź funkcję tworzącą ciągu n₀ = 2, a\ = 3. a_n+2 = a_n+i + 3a„.

oo    oo    oo

/(*) = £a_ni“ = 2+3* + £a„;r" = 2 + 3x + £B„₊2*ⁿ⁺²

n=0    n=2    n=0

oo

= 2 + 3x + ^(a_n+1 + 3a_n):rⁿ⁺²

n=0

oo    oo

= 2 +    + xq_r>^.|Xⁿ'^fl + 3^ a_nxⁿ = 2 + 3x + x^2 ^a"^x" + ^3x2 ^2^anX"

n=l    n=0

= 2 + 3x + x(f(x) - 2) + 3x²f(x)

Skąd otrzymujemy

/(*) =

2 +x

\-x- 3x²