Ile jest drzew na zbiorze wierzchołków \(\displaystyle{ \left\{ 1,...,n\right\}, n \ge 5 }\), w których \(\displaystyle{ d(1)=2}\) lub \(\displaystyle{ d(2)=2}\)?
Mam pytanie jak zrobić lub gdzie mogę znaleźć dokładnie wytłumaczone takie zadania? Z góry bardzo dziękuję.
Drzewa na zbiorze wierzchołków
-
Karolinaa0
- Użytkownik
- Posty: 266
- Rejestracja: 11 cze 2018, o 19:12
- Płeć: Kobieta
- Lokalizacja: Płock
- Podziękował: 69 razy
Drzewa na zbiorze wierzchołków
Ostatnio zmieniony 22 lut 2020, o 01:42 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
FasolkaBernoulliego
- Użytkownik
- Posty: 157
- Rejestracja: 23 sty 2020, o 16:16
- Płeć: Mężczyzna
- wiek: 30
- Podziękował: 14 razy
- Pomógł: 18 razy
Re: Drzewa na zbiorze wierzchołków
Nie wiem, czy dobrze myślę, ale może warto skorzystać ze .
Rozważamy liczbę drzew na wierzchołkach \(\displaystyle{ \{2, \ldots, n\}}\). Każde z nich ma \(\displaystyle{ n-2}\) krawędzi. W każdą z nich możemy wetknąć wierzchołek \(\displaystyle{ 1}\) i będzie on miał wtedy rząd \(\displaystyle{ 2}\), więc (zakładając, że poprawnie rozumuję) drzew takich, że \(\displaystyle{ d(1) = 2}\) jest
\(\displaystyle{ (n-2) \cdot (n-1)^{n-3}}\).
Tak samo z wierzchołkiem \(\displaystyle{ 2}\).
Teraz rozważmy liczbę drzew na wierzchołkach \(\displaystyle{ \{3, \ldots, n\}}\). Każde z nich ma \(\displaystyle{ n-3}\) krawędzi. W każdą z nich możemy wetknąć wierzchołek \(\displaystyle{ 1}\) i dostajemy wtedy drzewo z \(\displaystyle{ n-2}\) krawędziami. Potem wtykamy wierzchołek 2. Drzew takich, że \(\displaystyle{ d(1)=2, \quad d(2) = 2}\) mamy w takim razie
\(\displaystyle{ (n-2) \cdot (n-3) \cdot (n-2)^{n-4}}\)
W takim razie drzew mających \(\displaystyle{ d(1) = 2}\) lub \(\displaystyle{ d(2) = 2}\) mamy
\(\displaystyle{ 2 (n-2)(n-1)^{n-3} -(n-3)(n-2)^{n-3}}\).
Dla \(\displaystyle{ n=3 }\)się zgadza... ale proszę to rozwiązanie traktować z pewną dozą niepewności, bo pierwszy raz tego typu zadanie robię.
Kod: Zaznacz cały
https://en.wikipedia.org/wiki/Cayley%27s_formulaRozważamy liczbę drzew na wierzchołkach \(\displaystyle{ \{2, \ldots, n\}}\). Każde z nich ma \(\displaystyle{ n-2}\) krawędzi. W każdą z nich możemy wetknąć wierzchołek \(\displaystyle{ 1}\) i będzie on miał wtedy rząd \(\displaystyle{ 2}\), więc (zakładając, że poprawnie rozumuję) drzew takich, że \(\displaystyle{ d(1) = 2}\) jest
\(\displaystyle{ (n-2) \cdot (n-1)^{n-3}}\).
Tak samo z wierzchołkiem \(\displaystyle{ 2}\).
Teraz rozważmy liczbę drzew na wierzchołkach \(\displaystyle{ \{3, \ldots, n\}}\). Każde z nich ma \(\displaystyle{ n-3}\) krawędzi. W każdą z nich możemy wetknąć wierzchołek \(\displaystyle{ 1}\) i dostajemy wtedy drzewo z \(\displaystyle{ n-2}\) krawędziami. Potem wtykamy wierzchołek 2. Drzew takich, że \(\displaystyle{ d(1)=2, \quad d(2) = 2}\) mamy w takim razie
\(\displaystyle{ (n-2) \cdot (n-3) \cdot (n-2)^{n-4}}\)
W takim razie drzew mających \(\displaystyle{ d(1) = 2}\) lub \(\displaystyle{ d(2) = 2}\) mamy
\(\displaystyle{ 2 (n-2)(n-1)^{n-3} -(n-3)(n-2)^{n-3}}\).
Dla \(\displaystyle{ n=3 }\)się zgadza... ale proszę to rozwiązanie traktować z pewną dozą niepewności, bo pierwszy raz tego typu zadanie robię.