Witam,
mam problem z obliczaniem liczby drzew - wzór (a nawet wzory) są na Wikipedii:
Liczba oznaczonych drzew o n wierzchołkach wynosi:
\(\displaystyle{ n^{n-2}}\)
Liczba drzew na zbiorze n-wierzchołków (gdzie n jest większe bądź równe 2), z których każdy ma stopień d1, d2, ..., dn, a suma stopni to 2n - 2, wynosi:
\(\displaystyle{ {n-2 \choose d_{1}-1,d_{2}-1,...,d_{n}-1 }}\)
I są jak najbardziej zrozumiałe. Problem polega jednak na tym, że nikt nie powiedział, który kiedy stosować. I dla przykładu: mamy taki graf:
I pytanie o liczbę drzew.
Jeżeli użyję pierwszego wzoru to uzyskam wynik 1296.
Jeżeli użyję drugiego wzoru to uzyskam wynik 4.
I tu pojawia się pytanie: to ile ich w końcu jest? Kiedy stosujemy pierwszy a kiedy drugi wzór?
PS. Pytanie jest dokładnie takie jak podałem - nie ma uściślenie typu: podaj liczbę drzew oznaczonych o 6 wierzchołkach czy podaj liczbę drzew na zbiorze 6 wierzchołków.
Dziękuję za wszelką okazaną pomoc
Liczba drzew
-
- Użytkownik
- Posty: 13
- Rejestracja: 30 sty 2013, o 10:26
- Płeć: Mężczyzna
- Lokalizacja: Kraków
-
- Użytkownik
- Posty: 13
- Rejestracja: 30 sty 2013, o 10:26
- Płeć: Mężczyzna
- Lokalizacja: Kraków
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Liczba drzew
Czyli...
Q.
...sformułuj precyzyjnie polecenie, żeby nie trzeba było domyślać się o co chodzi.pytajnik_jest_zajety pisze:I pytanie o liczbę drzew.
Q.
-
- Użytkownik
- Posty: 13
- Rejestracja: 30 sty 2013, o 10:26
- Płeć: Mężczyzna
- Lokalizacja: Kraków
Liczba drzew
Ale problem polega na tym, że ja mam takie pytanie i dlatego właśnie piszę. Może jestem za głupi i nie rozumiem tego "skrótu myślowego" ale ktoś w temacie domyśli się o co chodzi.
Zadanie nie jest trudne bo są dwa proste wzory i każdy je zrobi, problemem jest domyślenie się o co chodzi w zadaniu.
Zadanie nie jest trudne bo są dwa proste wzory i każdy je zrobi, problemem jest domyślenie się o co chodzi w zadaniu.