Nieizomorficzne drzewa

daiska · Post autor: **daiska** » 14 paź 2014, o 20:36

Ile jest nieizomorficznych drzew o $\displaystyle{ n}$ wierzchołkach?

Narysowałam sobie wszystkie drzewa dla $\displaystyle{ n \le 7}$, nie znalazłam żadnej analogii...

Dla $\displaystyle{ n \in \left\{1,2,3 \right\}}$ mam $\displaystyle{ 1}$ takie drzewo;
dla $\displaystyle{ n=4}$ mam $\displaystyle{ 2}$ drzewa;
dla $\displaystyle{ n=5}$ mam $\displaystyle{ 3}$ drzewa;
dla $\displaystyle{ n=6}$ mam $\displaystyle{ 6}$ drzew;
Edit: dla $\displaystyle{ n=7}$ mam $\displaystyle{ 11}$ drzew;

Będę wdzięczna za jakiekolwiek wskazówki.

norwimaj · Post autor: **norwimaj** » 15 paź 2014, o 00:20

Nie znam rozwiązania, ale dla $\displaystyle{ n=7}$ chyba jest $\displaystyle{ 11}$ drzew.

daiska · Post autor: **daiska** » 15 paź 2014, o 18:43

Faktycznie Jeszcze chciałam sprawdzić jedno: czy dla $\displaystyle{ n=8}$ jest $\displaystyle{ 20}$ nieizomorficznych drzew?

norwimaj · Post autor: **norwimaj** » 15 paź 2014, o 21:21

Ja naliczyłem ich $\displaystyle{ 23}$.

daiska · Post autor: **daiska** » 15 paź 2014, o 21:42

A mógłbyś ewentualnie wrzucić jakiś skan?

norwimaj · Post autor: **norwimaj** » 15 paź 2014, o 22:33

A których Ci brakuje? Poniżej podaję liczby drzew dla poszczególnych rozkładów stopni wierzchołków:

$\displaystyle{ 7,1,1,1,1,1,1,1\to1,\\
6,2,1,1,1,1,1,1\to1,\\
5,3,1,1,1,1,1,1\to1,\\
5,2,2,1,1,1,1,1\to2,\\
4,4,1,1,1,1,1,1\to1,\\
4,3,2,1,1,1,1,1\to3,\\
4,2,2,2,1,1,1,1\to3,\\
3,3,3,1,1,1,1,1\to1,\\
3,3,2,2,1,1,1,1\to5,\\
3,2,2,2,2,1,1,1\to4,\\
2,2,2,2,2,2,1,1\to1.\\}$

daiska · Post autor: **daiska** » 15 paź 2014, o 22:56

Mam $\displaystyle{ 21}$. Brakuje mi jeszcze $\displaystyle{ 2}$ drzew: $\displaystyle{ 4,3,2,1,1,1,1,1}$

Kombinuję dalej

norwimaj · Post autor: **norwimaj** » 15 paź 2014, o 23:34

\(\displaystyle{ \begin{picture}(0,0)
\put(0,0){
\put(0,0){\line(1,1){20}}
\put(0,20){\line(1,-1){20}}
\put(0,20){\line(0,1){15}}
\put(20,20){\line(0,1){15}}
\put(20,20){\line(1,0){15}}
\put(0,0){\circle*{2}}
\put(20,0){\circle*{2}}
\put(0,20){\circle*{2}}
\put(20,20){\circle*{2}}
\put(10,10){\circle*{2}}
\put(0,35){\circle*{2}}
\put(20,35){\circle*{2}}
\put(35,20){\circle*{2}}
}

\put(45,0){
\put(0,0){\line(1,1){20}}
\put(0,20){\line(1,-1){20}}
\put(35,20){\line(0,1){15}}
\put(20,20){\line(0,1){15}}
\put(20,20){\line(1,0){15}}
\put(0,0){\circle*{2}}
\put(20,0){\circle*{2}}
\put(0,20){\circle*{2}}
\put(20,20){\circle*{2}}
\put(10,10){\circle*{2}}
\put(35,35){\circle*{2}}
\put(20,35){\circle*{2}}
\put(35,20){\circle*{2}}
}

\put(90,0){
\put(0,0){\line(1,1){20}}
\put(0,20){\line(1,-1){20}}
\put(35,20){\line(0,1){15}}
\put(35,20){\line(1,0){15}}
\put(20,20){\line(1,0){15}}
\put(0,0){\circle*{2}}
\put(20,0){\circle*{2}}
\put(0,20){\circle*{2}}
\put(20,20){\circle*{2}}
\put(10,10){\circle*{2}}
\put(35,35){\circle*{2}}
\put(50,20){\circle*{2}}
\put(35,20){\circle*{2}}
}

\put(-10,-10){$.$}
\put(150,-10){$.$}
\put(-10,45){$.$}
\put(150,45){$.$}
\end{picture}}\)

daiska · Post autor: **daiska** » 16 paź 2014, o 11:03

Dziękuję.