Grafy, funkcja tworzaca

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
miglanc
Użytkownik
Użytkownik
Posty: 3
Rejestracja: 18 wrz 2007, o 22:55
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 1 raz
Pomógł: 1 raz

Grafy, funkcja tworzaca

Post autor: miglanc » 18 wrz 2007, o 23:11

Witam! I od razu proszę o pomoc i rozwiązanie zadania:
1)Odkoduj ciąg \(\displaystyle{ (7,4,4,7,5)}\) otrzymany za pomocą kodu Prufera.

2)Znaleźć wzór na funkcje tworzącą dla ciągu \(\displaystyle{ (a_n)}\) dla którego zachodzi następujące równanie rekurencyjne

\(\displaystyle{ \begin{cases}a_0=a_1=1 \\ a_n=2a_{n-1} + 3a_{n-2},\ n\geqslant 2\end{cases}}\)

3)
a)Ile krawędzi ma dopełnienie 3-regularnego grafu prostego na 8 wierzchołkach?
b)Co możesz powiedzieć o grafie na 55 wierzchołkach,o 54 krawędziach i o dwóch składowych spójności?
c)Ile jest drzew rozpiętych cyklu na n-wierzchołkach?
d)Dla jakiego \(\displaystyle{ k}\) k-kostka jest grafem Eulera?

sorka za brak indeksowania i z góry dziękuje za jakąkolwiek pomoc

Następnym razem skorzystaj z:
http://matematyka.pl/viewtopic.php?t=28951
max
Ostatnio zmieniony 19 wrz 2007, o 16:00 przez miglanc, łącznie zmieniany 1 raz.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
max
Gość Specjalny
Gość Specjalny
Posty: 3306
Rejestracja: 10 gru 2005, o 17:48
Płeć: Mężczyzna
Lokalizacja: Lebendigentanz
Podziękował: 37 razy
Pomógł: 778 razy

Grafy, funkcja tworzaca

Post autor: max » 19 wrz 2007, o 16:11

2) Załóżmy, że \(\displaystyle{ F}\) to funkcja tworząca ciągu \(\displaystyle{ (a_{n})}\). Z zależności rekurencyjnej dostajemy:
\(\displaystyle{ F(x) - a_{1}x- a_{0} = 2x(F(x) - a_{0}) + 3x^{2} F(x)\\
F(x) = \frac{1-x}{1 -2x -3x^{2}}}\)

ODPOWIEDZ