szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
 Tytuł: Ile jest drzew
PostNapisane: 31 sie 2016, o 23:18 
Użytkownik

Posty: 61
Witam.

Treść zadania:
Cytuj:
Niech n > 1. Wyznaczyć liczbę drzew T o zbiorze wierzchołków [n]takich, że jednocześnie deg_{T}(1) = 2 oraz deg_{T}(2) = 1


Nie bardzo wiem jak ruszyc takie zadanie, oraz dodatkowo chciałbym sie zapytać co oznacza ten warunek deg_{T}(1) = 2 oraz deg_{T}(2) = 1, wiem ,że deg oznacza stopień wierzchołka. Ale czy to chodzi o to, że dwa wierzchołki obok siebie mają mieć stopień 2 oraz 1?

Pozdrawiam ;)
Góra
Mężczyzna Offline
 Tytuł: Ile jest drzew
PostNapisane: 1 wrz 2016, o 16:05 
Użytkownik

Posty: 8
Lokalizacja: Śląsk
Ja bym tutaj pokombinował coś z kodem Prufera.

Dla wierzchołka o stopniu 2, możemy w kodzie prufera wybrać jedno z n-2 miejsc: \binom {n-2} {1}

Na każdym z pozostałych n-3 miejsc kodu prufera możemy postawić dowolny z n-2 wierzchołków (wierzchołka o stopniu 1 na pewno w kodzie prufera nie będzie).

Więc ostateczny wynik:

\binom {n-2} {1}  \cdot  (n-2) ^{n-3}

Proszę mnie poprawić jeśli się mylę.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Ile jest drzew - zadanie 2  dram  1
 Ile jest dzielnikow liczby  Anonymous  6
 ile jest liczb 2cyfr/3cyfr, 5cyfr o pocz 12, bez cyfr 4 i 5?  Anonymous  1
 permutacje/ile jest sposobow ustawien/ -prosba o sprawdzenie  alamakota  3
 ile jest liczb trzycyfrowych, mniejszych od 555  Anonymous  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl